P2572 [SCOI2010]序列操作1(老司机树 又称 珂朵莉树)

题目链接：传送门

题目：

题目描述：

lxhgww最近收到了一个01序列，序列里面包含了n个数，这些数要么是0，要么是1，现在对于这个序列有五种变换操作和询问操作：

0 a b 把[a, b]区间内的所有数全变成0

1 a b 把[a, b]区间内的所有数全变成1

2 a b 把[a,b]区间内的所有数全部取反，也就是说把所有的0变成1，把所有的1变成0

3 a b 询问[a, b]区间内总共有多少个1

4 a b 询问[a, b]区间内最多有多少个连续的1

对于每一种询问操作，lxhgww都需要给出回答，聪明的程序员们，你们能帮助他吗？

输入格式：

输入数据第一行包括2个数，n和m，分别表示序列的长度和操作数目

第二行包括n个数，表示序列的初始状态

接下来m行，每行3个数，op, a, b，（0<=op<=4，0<=a<=b<n）表示对于区间[a, b]执行标号为op的操作

输出格式：

对于每一个询问操作，输出一行，包括1个数，表示其对应的答案

这道题正解是用线段树的，但线段树写着非常麻烦。

前聊

老司机树又称珂朵莉树，是一个用set维护的数据结构，他的每个节点都是一个具有相同性质的区间。

介绍：OIwiki

老司机树多用于区间赋值操作，和在此操作下的其他操作，比如区间不同数有多少个。其时间复杂度在数据随机的情况下，挺优的。但如果数据不随机，出题人想卡你，一定能卡成O(n^2logn)…

貌似在数据随机下时间复每次操作大概需要O(n/q)次在set中查找。

#include<bits/stdc++.h>
#define mset(a,b) memset(a,b,sizeof(a))
using namespace std;
typedef long long ll;
typedef pair<int,int> P;
const int N=1e5+20;
struct ODT_tree
{
    struct node//闭区间[l,r]
    {
        int l,r,v;
        node(int l,int r,int v):l(l),r(r),v(v) {}
        node() {}
        bool operator < (const node & o) const
        {
            return l<o.l;
        }
    };
    int n;
    set<node> odtst;
    typedef set<node>::iterator iter;
    inline void iadd(int l,int r,int v)//init_add
    {
        odtst.insert(node(l,r,v));
    }
    iter split(int x)
    {
        if (x > n) return odtst.end();
        auto it = --odtst.upper_bound(node(x,0,0));
        if (it->l == x) return it;
        int l = it->l, r = it->r, v = it->v;
        odtst.erase(it);
        odtst.insert(node(l, x - 1, v));
        return odtst.insert(node(x, r, v)).first;
    }
    void assign(int l, int r, int v)
    {
        auto itr = split(r + 1), itl = split(l);
        odtst.erase(itl, itr);//可能有很多个,也可能很少
        odtst.insert(node(l, r, v));
        pt();
    }
    void up1(int l,int r)//[l,r]区间取反
    {
        auto itr = split(r + 1), itl = split(l);
        for (; itl != itr;)
        {
// itl->v^=1;
            int a=itl->l,b=itl->r,v=itl->v;
            odtst.erase(itl++);
            odtst.insert(node(a,b,v^1));
        }
        pt();
    }
    int qy1(int l,int r)//询问区间[l,r] 1的个数
    {
        auto itr = split(r + 1), itl = split(l);
        int ans=0;
        for (; itl != itr; ++itl)
        {
            if(itl->v==1) ans+=itl->r - (itl->l)+1;
            // Perform Operations here
        }
        return ans;
    }
    int qy2(int l,int r)//询问区间[l,r]最多有多少个连续的1
    {
        auto itr = split(r + 1), itl = split(l);
        int lastv=-1,ls=0;
        int ans=0;
        for (; itl != itr; ++itl)
        {
            if(itl->v==lastv){
                ls+=itl->r - itl->l + 1;
                if(lastv==1 )ans=max(ans,ls);
            }
            else{
                lastv=itl->v;
                ls=itl->r - itl->l + 1;
                if(lastv==1 )ans=max(ans,ls);
            }
            // Perform Operations here
        }
        return ans;
    }
}odt;
int data[N];
int main()
{
    int n,q;
    scanf("%d%d",&n,&q);
    odt.n=n-1;
    for(int i=0; i<n; ++i)
    {
        scanf("%d",data+i);
    }
    int last=-1,ls=0;
    for(int i=0; i<n; ++i)
    {
        if(last==-1)
        {
            last=i;
            ls=1;
            continue;
        }
        if(data[i]==data[i-1]){
            ls++;
        }
        else{
            odt.iadd(last,last+ls-1,data[i-1]);
            last=i;
            ls=1;
        }
    }
    odt.iadd(last,last+ls-1,data[n-1]);
    for(int i=1;i<=q;++i)
    {
        int cmd,a,b;
        scanf("%d%d%d",&cmd,&a,&b);
        if(cmd==0){
            odt.assign(a,b,0);
        }
        else if(cmd==1){
            odt.assign(a,b,1);
        }
        else if(cmd==2){
            odt.up1(a,b);
        }
        else if(cmd==3){
            printf("%d\n",odt.qy1(a,b));
        }
        else {
            printf("%d\n",odt.qy2(a,b));
        }

    }
    return 0;
}