简介
珂朵莉树，又名老司机树（Old Driver Tree）。珂朵莉树起源于 Codeforces 的一场比赛 CF896C。
这种想法的本质是基于数据随机的「颜色段均摊」，而不是一种数据结构。 ——OI Wiki
珂朵莉树本质上并不能算一种数据结构，仅仅只能算一种思想。并且其适用范围较为有限，只能适用于以下情况：维护一个序列，数据随机，只有区间赋值操作。
在数据随机的情况下一般效率较高，但数据不随机时，就容易被卡。在只有区间赋值操作的数据结构题可以拿来骗分，数据弱一点的题甚至能 AC。
数据随机时，用set实现的珂朵莉树复杂度为 $O(n\;log\;log\;n)$ ，而链表实现的复杂度为 $O(n\;log\;n)$ 。（珂朵莉树严格证明可参考这篇）
原理其实很简单，甚至看代码都能看懂，这里一句话带过：维护若干个区间，将值相同的区间合并为一个，这样区间总数就能减少。
而这里讲点不一样的，本文重点介绍一下map实现的珂朵莉树（是我的一位学长教我的orz），用的人相对较少，其代码实现相比set实现的也更简单。
正文
struct node{
int l,r;
mutable ll v;
node(int l,int r,ll v): l(l),r(r),v(v){}
bool operator<(const node &x)const{return l<x.l;}
};这是set实现的ODT保存节点的方式，它保存了区间左右端点和区间的值，但实际上区间右端点是没必要保存的，因为我们可以直接从下一个区间的左端点推出当前区间的右端点，这样我们就能少维护一个信息，就可以直接用一个map存了。
同时，在工程上，都习惯用左闭右开的区间和下标从0开始，这里借鉴一下，这样下一个区间的左端点就正好对应当前区间的右端点了。
要注意最后一个区间没有后继，为了获取最后一个区间的右端点，在map结尾插入一个 $[n,+\infty)$ 的区间就可以了。
这样做为什么更好呢？
set实现的 split：
auto split(int pos){
auto it=lower_bound(s.begin(),s.end(),(node){pos,0,0});
if(it!=s.end() and it->l==pos)
return it;
it--;
if(it->r<pos)return s.end();
int l=it->l;
int r=it->r;
ll v=it->v;
s.erase(it);
s.insert(node(l,pos-1,v));
return s.insert(node(pos,r,v)).first;
}举个例子，如果我们想把元素都一样的一个区间 $[l,r]$ 从下标 $p$ 处劈开，按照上面的写法，需要先把这个区间删掉，再加入两个值一样但范围分别为 $[l,p-1]$ 和 $[p,r]$ 的区间，原因是我们把区间劈开后要修改两个区间的左右端点，有点麻烦，这不好。
但如果不存右端点，就只需要在这个区间后面插入一个从 $p$ 开始区间就可以了，这很好。因为每个区间的右端点都是由下一个区间左端点决定的，也就不需要对原来的区间做修改了。
map实现的 split：
auto split(int l){
auto it = mp.lower_bound(l);
if (it->first == l)
return it;
it--;
return mp.insert({l, it->second}).first;
}可以发现，码量减少了很多。
CF896C代码实现
这里给出了模板题的两种代码实现方式，以供参照和对比 （set实现的懒得封装了）。
map实现：
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn = 100005;
ll n, m, seed, vmax;
ll a[maxn];
ll qpow(ll a, ll b, ll p)
{
ll res = 1;
a %= p;
while (b)
{
if (b & 1)
res = res * a % p;
b >>= 1;
a = a * a % p;
}
return res;
}
struct ODT
{
map<int, ll> mp;
ODT(int size)
{
mp[size] = 0LL;
for(int i=0;i<n;i++){
mp[i]=a[i];
}
}
auto split(int l)
{
auto it = mp.lower_bound(l);
if (it->first == l)
return it;
it--;
return mp.insert({l, it->second}).first;
}
void assign(int l, int r, ll v)
{
mp.erase(split(l), split(r));
mp[l] = v;
}
void add(int l, int r, ll v)
{
for (auto i = split(l), end = split(r); i != end; i++)
i->second += v;
}
ll kth(int l, int r, int k)
{
map<ll, int> mp;
for (auto i = split(l), end = split(r); i != end; i++)
mp[i->second] += (next(i)->first - i->first);
for (auto i : mp)
{
k -= i.second;
if (k < 0)
return i.first;
}
return 114514;
}
ll pow(int l, int r, int x, int p)
{
ll result = 0;
for (auto i = split(l), end = split(r); i != end; i++)
result = (result + (ll)(next(i)->first - i->first) * qpow(i->second, x, p)) % p;
return result;
}
};
ll rnd()
{
ll ret = seed;
seed = (seed * 7 + 13) % 1000000007;
return ret;
}
int main()
{
ios::sync_with_stdio(0);
cin >> n >> m >> seed >> vmax;
for (int i = 1; i <= n; i++)
a[i - 1] = (rnd() % vmax) + 1;
ODT odt(n);
for (int i = 1; i <= m; i++)
{
int opt = rnd() % 4 + 1;
int l = rnd() % n + 1;
int r = rnd() % n + 1;
if (l > r)
swap(l, r);
ll x, y;
if (opt == 3)
x = rnd() % (r - l + 1) + 1;
else
x = rnd() % vmax + 1;
if (opt == 4)
y = rnd() % vmax + 1;
l--;
if (opt == 1)
{
odt.add(l, r, x);
}
else if (opt == 2)
{
odt.assign(l, r, x);
}
else if (opt == 3)
{
cout << odt.kth(l, r, x - 1) << '\n';
}
else
{
cout << odt.pow(l, r, x, y) << '\n';
}
}
return 0;
}set实现：
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn = 100005;
ll n, m, seed, vmax;
ll a[maxn];
struct node
{
int l, r;
mutable ll v;
node(int l, int r, ll v) : l(l), r(r), v(v) {}
bool operator<(const node &x) const
{
return l < x.l;
}
};
set<node> s;
auto split(int pos)
{
auto it = lower_bound(s.begin(), s.end(), (node){pos, 0, 0});
if (it != s.end() and it->l == pos)
{
return it;
}
it--;
if (it->r < pos)
return s.end();
int l = it->l;
int r = it->r;
ll v = it->v;
s.erase(it);
s.insert(node(l, pos - 1, v));
return s.insert(node(pos, r, v)).first;
}
void assign(int l, int r, ll x)
{
auto itr = split(r + 1), itl = split(l);
s.erase(itl, itr);
s.insert(node(l, r, x));
}
void add(int l, int r, ll x)
{
auto itr = split(r + 1), itl = split(l);
for (auto it = itl; it != itr; it++)
{
it->v += x;
}
}
struct rnk
{
ll num;
int len;
rnk(ll num, int len) : num(num), len(len) {}
bool operator<(const rnk &x) const
{
return num < x.num;
}
};
ll kth(int l, int r, ll x)
{
auto itr = split(r + 1), itl = split(l);
vector<rnk> p;
for (auto it = itl; it != itr; it++)
{
p.push_back(rnk(it->v, it->r - it->l + 1));
}
sort(p.begin(), p.end());
int i = 0;
for (; i < p.size(); i++)
{
if (p[i].len < x)
{
x -= p[i].len;
}
else
break;
}
return p[i].num;
}
ll qpow(ll a, ll b, ll p)
{
ll res = 1;
a %= p;
while (b)
{
if (b & 1)
res = res * a % p;
b >>= 1;
a = a * a % p;
}
return res;
}
ll calc(int l, int r, ll k, ll p)
{
auto itr = split(r + 1), itl = split(l);
ll ans = 0;
for (auto it = itl; it != itr; it++)
{
ans = (ans + qpow(it->v, k, p) % p * (it->r - it->l + 1) % p) % p;
}
return ans;
}
ll rnd()
{
ll ret = seed;
seed = (seed * 7 + 13) % 1000000007;
return ret;
}
int main()
{
ios::sync_with_stdio(0);
cin >> 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; i <= m; i++)
{
int opt = rnd() % 4 + 1;
int l = rnd() % n + 1;
int r = rnd() % n + 1;
if (l > r)
swap(l, r);
ll x, y;
if (opt == 3)
x = rnd() % (r - l + 1) + 1;
else
x = rnd() % vmax + 1;
if (opt == 4)
y = rnd() % vmax + 1;
if (opt == 1)
{
add(l, r, x);
}
else if (opt == 2)
{
assign(l, r, x);
}
else if (opt == 3)
{
cout << kth(l, r, x) << endl;
}
else
{
cout << calc(l, r, x, y) << endl;
}
}
return 0;
}