前言 珂朵莉树Old Driver Tree (ODT) 是一种十分暴力的数据结构。珂朵莉树是一场 CF 比赛中提出的数据结构，因那道题题面（CF896C）关于珂朵莉而得名。 珂朵莉树适用于以下的情况：维护一个序列，有区间赋值操作，数据随机。下面是珂朵莉树板子题： 维护一个序列，需要支持以下操作 1. 将 $[l,r]$ 区间所有数加上 $x$ 2. 将 $[l,r]$ 区间所有数改成 $x$ 3. 求 $[l,r]$ 区间第 $k$ 小 4. 求 $[l,r]$ 区间每个数字的 $x$ 次方的和模 $y$ 的值 (即 $\left(\sum_{i=l}^{r} a_{i}^{x}\right) \bmod y$) – CF896C Willem, Chtholly and Seniorious 支持的操作还可以有很多，只要暴力能做珂朵莉树一般都可以做。 珂朵莉树的思想是维护一堆区间，合并相同值的区间，这样区间总数就可以减少。 珂朵莉树非常依赖区间赋值操作，如果区间赋值操作很少或者区间赋值的区间都较短，那么珂朵莉树和暴力就没什么区别了。 显然，要卡珂朵莉树非常容易。但对于数据完全随机的情况，珂朵莉树就可以跑得飞快。有很多题可以用珂朵莉树水过，甚至比正解还快。 思路 珂朵莉树维护了很多区间。 一个区间表示一段相同的数。一个区间 $(l,r,num)$ 表示从左端点 $l$ 到右端点 $r$，中间的数字全部为 $num$。 例如 $1,2,3,3,3,4,4,5$ 可以用 $5$ 个区间来表示：$(1,1,1)(2,2,2)(3,5,3)(6,7,4)(8,8,5)$。 区间赋值的时候，我们可以删去一些区间并用一个大区间代替它们，区间数量就少了很多。 而查询只需要找出相应的区间，然后暴力统计即可。 如果某次操作的边界在某个区间的中心，那么将这个区间断开即可。 我们用 set 维护区间左端点位置的值，使区间始终保持有序。 区间结构体定义 struct node { long long l,r; mutable long long num; bool operator<(const node y) const { return l<y.l; } }; Split Split 操作用来将一个区间断开。 set<node>::iterator split(long long x) { node tmp={x}; set<node>::iterator it=s.lower_bound(tmp); if(it!=s.end()&&it->l==x) { return it; } it--; long long l=it->l,r=it->r,num=it->num; s.erase(it); tmp={l,x-1,num}; s.insert(tmp); tmp={x,r,num}; return s.insert(tmp).first; } 区间赋值操作 (Assign) 删除该区间所覆盖的所有小区间，并插入一个大区间来代替它们。 void assign(long long l,long long r,long long x) { set<node>::iterator R=split(r+1); set<node>::iterator L=split(l); s.erase(L,R); node tmp={l,r,x}; s.insert(tmp); } 查询操作 就是暴力，找出相应区间并暴力统计 区间和 long long query_sum(long long l,long long r) { set<node>::iterator R=split(r+1),L=split(l); long long ans=0; while (L!=R) { ans+=L->num*(L->r-L->l+1); //遍历求和 ans%=y; L++; } return ans; } 区间 x 次方和 和求和一样，只是改成快速幂 long long query_pow_sum(long long l,long long…