珂氏树求条

如下所示

TLE 到 30 分：

#include <bits/stdc++.h>
using namespace std;
const int SIZE=1e5+10;
int n,m,a[SIZE];
struct omg{
    int lf,rt;
    mutable int val;
    omg(int lf,int rt=-1,int val=0):lf(lf),rt(rt),val(val){}
    bool operator<(const omg &rhs)const{
        return lf<rhs.lf;
    }
};
set<omg> wtf;
typedef set<omg>::iterator iter;
iter split(int po){
    iter it=wtf.lower_bound(omg(po));
    if(it!=wtf.end()&&it->lf==po) return it;
    it--;
    int l=it->lf,r=it->rt,v=it->val;
    wtf.erase(it);
    wtf.insert(omg(l,po-1,v));
    return wtf.insert(omg(po,r,v)).first;
}
bool fluh=false;
void flushhh(set<omg> &odt){
    set<omg> ano=odt;
    iter it=ano.begin();
    odt.clear(),odt.insert(*ano.begin());
    for(++it;it!=ano.end();++it){
        if((--odt.end())->val==it->val){
            iter aha=--odt.end();
            odt.erase(aha);
            odt.insert(omg(aha->lf,it->rt,it->val));
        }else odt.insert(*it);
    }
}
int main(){
    cin>>n>>m;
    for(int i=1;i<=n;i++) cin>>a[i];
    int o0=(a[1]==0?1:0),o1=(a[1]==1?1:0);
    for(int i=2;i<=n;i++){
        if(a[i]==0){
            if(o1!=0) wtf.insert(omg(o1,i-1,1)),o0=i,o1=0;
        }else{
            if(o0!=0) wtf.insert(omg(o0,i-1,0)),o1=i,o0=0;
        }
    }
    if(o0!=0) wtf.insert(omg(o0,n,0));
    else wtf.insert(omg(o1,n,1));
    while(m--){
        int o,l,r,qans=0;
        cin>>o>>l>>r,l++,r++;
        iter itr=split(r+1),itl=split(l);
        if(o==0||o==1){
            wtf.erase(itl,itr);
            wtf.insert(omg(l,r,o));
        }else if(o==2) for(iter it=itl;it!=itr;++it) it->val=!it->val;
        else if(o==3){
            for(iter it=itl;it!=itr;++it) qans+=it->val*(it->rt-it->lf+1);
            cout<<qans<<endl;
        }else if(o==4){
            flushhh(wtf);
            itr=split(r+1),itl=split(l);
            for(iter it=itl;it!=itr;++it) qans=max(qans,it->val*(it->rt-it->lf+1));
            cout<<qans<<endl;
        }
    }
    return 0;
}