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

void solve(){
    int q;cin>>q;
    int maxl=0;
    set<int> rec;
    auto find=[&](int l,int r){
        auto eL=rec.lower_bound(l);
        if(eL==rec.end())return false;
        if(*eL<=r)return true;
        return false;
    };
    for(int i=1;i<=q;i++){
        int l,r;cin>>l>>r;
        if(!find(l,r)){
            maxl=max(maxl,r-l+1);
            for(int k=l;k<=r;k++){
                rec.insert(k);
            }
        }
        cout<<maxl+1<<endl;
    }
}

易知每次操作只会添加连续的一段(1->x)，因此想要知道种类数，只需要维护最大值即可，而每次操作的最大值即区间长度(R-L+1);

那么现在的问题就是，如何快速查询每次的操作区间内是否已经存在非零数：

我们可以维护一个集合，存储所有的非零索引，对于每次的询问(L,R)，我们可以二分的查询集合中第一个大于等于L的索引eL ， 如果eL <= R 则说明已经存在一个索引 处于 (L,R) 区间内，否则说明不存在；

若是已经存在，我们就进行维护最大值操作，且将(L,R)内的索引全部添加进集合 ，因为 (L,R)的最大值不会超过3e5,索引我们最多添加进3e5个数，时间复杂度O(Nlog(N)) 不会超时