Charging

非常棒的一个二分题（日后可能就是个硬核板子题了）

对于每一个min(tot, x), 我们不妨直接枚举二分x。如果这个x满足满足tot >= x, 即方案数大于等于x的区间交集的数量，那么我们就继续二分。
check函数的写法有点像板子。对于一个区间我们求大于等于x的最大交集区间个数：枚举左端点，对于该左端点的右端点来说，如果区间长度 >= x, 那么我们就继续记录tot， 记录下当前的右端点，然后枚举完当前的左端点的右端点后，动态判断tot（交集区间个数），然后删除对于下一个左端点来说，没有贡献的交集的区间个数（也就时记录下的tot中的有效右端点的个数）；
最坏复杂度（o(logm * (n + m)）

#include <bits/stdc++.h>

using namespace std;

const int N = 6e5 + 10;

vector<int> L[N];
int n, m;
int R[N];

bool check(int x) {
    memset(R, 0, sizeof R);
    int tot = 0;
    //枚举左端点
    for(int i = 1; i <= n; i ++ ) {
        //枚举右端点
        for(int j : L[i]) {
            if(j - i + 1 >= x) {
                tot ++;
                R[j] ++;
            }
        }
        if(tot >= x) return true;
        //减去当前左端点为i时，右端点不符合的情况数
        tot -= R[i + x - 1];
    }
    return false;
}

int main()
{

    scanf("%d%d", &n, &m);

    for(int i = 1; i <= n; i ++ ) {
        int l, r;
        scanf("%d%d", &l, &r);
        L[l].push_back(r);
    }

    //枚举答案长度(长度合法的话需要tot >= x)
    int l = 1, r = m;
    while(l < r) {
        int mid = l + r + 1 >> 1;
        if(check(mid)) l = mid;
        else r = mid - 1;
    }

    printf("%d\n", l);
    return 0;
}