题解 | 小红的区间修改（一）

根据题意简化成每段区间成功添加到集合后 最大的区间长度

但如果按个遍历集合内每个元素 时间复杂度为$O_n$超时 借助set二分查找优化为$log(n)$后即可

#include <iostream>
#include<algorithm>
#include <set>
#include<vector>
using namespace std;
typedef pair<int,int> PII;
set<PII> p;
int main() {
    int q;
    scanf("%d",&q);
    int tem=0;
    for(int i=1;i<=q;i++){
        int l,r;
        scanf("%d%d",&l,&r);
        auto t=p.lower_bound({l,0});//返回第一个大于等于{l,0}的
        bool st=true;
        if(t!=p.end()&&t->first<=r)st=false;//先看右边  如果为end肯定不会重叠 否则判断是否重叠  
        if(st&&t!=p.begin()){  //在满足右边情况下 如果为第一个则不会重叠 否则进行判断
            auto h=prev(t);    //迭代器prev找前一个
            if(h->second>=l)st=false;
        }
        if(st){
            p.insert({l,r});//不重叠则插入
            tem=max(tem,r-l+2);//注意0肯定存在
        }printf("%d\n",tem);
    }
    return 0;
}