「学习笔记」珂朵莉树 ODT

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

「学习笔记」珂朵莉树 ODT-LMLPHP

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

没错，珂朵莉树来自Codeforces 896C C. Willem, Chtholly and Seniorious

国外珂学家滑稽）

前置芝士：

set的基本操作

迭代器（跟指针差不多

重载运算符、构造函数的简单了解

mutable（下面也会讲

暴力枚举

常数优化（inline O2 O3 register大法好啊

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

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

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

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

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

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

这里我们以P2572 [SCOI2010]序列操作为例，讲一讲珂朵莉树。

先写个结构体。

#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，否则还要删除元素，再插入进去，降低了效率。因为珂朵莉树比较暴力，我们要尽可能优化复杂度。

建立你的珂朵莉树

	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顺序

炒鸡简单对吧？

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]的迭代器

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]

然后如果调用了be

be原指向的区间[2,3]已经被删除了

然后RE*8+TLE*1+AC*1

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

区间取反

暴力枚举即可（也要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的个数

也很暴力，一个个枚举

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的个数

还是暴力

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;

}

差不多就这些了。

骗分大法好啊！

完整代码(https://www.luogu.org/problemnew/show/P2572)

#include<bits/stdc++.h>

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<node>::iterator

set<node> 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;

}