珂朵莉树
Forward_Star
2019-09-25 17:53:03
## ~~末日三问~~
### Q:什么是珂朵莉树？
A:珂朵莉树是一种存储区间信息的数据结构；简单地说，是把整个区间划分为一个个互不相交的小区间，通过将含相同元素的区间合并为一段区间，可以提高某些询问与操作的效率。
### Q:珂朵莉树有什么用途？
A:只要是涉及到区间赋值操作的题，就可以用珂朵莉树处理几乎任何关于区间信息的询问。另外，也可以帮助我们更好的研究珂学~~（说句闲话，研究珂学的最好方式是……）~~。
### Q:什么情况下可以用珂朵莉树？
A:首先要明确的是，珂朵莉树本质上是一种暴力的算法。这很容易理解，既然她的高效建立在区间合并操作的基础上，那么如果构造一组数据使得其几乎不含区间赋值操作，区间合并派不上用场，珂朵莉树会被轻易卡掉。
因此，珂朵莉树要求题目数据具有**高度随机性**。
## 前置知识
珂朵莉树需要用到结构体和stl库的set（不知道有没有大佬会手写平衡树去代替set维护区间%%）。网上的一些详解主要是对珂朵莉树操作的解释，但却没有对于结构体和set操作的说明，对于我等蒟蒻不甚友好。
### 结构体&&珂朵莉树定义
前面说到，珂朵莉树是存储区间信息的，因此我们可以定义结构体来表示区间。
```cpp
struct node
{
int l,r; //表示区间左右端点
mutable int v; //表示该区间中每个数的值
node(int L,int R=-1,bool V=0) //这个比较玄学，大概是赋一个初值，没有的话会在后续求lower_bound（某个set操作）时编译错误
{
l=L;
r=R;
v=V;
};
bool operator<(const node&next) const //重载运算符
{
return l<next.l;
}
}; //注意结束的大括号后要打分号
```
结构体，可以理解为一个集合（这里仅指高一数学课本上定义的集合，不是指stl库的set）。在结构体中定义的变量就是这个集合的元素。
定义结构体后我们可以把它看作一种数据类型，直接用来定义变量。
```cpp
node a; //这样，就定义了一个数据类型为node（前文定义的结构体）的变量
a.l = 1;
a.r = 10;
a.v = 0;
//调用结构体内某个变量时，只需要"a.(结构体内变量名)"即可
```
以上是结构体的基本定义及使用。然后大家可能有疑问：为什么定义结构体内$v$的时候用了$mutable$？
这是因为在调用函数时，往往只传参，但是函数内操作不会更改其实际的值。而珂朵莉树往往涉及需要修改$v$的操作，如果是一般的数据类型，我们会在变量前加上&，但对于结构体，就需要在定义时加上$mutable$。
可能稍有难度的是结构体内的重载运算符，这是因为结构体内涉及到几个元素，所以一般的运算符是不能直接用于结构体之间的运算或比较的。重载运算符相当于给运算符“设定规则”，比如对于我们上文定义的$node$，重载运算符后两个$node$类型之间的$<$就是只比较其$l$的大小了。
### stl::set的一些操作
以下是珂朵莉树需要用到的一些set操作：
1、定义set：
```cpp
#include<set>
set<node> Chtholly_tree;
```
需要用到头文件set，将某个变量定义为set的语句为"set<set存放数据类型> 变量名"。对于珂朵莉树，我们要定义一个存放$node$($node$定义见前文)的set。
2、插入(insert)：
set也可以看成一个集合，不过它支持多种操作而且有序。既然是集合，那它肯定不止一个元素，因此不需要再套上一个数组。
加入元素可以用一行代码解决：
```cpp
Chtholly_tree.insert(node(l,r,v));
```
这样就可以插入一个区间，由于重载运算符后$<$号是比较区间左端点大小，所以set中的区间是从左到右排列的。
3、删除(erase)：
删除操作有两种：
```cpp
Chtholly_tree.erase(it); //删除it指代的区间
Chtholly_tree.erase(left,right); //删除left到right（不包含right）之间的所有区间
```
其中$it,left,right$都是迭代器，可以指代set中的元素；它大致类似于数组的下标，在珂朵莉树中迭代器用于指代区间。
获取迭代器的信息可以用"->"，比如：
```cpp
it->l //区间左端点
it->r //区间右端点
it->v //区间中数字的值
```
4、lower_bound：
学过平衡树（或者微积分）的同学应该很清楚这个概念：这是指大于等于某个数的所有数中最小的数。
那么要查找左端点离$pos$最近的区间，我们就可以用下面这一行代码解决：
```
Chtholly_tree.lower_bound(node(pos));
```
它返回的是一个迭代器，指代对应的区间。
## 珂朵莉树的实现
明白了上述的操作之后，珂朵莉树的实现就非常简单了。
珂朵莉树有两个关键操作：split和assign_val。
### split
$split(pos)$将返回一个左端点为$pos$的迭代器（区间）。
但是set中并不一定有现成左端点为$pos$的区间，所以顾名思义，我们把左端点最接近$pos$的区间$split$（分裂）一下，分成$[l,pos-1],[pos,r]$两部分，其中$l,r$分别是该区间左、右端点。然后，返回$[pos,r]$的那段区间。
```cpp
set<node>::iterator split(int pos)
{
set<node>::iterator it=Chtholly_tree.lower_bound(node(pos)); //见上述set操作，此为查找离左端点pos最近且大于pos的区间
if (it!=Chtholly_tree.end()&&it->l==pos) return it; //如果有现成左端点为pos的区间则直接返回
it--; //因为找到的区间在pos右边，所以取上一个区间
int left=it->l;
int right=it->r;
int temp=it->v;
Chtholly_tree.erase(it);
Chtholly_tree.insert(node(left,pos-1,temp));
return Chtholly_tree.insert(node(pos,right,temp)).first;
}
```
### assign_val
这个操作叫区间推平，和$split$相反，它并不是要分裂某个区间而是要把某几个区间合并，主要用于区间赋值。
```cpp
void assign_val(int l,int r,int temp)
{
set<node>::iterator itr=split(r+1); //+1的原因是使得分裂后得到两个区间中左边的区间右端点能刚好取到r
set<node>::iterator itl=split(l); //先分裂最右边的区间，再分裂左边区间是防止分裂完左边区间后得到的区间包含右端点r，从而分裂右区间时该区间被再一次分裂
Chtholly_tree.erase(itl,itr); //相当于把[l,r]段清空
Chtholly_tree.insert(node(l,r,temp)); //然后重新插入[l,r]段，实现区间赋值
}
```
## 完整地写出珂朵莉树
珂朵莉树思想并不复杂，但是对于初学者而言可能会被其各种set的操作绕晕。
下面我们通过[一道例题](https://www.luogu.org/problem/CF915E),来尝试写一下珂朵莉树的代码。
题目的操作无非就是把一段区间全部变为工作日或非工作日，那么我们可以用bool类型，0表示非工作日，1表示工作日，然后利用珂朵莉树的assign_val进行区间赋值即可。
那么，首先定义珂朵莉树，写好split,assign_val，然后对于每个操作，执行assign(l,r,k-1).
只需要复制一下上面的代码，再加上几行代码统计一下工作日，就可以拼成一个正解，很简单吧！
```cpp
#include<cstdio>
#include<set>
using namespace std;
struct node
{
int l,r;
mutable bool v;
node(int L,int R = -1,bool V = 0)
{
l = L;
r = R;
v = V;
}
bool operator <(const node&next) const
{
return l < next.l;
}
};
set<node> Chtholly_tree;
int n,q,ans;
set<node>::iterator split(int pos)
{
set<node>::iterator it = Chtholly_tree.lower_bound(node(pos));
if (it != Chtholly_tree.end() && it->l == pos) return it;
it --;
int l = it->l;
int r = it->r;
int v = it->v;
Chtholly_tree.erase(it);
Chtholly_tree.insert(node(l,pos-1,v));
return Chtholly_tree.insert(node(pos,r,v)).first;
}
void assign_val(int l,int r,int temp)
{
set<node>::iterator itr = split(r+1);
set<node>::iterator itl = split(l);
set<node>::iterator it = itl;
for (;it != itr;it ++)
ans -= it->v * (it->r-it->l+1);
Chtholly_tree.erase(itl,itr);
Chtholly_tree.insert(node(l,r,temp));
ans += (r - l + 1) * temp;
}
int main()
{
scanf("%d%d",&n,&q);
ans = n;
Chtholly_tree.insert(node(1,n,1));
for (int i = 1;i <= q;i ++)
{
int l,r,k;
scanf("%d%d%d",&l,&r,&k);
assign_val(l,r,k-1);
printf("%d\n",ans);
}
return 0;
}
```
## 总结
最后的最后，还是提醒大家一点：珂朵莉树终究只是暴力！除了区间推平操作可以在随机数据下保证她的高效性，其它操作都是用最简单粗暴的方法实现的。所以，在欣赏她的这种暴力美学的同时，也不要过分依赖珂朵莉树。