珂朵莉树总结
前置知识
set
简介
~~~~ 珂朵莉树（Chtholly Tree），又名ODT。起源自 CF896C（某位毒瘤出的题目。
~~~~~~ 说是树，其实跟树没有半毛关系，只是一种暴力的数据结构（甚至都不一定可以称之为数据结构），本质是基于数据随机的「颜色段均摊」。
使用前提
~~ 保证数据随机，且拥有区间推平，否则会退化成 O(n^2) 暴力。如果满足两个条件，它的时间复杂度会趋近 O(nloglogn) ，比线段树都要快很多。但由于其特性，也会被出题人精心制作的数据卡超时（其实都不用精心制作)，因此一般用来骗分。
基本原理
~~~~ 把值相同的区间合并成一个节点保存在 set 里面。
实现
节点存储
~~~~ 我们定义一个结构体来存储每个节点，用结构体变量来表示这个节点（区间）的值。
typedef long long ll;
struct node{
int l,r;//起点和终点
mutable ll v;
node(int L,int R=0,ll V=0):l(L),r(R),v(V){}
bool operator <(const node& a)const{return l<a.l;}//按左端点排序
};
~~~~ 使用 mutable 是为了突破 const 限制，便于我们能在 set 中利用迭代器修改它。
构造珂朵莉树
set<node> chtolly;
~~~~ 就是这么简单，你得到了一个，没有初始化的珂朵莉树。
~~~~ 一般来讲，我们要向其中不断插入长度为1的节点来初始化。
for(int i=1;i<=n;i++){
cin>>a[i];
chtolly.insert(node(i,i,a[i]));
}
chtolly.insert(node(n+1,n+1,0));
~~~~ 后续需要使用迭代器，懒的话可以直接宏定义。
#define IT set<node>::iterator
核心操作
分裂（split）
~~~~ 既然需要进行区间操作，我们就把需要修改的区间拿出来，有一部分需要修改，而另一部分不需要修改，就把这个区间拆开，要修改的部分就直接改，不需要改的就蒜了（听起来就很暴力）。
~~~~ 所以 split(pos) 的操作就是把 [l,r] 分裂成 [l,pos-1],[pos,r] ，返回后者的迭代器。
IT split(int pos){ //分裂
IT it=chtolly.lower_bound(node(pos));//找到首个不小于pos的的节点
if(it !=chtolly.end()&&it->l==pos){return it;}//左端点恰好在pos,无需分裂
it--;//否则肯定在上一个结点
int l=it->l,r=it->r;
ll v=it->v;
chtolly.erase(it);//清除原节点
chtolly.insert(node(l,pos-1,v));
return chtolly.insert(node(pos,r,v)).first;
}
~~~~ 这样，如果我们要利用区间中的数据就可以这样写了。
IT itr=split(r+1),itl=split(l);
for(;itl!=itr;itl++){
//你想干的事情
}
~~~~ 重要细节：必须先声明 itr ，再声明 itl ，否则 itl 可能会因为 split 中的 erase 操作而失效并导致 RE 。
~~~~ 当然只有 split 复杂度还是得爆炸，所以接下来就是珂朵莉树最核心（玄学）的部分。
推平（assign）
~~~~ 既然一个区间的值都一样了，那么我们就可以让这个区间用一个节点表示。珂朵莉树的核心。
void assign(int l,int r,int v){//推平
IT itr=split(r+1),itl=split(l);
chtolly.erase(itl,itr);
chtolly.insert(node(l,r,v));
}
~~~~ 珂朵莉树的复杂度是由 assign 保证的。它可以让 set 大小快速下降，使珂朵莉树在随机情况下能超越线段树以及常数很大的数据结构。
其他操作
~~~~ 都是暴力了，没什么好说的。
1.区间加
~~~~ 直接加一遍就好了（比较像分块）。
void add(int l,int r,ll v){
IT itr=split(r+1),itl=split(l);
for(;itl!=itr;itl++){
itl->v+=v;
}
}
2.区间和
~~~~ 也是直接求和就好了。
ll sum(int l,int r)
{
IT itr = split(r+1),itl=split(l);
ll res=0;
for (;itl!=itr;itl++){
int L=itl->l,R=itl->r;
ll V=itl->v;
res+=(ll)(R-L+1)*V;
}
return res;
}
珂朵莉树就介绍到这里了。制作不易，喜欢的记得点个赞。
