干草堆

考察差分数组

#include<iostream>
#include<algorithm>

using namespace std;

const int N = 1e6 + 10;

int b[N];
int n, k;

void insert(int l, int r)
{
    b[l]++, b[r + 1]--;
}
int main()
{
    cin >> n >> k;
    while(k--)
    {
        int l, r;
        cin >> l >> r;
        insert(l, r);
    }
    for(int i = 1; i <= n; i++) b[i] += b[i - 1];
    sort(b + 1, b + n + 1);
    cout << b[(n + 1) / 2] << endl;
    
    return 0;
}