好久没写学习笔记了啊……
珂朵莉树
模板：CF896C Willem, Chtholly and Seniorious。
题意：
- 给定一个序列，支持区间加，区间赋值，询问区间第 $k$ 小，区间幂次和（即 $x$ 次方的和，取模）。
- 数据范围 $10^5$，数据随机。
珂朵莉树（Chtholly Tree），又称 ODT（Old Driver Tree），是一种暴力数据结构，其复杂度正确一般仅限于：存在区间赋值操作（常称为区间推平，即将一个区间的数变为同一个）且数据随机。
基本结构
珂朵莉树用将整个序列分为若干个区间，用 $l,r,v$ 来记录一个值均为 $v$ 的区间 $[l,r]$。
struct node{
int l,r;
mutable int v;
node(int l,int r=0,int v=0):l(l),r(r),v(v){};
bool operator <(const node &a)const{
return l<a.l;//按左端点排序存放在 set 中
}
};
set<node> s;
我们将这些区间存放在一个 set 中，由于该 set 中的某个元素的 $v$ 可能会被修改，因此 mutable 必不可少。
刚开始时 set 中为 $n$ 个长度为 $1$ 的段。
分裂操作 split
分裂操作是珂朵莉树的核心，对于一个区间 $[l,r]$，我们给定一个值 $pos$，需要将其拆分为 $[l,pos-1]$ 和 $[pos,r]$ 两个区间。
本文中我直接使用了
auto，但如果在较低的 c++ 版本（如 c++98），需要将auto改为set<node>::iterator。
auto split(int pos){
auto it=s.lower_bound(node(pos));
if(it!=s.end()&&it->l==pos) return it;
it--;if(it->r<pos) return s.end();
int l=it->l,r=it->r,v=it->v;
s.erase(it);
s.insert(node(l,pos-1,v));
return s.insert(node(pos,r,v)).first;
}
对于分裂操作，我们先找到 $pos$ 对应的区间。使用 lower_bound 找到一个区间后，若该区间的开头即为 $pos$，那么无需分裂，直接返回。反之，$it$ 往前一个位置就是 $pos$ 所在的区间。同时，若 $pos=n+1$（该情况见后文），我们判断一下返回即可（即第三行）。
接着，我们只需要将原来那个区间删除，并将两个新区间分别插入即可。
由于 insert 函数的返回的是一个 pair 且其 first 就为迭代器，我们可以直接如最后一行一样返回 $pos$ 所在区间的迭代器。
推平操作 assign
随机的推平操作是保证复杂度的关键。
inline void assign(int l,int r,int k){
auto itr=split(r+1),itl=split(l);
s.erase(itl,itr);s.insert(node(l,r,k));
}
我们只需要找到 $l$ 和 $r+1$ 所在的区间，将之间的区间全部删除，插入一个新区间即可。
在数据随机时，随机的 assign 操作能够使区间数趋近于 $\log n$ 并保持稳定，因此复杂度为 $O(m\log n)$。
详细证明见 Blaze 的博客。
其他操作
区间加 add
inline void add(int l,int r,int k){
auto itr=split(r+1),itl=split(l);
for(auto it=itl;it!=itr;it++) it->v+=k;
}
找到两端所在区间，暴力加即可。
区间第 $k$ 小
inline int getrank(int l,int r,int k){
vector<pair<int,int>> vec;//vec.clear();
auto itr=split(r+1),itl=split(l);
for(auto it=itl;it!=itr;it++)
vec.push_back(mk(it->v,it->r-it->l+1));
sort(vec.begin(),vec.end());
for(auto it=vec.begin();it!=vec.end();it++){
k-=it->second;
if(k<=0) return it->first;
}
return 114514;
}
用 vector 把所有区间排一下序，暴力找即可。
区间幂次和
inline int getpow(int l,int r,int k,int p){
auto itr=split(r+1),itl=split(l);
int ret=0;
for(auto it=itl;it!=itr;it++)
ret=(ret+(it->r-it->l+1)%p*ksm(it->v,k,p)%p)%p;//ksm 为快速幂
return ret;
}
同理。
容易发现除了 split，其他操作都是极其暴力的，复杂度全靠随机的 assign 来保证。因此，珂朵莉树的使用范围还是比较狭窄的。
一道例题
CF453E Little Pony and Lord Tirek。
题意：
- 你有 $n$ 只小马（编号从 $1$ 到 $n$）。每只小马有三种属性。
- $s_i$：时间为 $0$ 时这只小马拥有的法力值。
- $m_i$：这只小马可以拥有的最大法力值。
- $k_i$：这只小马单位时间内回复的法力值。
- 提雷克会给出 $m$ 条指令，每一条都可以被描述为 $3$ 个整数：$t_i, l_i, r_i$。表示在时间为 $t_i$ 时，提雷克会从区间 $[l_i,r_i]$ 的小马中吸取其所有法力，指令保证 $t$ 升序，计算每一条指令之后提雷克可以吸取多少点法力。
首先考虑一个子问题。若每次操作都针对整个序列且所有小马初始法力为 $0$，我们可以对于所有小马对于 $\frac{m_i}{k_i}$ 从小到大排序，我们发现对于每个时间，一定有一个前缀的答案为 $\sum m_i$，后缀的答案为 $\sum k_i \times \Delta t$（$\Delta t$ 为时间差）。
再回到这个问题，我们发现其所有操作都为推平操作（吸走所有魔力），那么我们考虑对于一个区间 $[l,r]$，该区间内所有小马都在 $v$ 时间法力值归零，并一直增长到当前时间的，发现这种区间可以用珂朵莉树维护，并且可以用上述方法计算贡献。具体的，我们将所有小马排序后一头一头加入主席树中（已加入的小马对于答案的贡献为 $m_i$，还没加入的贡献为 $k_i\times \Delta t$），然后对于一个区间，我们计算出其与询问时间的时间差，再二分找到该时间差对应哪一时刻的主席树，然后查询该区间的贡献即可。由于问题中仅存在推平操作，复杂度一定是正确的。
如果对于代码或具体实现有疑惑，可以查看文章开头给出的 Leap_Frog 的博客链接。
完整代码（CF896C）
#include<bits/stdc++.h>
#define IT set<node>::iterator
#define int long long
#define mk make_pair
using namespace std;
const int N=1e5+5;
const int mod=1e9+7;
int n,m,seed,vmax;
inline int rnd(){
int ret=seed;
seed=(seed*7+13)%mod;
return ret;
}
struct node{
int l,r;
mutable int v;
node(int l,int r=0,int v=0):l(l),r(r),v(v){};
bool operator <(const node &a)const{
return l<a.l;
}
};
set<node> s;
auto split(int pos){
auto it=s.lower_bound(node(pos));
if(it!=s.end()&&it->l==pos) return it;
it--;if(it->r<pos) return s.end();
int l=it->l,r=it->r,v=it->v;
s.erase(it);
s.insert(node(l,pos-1,v));
return s.insert(node(pos,r,v)).first;
}
inline void add(int l,int r,int k){
auto itr=split(r+1),itl=split(l);
for(auto it=itl;it!=itr;it++) it->v+=k;
}
inline void assign(int l,int r,int k){
auto itr=split(r+1),itl=split(l);
s.erase(itl,itr);s.insert(node(l,r,k));
}
inline int getrank(int l,int r,int k){
vector<pair<int,int>> vec;//vec.clear();
auto itr=split(r+1),itl=split(l);
for(auto it=itl;it!=itr;it++)
vec.push_back(mk(it->v,it->r-it->l+1));
sort(vec.begin(),vec.end());
for(auto it=vec.begin();it!=vec.end();it++){
k-=it->second;
if(k<=0) return it->first;
}
return 114514;
}
inline int ksm(int a,int b,int p){
a%=p;
int ret=1;
while(b){
if(b&1) ret=ret*a%p;
a=a*a%p;
b>>=1;
}
return ret;
}
inline int getpow(int l,int r,int k,int p){
auto itr=split(r+1),itl=split(l);
int ret=0;
for(auto it=itl;it!=itr;it++)
ret=(ret+(it->r-it->l+1)%p*ksm(it->v,k,p)%p)%p;
return ret;
}
int a[N];
signed main(){
scanf("%lld%lld%lld%lld",&n,&m,&seed,&vmax);
for(int i=1;i<=n;i++){
a[i]=(rnd()%vmax)+1;
s.insert(node(i,i,a[i]));
}
for(int i=1,op,l,r,x,y;i<=m;i++){
op=(rnd()%4)+1;
l=(rnd()%n)+1;
r=(rnd()%n)+1;
if(l>r) swap(l,r);
if(op==3) x=(rnd()%(r-l+1))+1;
else x=(rnd()%vmax)+1;
if(op==4) y=(rnd()%vmax)+1;
if(op==1) add(l,r,x);
else if(op==2) assign(l,r,x);
else if(op==3) printf("%lld\n",getrank(l,r,x));
else printf("%lld\n",getpow(l,r,x,y));
}
return 0;
}