BZOJ 1858 [SCOI2010] 序列操作

本来想用线段树做，但是考虑到用线段树的话pushup，pushdown函数有点复杂... 看到题目有覆盖操作立刻想到了珂朵莉树，于是现学了一波然后改了一下模板A了这道题。 (珂学是个好东西) (刷这道题全程循环夢違科(珂)学世紀2333333)

    
    #include <iostream>
    #include <set>
    #include <vector>
    #include <algorithm>
    #include <cstdio>
    
    #define __node_it set<node>::iterator
    
    using namespace std;
    
    //define
    const int maxn = 1e5 + 5;
    struct node{
        mutable int l, r, v;
        node(int L,int R = -1, int V = 0):l(L), r(R), v(V){}
        bool operator < (const node& rhs) const{
            return l < rhs.l;
        }
    };
    int n, m;
    set<node> s;
    
    __node_it split(int rt){
        __node_it it = s.lower_bound(node(rt));
        if(it != s.end() && it->l == rt)return it;
        --it;int ll = it->l, rr = it-> r, vv = it->v;
        s.erase(it);
        s.insert(node(ll, rt - 1, vv));
        return s.insert(node(rt, rr, vv)).first;
    }
    
    void assign(int l, int r, int v){
        __node_it itr = split(r + 1), itl = split(l);
        s.erase(itl, itr);
        s.insert(node(l, r, v));
    }
    
    int sum(int l, int r){
        int ans = 0;
        __node_it itr = split(r + 1), itl = split(l);
        for(; itl != itr; ++itl){
            ans += itl->v ? itl->r - itl->l + 1:0;
        }
        return ans;
    }
    
    void reverse(int l, int r){
        __node_it itr = split(r + 1), itl = split(l);
        for(; itl != itr; ++itl){
            itl->v ^= 1;
        }
    }
    
    int cnt(int l, int r){
        int ans = -0x7f7f7f7f, cnt = 0;
        __node_it itr = split(r + 1), itl = split(l);
        for(; itl != itr; ++itl){
            if(itl->v == 1){
                cnt += itl->r - itl->l + 1;
            }
            else{
                cnt = 0;
            }
            ans = max(ans, cnt);
        }
        return ans;
    }
    
    //main
    int main(){
        ios::sync_with_stdio(false);
        cin >> n >> m;int tmp;
        for(register int i = 0; i < n; ++i){
            cin >> tmp;
            s.insert(node(i, i, tmp));
        }
        int x, y, z, a;
        while(m--){
            cin >> x;
            switch(x){
                case 0:
                    cin >> y >> z;
                    assign(y, z, 0);
                    break;
                case 1:
                    cin >> y >> z;
                    assign(y, z, 1);
                    break;
                case 2:
                    cin >> y >> z;
                    reverse(y, z);
                    break;
                case 3:
                    cin >> y >> z;
                    cout << sum(y, z) << endl;
                    break;
                case 4:
                    cin >> y >> z;
                    cout << cnt(y, z) << endl;
                    break;
            }
        }
        return 0;
    }