P2572 [SCOI2010]序列操作 珂朵莉树

题目链接：https://www.luogu.com.cn/problem/P2572
题目大意：

思路：珂朵莉树搞一搞，好像数据加强了，只能30分，会T。

#include <bits/stdc++.h>
#define ll long long
#define sit set<node>::iterator
using namespace std;

struct node{
    int l, r;
    mutable ll val;
    int operator<(const node &a) const{
        return l<a.l;
    }
    node(int L, int R, ll Val): l(L), r(R), val(Val){}
    node(int L) : l(L){}
};

struct odTree{
    set<node> s;
    sit Split(int pos){//一个节点分裂[l, r]->[l, pos-1]+[pos, r]
        sit it=s.lower_bound(node(pos));
        if(it!=s.end()&&it->l==pos) return it;
        --it;
        int l=it->l, r=it->r;
        ll val=it->val;
        s.erase(it);
        s.insert(node(l, pos-1, val));
        return s.insert(node(pos, r, val)).first;
    }
    void Assign(int l, int r, ll val){//区间赋值
        sit it2=Split(r+1), it1=Split(l);
        s.erase(it1, it2);
        s.insert(node{l, r, val});
    }
    void Add(int l, int r){//区间[l, r] a[i]取反
        sit it2=Split(r+1), it1=Split(l);
        for(sit it=it1; it!=it2; ++it) it->val^=1;
    }
    ll Query(int l, int r){//求[l, r]的1的个数
        sit it2=Split(r+1), it1=Split(l);
        ll res=0;
        for(sit it=it1; it!=it2; ++it){
            if(it->val==1){
                res+=((it->r)-(it->l)+1);
            }
        }
        return res;
    }
    ll Query2(int l, int r){//求[l, r]的0连续1的个数
        sit it2=Split(r+1), it1=Split(l);
        ll res=0, tmp=0;
        for(sit it=it1; it!=it2; ){
            if(it->val==1){
                tmp=0;
                while(it!=it2&&it->val==1){
                    tmp+=((it->r)-(it->l)+1);
                    ++it;
                }
                res=max(res, tmp);
            }
            else{
                ++it;
            }
        }
        return res;
    }

}Tree;

inline int read(){
    int x=0,f=1;
    char ch=getchar();
    while(ch<'0'||ch>'9'){
        if(ch=='-')
            f=-1;
        ch=getchar();
    }
    while(ch>='0'&&ch<='9'){
        x=(x<<1)+(x<<3)+(ch^48);
        ch=getchar();
    }
    return x*f;
}

int main(){

    int n, m, val;
    n=read(), m=read();
    for(int i=1; i<=n; i++){
        val=read();
        Tree.s.insert(node(i, i, (ll)val));
    }
    Tree.s.insert(node(n+1, n+1, -1));
    for(int i=1; i<=m; i++){
        int op=read(), x=read(), y=read();
        x++, y++;
        if (op == 0) Tree.Assign(x, y, 0);
        else if (op == 1) Tree.Assign(x, y, 1);
        else if (op == 2) Tree.Add(x, y);
        else if (op == 3) printf("%lld\n", Tree.Query(x, y));
        else printf("%lld\n", Tree.Query2(x, y));
    }

    return 0;
}