珂朵莉树（老司机树，ODT，颜色段均摊）

前言

在宿舍里有人说珂朵莉树写起来比shi山线段树方便多了。
正文

珂朵莉树，又名老司机树，颜色段均摊，ODT。
可以在数据完全随机化的情况下较快的完成一些操作（所以容易被卡）。
珂朵莉树其实形态并不像树，基于set或是链表，是一种很暴力的数据结构。
先来看一到例题（珂朵莉树起源题）
CF896C
题目大意：
有一个序列,你需要编写程序支持以下操作：
1 l r x ：将[l,r]区间所有数加上x
2 l r x ：将[l,r]区间所有数改成x
3 l r x ：输出将[l,r] 区间从小到大排序后的第x个数是的多少
4 l r x y ：输出[l,r] 区间每个数字的x次方的和模y的值
天哪线段树直接报废
进入正题：
珂朵莉树的每个节点由一个三元组组成 \((l,r,val)\) 表示从 \(l \sim r\) 这段区间中的值都是 \(val\)。
例如：
\(1,1,3,3,3,3,2,2,2,1,1,1\)，构造时长这样：
\((1,2,1),(3,6,3),(7,9,2),(10,12,1)\)
珂朵莉树中的点按 \(l\) 排序。
操作1：
例如我想让 \(2 \sim 11\) 中的数 \(+1\)
但是：这并不是几个整个节点，所以我们需要拆点。
核心：区间分割

现在我们可以将 \((1,2,1)\) 变为 \((1,1,1)\) 和 \((2,2,1)\)，将 \((10,12,1)\) 变为 \((10,11,1)\) 和 \((12,12,1)\)。
接着我们就可以将 \((2,2,1),(3,6,3),(7,9,2),(10,11,1)\) 中的 \(val\) 都 \(+1\)
所以我们将 split(x) 定义为找到 \(x\) 所在的区间 \((l,r,val)\) 将其分为 \((l,x-1,val)\) 和 \((x,r,val)\) 并返回 \((x,r,val)\) 的迭代器。
代码：

点击查看代码

1. struct node{
2.         int l,r;
3.         mutable int v;//mutalbe  可变，可以修改此值，一定要加，不然无法修改v
4.         bool operator < (const node&W)const
5.         {
6.                 return l<W.l;
7.         }
8. };
9. set<node> tree;
10. auto split(int x)
11. {
12.         auto it=tree.lower_bound({x,0,0});
13.         if(it!=tree.end()&&it->l == x)
14.         {
15.                 return it;
16.         }
17.         it--;
18.         int l=it->l,r=it->r,v=it->v;
19.         tree.erase(it);
20.         tree.insert({l,x-1,v});
21.         return tree.insert({x,r,v}).first;
22. }

复制代码

核心：区间推平

这个很好办，直接看代码：
点击查看代码

1. void assign(int l,int r,int v)
2. {
3.         auto itr=split(r+1),itl=split(l);
4.         tree.erase(itl,itr);//erase 左闭又开
5.         tree.insert({l,r,v});
6. }

复制代码

注意：

一定要先进行split(r+1)在进行split(l) 否则会RE
例如 \((1,4,1),l=1,r=2\)
若先进行split(l):
itl=(1,4,1)的迭代器
split(r+1)
此时 \((1,4,1)\) 会被分裂成 \((1,2,1)\) 和 \((3,4,1)\)
此时的 \((1,4,1)\) 已经被删掉了，所以 \(itl\) 就是一个野指针，遍历时会出问题。
add操作

解决了问题，add操作就很好写。
点击查看代码

1. void add(int l,int r,int v)
2. {
3.   auto itr=split(r+1),itl=split(l+1);
4.   for(auto it=itl;it!=itr;it++)
5.   {
6.     it->v+=v;
7.   }
8. }

复制代码

别的也是类似于这样。
珂朵莉树的总代码（核心部分）
点击查看代码[code]struct node{        int l,r;        mutable int v;//mutalbe  可变，可以修改此值        bool operator < (const node&W)const        {                return ll == x)        {                return it;        }        it--;        int l=it->l,r=it->r,v=it->v;        tree.erase(it);        tree.insert({l,x-1,v});        return tree.insert({x,r,v}).first;}void assign(int l,int r,int v){        auto itr=split(r+1),itl=split(l);        tree.erase(itl,itr);        tree.insert({l,r,v});}void build(int l,int r,int *a){        tree.clear();        int pos=l;        for(int i=l+1;i