BZOJ 1858 「SCOI2010」序列操作

区间覆盖，区间求和，区间连续值个数……
珂朵莉树！

骗分神器珂朵莉树，懒得写线段树就用她！

出题人很良心地没有卡珂朵莉树，估计只有发明人才会卡吧……

代码：

#include <cstdio>
#include <set>
#include <algorithm>
using namespace std;
const int N = 1e5;
int n,m;
struct node
{
    int l,r;
    mutable int val;
    inline bool operator<(const node &a) const
    {
        return l < a.l;
    }
};
set<node> tree;
typedef set<node>::iterator IT;
IT split(int x)
{
    IT it = tree.lower_bound((node){x,0,0});
    if(it != tree.end() && it->l == x)
        return it;
    --it;
    int l = it->l,r = it->r;
    int v = it->val;
    tree.erase(it);
    tree.insert((node){l,x - 1,v});
    return tree.insert((node){x,r,v}).first;
}
inline void assign(int l,int r,int val)
{
    IT itr = split(r + 1),itl = split(l);
    tree.erase(itl,itr);
    tree.insert((node){l,r,val});
}
inline void flip(int l,int r)
{
    IT itr = split(r + 1),itl = split(l);
    for(;itl != itr;++itl)
        itl->val ^= 1;
}
inline int query(int l,int r)
{
    IT itr = split(r + 1),itl = split(l);
    int ret = 0;
    for(;itl != itr;++itl)
        ret += itl->val * (itl->r - itl->l + 1);
    return ret;
}
inline int continuity(int l,int r)
{
    IT itr = split(r + 1),itl = split(l);
    int ret = 0,cur = 0;
    for(;itl != itr;++itl)
        if(itl->val)
            cur += itl->r - itl->l + 1;
        else
        {
            ret = max(ret,cur);
            cur = 0;
        }
    return max(ret,cur);
}
int main()
{
    scanf("%d%d",&n,&m);
    int x,last,cnt = 1;
    scanf("%d",&last);
    for(register int i = 2;i <= n;++i)
    {
        scanf("%d",&x);
        if(x == last)
            ++cnt;
        else
        {
            tree.insert((node){i - cnt,i - 1,last});
            last = x;
            cnt = 1;
        }
    }
    tree.insert((node){n - cnt + 1,n,last});
    int op,a,b;
    while(m--)
    {
        scanf("%d%d%d",&op,&a,&b);
        ++a,++b;
        if(op == 0 || op == 1)
            assign(a,b,op);
        else if(op == 2)
            flip(a,b);
        else if(op == 3)
            printf("%d\n",query(a,b));
        else
            printf("%d\n",continuity(a,b));
    }
}