学到了一个新的STL：nth_element
位于头文件algorithm中，这个相当于是算法课本第二章的线性时间选择，在线性时间内选择出第k大/小个元素，非常的简单
主要的原理是把第k个位置的交换一下，所以最后输出就好
用法

// 选出第k个元素
nth_element(arr+1,arr+k,arr+n+1);
nth_element(arr.begin(),arr.begin()+k,arr.end(),cmp);

// 输出结果
cout<<arr[k];

开始解题

题目链接

这个题目运用到了差分的知识点，模板题

前缀和

如果想求数组之间的和，可以引入一个数组表示的是的值，即

就可以将问题转换为

差分

长度为 的整数序列， 个操作，每个操作包含三个整数 ，表示将序列中 之间的每个数加上 。输出进行完所有操作后的序列。

解法：给区间中的每个数加上c：

#include<bits/stdc++.h>
using namespace std;
int n,m,l,r,c;
int arr[100005];
int ed[100005];
int main(){
    scanf("%d %d",&n,&m);
    for(int i=1;i<=n;i++){
        scanf("%d",&arr[i]);
        ed[i]=arr[i]-arr[i-1];
    }
    while(m--){
        scanf("%d%d%d",&l,&r,&c);
        ed[l]+=c;
        ed[r+1]-=c;
    }
    for(int i=1;i<=n;i++){
        ed[i]+=ed[i-1];
        cout<<ed[i]<<" ";
    }
    return 0;
}

本题解法

所以就只需要计算套用差分模板

#include<iostream>
#include<algorithm>
using namespace std;
int N,K,A,B;
int arr[1000005];
int main(){
    cin>>N>>K;
    for(int i=1;i<=K;i++){
        cin>>A>>B;
        arr[A]++;
        arr[B+1]--;
    }
    for(int i=1;i<=N;i++){
        arr[i]+=arr[i-1];
    }
    nth_element(arr+1,arr+(N+1)/2,arr+N+1);
    cout<<arr[(N+1)/2];
    return 0;
}

image.png