珂朵莉树，也叫ODT(Old Driver Tree 老司机树)

从前有一天，珂朵莉出现了。。。

然后有一天，珂朵莉树出现了。。。

看看图片的地址 Codeforces可还行)

没错，珂朵莉树来自Codeforces

国外珂学家 滑稽）

---

前置芝士：set的基本操作迭代器（跟指针差不多重载运算符、构造函数的简单了解mutable（下面也会讲暴力枚举常数优化（inline O2 O3 register大法好啊

够简单了吧？除了真正的小白，大家都应该有所了解。

---

废话完了，扯进正题（毕竟你不是珂学家，你是个O·I·E·R）。

珂朵莉树的适用范围（缺一不可，不然复杂度就是不正确的，很容易被卡）：

1. 数据纯随机
2. 有区间修改操作

大概就这两个吧。珂朵莉树毕竟是一种骗分算法（珂朵莉：我不服），想到正解尽量用正解。

---

珂朵莉树的主要思想就是用一个set来维护元素相同的区间。

这里我们以为例，讲一讲珂朵莉树。

先写个结构体。

#define Re register //卡常操作 struct node{    int l, r; mutable bool val;    node( int L, int R = -1, int v = 0 ):l(L), r(R), val(v){}//构造函数    bool operator < ( const node t )const{ return l < t.l; }//重载运算符};

l表示左边界，r表示右边界，val表示l~r保存的值都是val（当然，根据题目需要，val的类型可以改变）。

mutable的作用很简单。由于在set中，元素是以常量方式存储的，不能直接修改。在set中我们是按l排序的，修改val的值实际上没有关系，不会影响set中元素的顺序，把val的类型前加个mutable，就可以直接修改val，否则还要删除元素，再插入进去，降低了效率。因为珂朵莉树比较暴力，我们要尽可能优化复杂度。

1. 建立你的珂朵莉树

ls = 1;     for ( Re int i = 1; i <= N; ++i ) scanf( "%d", &a[i] );    for ( Re int i = 2; i <= N; ++i ) if ( a[i] ^ a[i - 1] ) S.insert( node( ls, i - 1, a[i - 1] ) ), ls = i;    S.insert( node( ls, N, a[N] ) );

直接把连续的一段段插进去即可。

举个例子：

111001100011000

我们就会插入以下几个元素（以 l、r、val顺序

1 3 14 5 06 7 18 10 010 11 112 15 0

炒鸡简单对吧？

1. Split

学过FHQ Treap的童鞋听到这个很熟悉对吧？其实它们作用是差不多的，但是由于FHQ Treap是以二叉查找树结构存储的，但这里的珂朵莉树直接用set存，相对来说简单得多。

Split(pos)的作用就是在某个包含pos的区间[l,r]中，分成两个区间[l,pos - 1],[pos,r]。实现很简单，请看代码。

inline IT Split( Re int pos ){    Re IT t(S.lower_bound(node(pos)));//找到左边界第一个大于等于它的元素    if ( t != S.end() && t->l == pos ) return t; // 如果左边界就是这个元素，不用分了，直接返回[pos,r]也就是[l,r]    t--;//前一个元素就是包含pos的区间    Re int L(t->l), R(t->r); Re bool v(t->val);//存下来把原来的信息    S.erase(t);//删了它！    S.insert( node( L, pos - 1, v ) );//插入区间[l,pos - 1]    return S.insert( node( pos, R, v ) ).first;//插入区间[pos,r]并返回[pos,r]的迭代器}

举例子：

如果把上面那个例子中，Split(2)t 指向[4,5](4是第一个大于等于2的)左边界不是2，t--，指向区间[1,3]分成两个区间[1,1][2,3]返回[2,3]的迭代器

1. Assign

这个操作用于区间修改元素。由于这个操作可以迅速减少set中元素的个数，所以这是珂朵莉树的复杂度保证。

也十分简单，就是把边界Split，中间全部删除再插入一个元素就好了。

inline void Assign( Re int l, Re int r, Re bool v ){//把l到r所有元素统统变成v    Re IT ed(Split(r + 1)), be(Split(l));//Split边界 分成[...l-1] {[l...]...[..r]} [r+1...] be指向;[l...],ed指向[r+1...] 大括号中间全部要删除    S.erase( be, ed );//删去be~ed-1的所有元素，就是大括号中间的部分    S.insert(node( l, r, v ));//插入区间[l,r]}

有一个小细节，要先执行Split(r+1)，再执行Split(l)

为什么呢？

举反例——

还是拿建树那里的例子Assign(2,2)假设先执行Split(2)第一个区间[1,3]变成了[1][2,3]be指向区间[2,3]再执行Split(3)时[2,3]变成了[2][3]ed指向[3]然后如果调用了bebe原指向的区间[2,3]已经被删除了然后RE*8+TLE*1+AC*1

没错反过来的目的就是避免Split右区间时把be指向的区间删了。

1. 区间取反

暴力枚举即可（也要Split）

inline void Change( Re int l, Re int r ){    Re IT ed(Split(r + 1)), be(Split(l));    for ( Re IT it = be; it != ed; ++it ) it->val = !(it->val);}

1. 查询1的个数

也很暴力，一个个枚举

inline int Get1( Re int l, Re int r ){    Re IT ed(Split(r + 1)), be(Split(l)); Re int ans(0);    for ( Re IT it = be; it != ed; ++it ) if ( it->val ) ans += (it->r) - (it->l) + 1;    return ans;}

1. 查询最长连续1的个数

还是暴力

inline int Get2( Re int l, Re int r ){    Re IT ed(Split(r + 1)), be(Split(l)); Re int ans(0), cur(0);    for ( Re IT it = be; it != ed; ++it )        if ( it->val ) cur += (it->r) - (it->l) + 1;        else ans = max( ans, cur ), cur = 0;    ans = max( ans, cur );    return ans;}

---

差不多就这些了。

骗分大法好啊！

完整代码()

#include
    
     using namespace std;#define Re register struct node{    int l, r; mutable bool val;    node( int L, int R = -1, int v = 0 ):l(L), r(R), val(v){}    bool operator < ( const node t )const{ return l < t.l; }};#define IT set
     
      ::iteratorset
      
        S;inline IT Split( Re int pos ){    Re IT t(S.lower_bound(node(pos)));    if ( t != S.end() && t->l == pos ) return t;    t--;    Re int L(t->l), R(t->r); Re bool v(t->val);    S.erase(t);    S.insert( node( L, pos - 1, v ) );    return S.insert( node( pos, R, v ) ).first;}inline void Assign( Re int l, Re int r, Re bool v ){    Re IT ed(Split(r + 1)), be(Split(l));    S.erase( be, ed );    S.insert(node( l, r, v ));}inline void Change( Re int l, Re int r ){    Re IT ed(Split(r + 1)), be(Split(l));    for ( Re IT it = be; it != ed; ++it ) it->val = !(it->val);}inline int Get1( Re int l, Re int r ){    Re IT ed(Split(r + 1)), be(Split(l)); Re int ans(0);    for ( Re IT it = be; it != ed; ++it ) if ( it->val ) ans += (it->r) - (it->l) + 1;    return ans;}inline int Get2( Re int l, Re int r ){    Re IT ed(Split(r + 1)), be(Split(l)); Re int ans(0), cur(0);    for ( Re IT it = be; it != ed; ++it )        if ( it->val ) cur += (it->r) - (it->l) + 1;        else ans = max( ans, cur ), cur = 0;    ans = max( ans, cur );    return ans;}int N, M, t, ls;int a[100005];int main(){    scanf( "%d%d", &N, &M ); ls = 1;     for ( Re int i = 1; i <= N; ++i ) scanf( "%d", &a[i] );    for ( Re int i = 2; i <= N; ++i ) if ( a[i] ^ a[i - 1] ) S.insert( node( ls, i - 1, a[i - 1] ) ), ls = i;    S.insert( node( ls, N, a[N] ) );    for ( Re int i = 1; i <= M; ++i ){        Re int op, a, b; scanf( "%d%d%d", &op, &a, &b ); a++; b++;        if ( op < 2 ) Assign( a, b, op );        if ( op == 2 ) Change( a, b );        if ( op == 3 ) printf( "%d\n", Get1( a, b ) );        if ( op == 4 ) printf( "%d\n", Get2( a, b ) );    }    return 0;}