珂朵莉树模板题。
一、什么是珂朵莉树
珂朵莉树，又称Old Driver Tree(ODT)。是一种基于std::set的暴力数据结构。B站上有UESTC的讲解视频。
二、什么时候用珂朵莉树
关键操作：推平一段区间，使一整段区间内的东西变得一样。保证数据随机。
就像这道题。
操作：
1. 区间加
2. **区间赋值**
3. 区间第k小
4. 求区间幂次和
**数据随机**，时限2s。
## 三、珂朵莉树的初始化
这道题里，这样定义珂朵莉树的节点：
```
struct node
{
int l,r;
mutable LL v;
node(int L, int R=-1, LL V=0):l(L), r(R), v(V) {}
bool operator<(const node& o) const
{
return l < o.l;
}
};
```
这样的一个节点表示$[l,r]$内的所有数都是v。需要注意的是```mutable```，意为易变的，不定的。它对```v```的修饰，使得我们可以在```add```操作中修改```v```的值。没有它的修饰会在```add```函数里导致CE。
我们把节点存在```set```里。
```
set<node> s;
```
像CF896C这道题就这样初始化。
```
cin>>n>>m>>seed>>vmax;
for (int i=1; i<=n; ++i)
{
a[i] = (rnd() % vmax) + 1;
s.insert(node(i,i,a[i]));
}
```
初始化完了？初始化完了。
## 四、珂朵莉树的核心操作：split
```split(pos)```操作是指将原来含有pos位置的节点分成两部分：$[l,pos-1]$和$[pos,r]$。
看这个操作的代码：
```
#define IT set<node>::iterator
IT split(int pos)
{
IT it = s.lower_bound(node(pos));
if (it != s.end() && it->l == pos) return it;
--it;
int L = it->l, 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;
}
```
一行一行来看。
```
#define IT set<node>::iterator
```
宏定义没什么好说的，记住NOI系列赛事不能用```auto```。```auto```一时爽，评测火葬场。
```
IT it = s.lower_bound(node(pos));
```
找到首个$l$不小于pos的节点。
```
if (it != s.end() && it->l == pos)
return it;
```
如果无需```split```，直接返回。
```
--it;
```
否则pos一定在前一个区间中。
```
int L = it->l, R = it->r;
```
$[L,R]$就是要被分割的区间。
```
LL V = it->v;
```
取出这个节点的值。
```
s.erase(it);
```
删除原节点。
```
s.insert(node(L, pos-1, V));
```
插入前半段。
```
return s.insert(node(pos, R, V)).first;
```
插入后半段，返回后半段的迭代器。这里利用了```pair<iterator,bool> insert (const value_type& val)```的返回值。
## 五、珂朵莉树的推平操作：assign
要是只有```split```还不得复杂度爆炸？我们需要```assign```操作迅速减小```set```的规模。
```
void assign(int l, int r, LL val=0)
{
IT itl = split(l),itr = split(r+1);
s.erase(itl, itr);
s.insert(node(l, r, val));
}
```
一些萌新可能没有见过```erase```的这种用法，你们应该学习一个。C++98中```void erase (iterator first, iterator last)```可删除$[first,last)$区间。这里就是把$[l,r+1)$内的部分推成一段。
珂朵莉树的复杂度是由```ass```♂```ign```保证的。由于数据随机，有$\frac{1}{4}$的操作为```assign```。```set```的大小快速下降，最终趋于$\log n$，使得这种看似暴力无比的数据结构复杂度接近$m\log n$。
## 六、其他操作：一个比一个暴力
区间加：
```
void add(int l, int r, LL val=1)
{
IT itl = split(l),itr = split(r+1);
for (; itl != itr; ++itl) itl->v += val;
}
```
分裂出来挨个加一下就行。
区间第k小：
```
LL rank(int l, int r, int k)
{
vector<pair<LL, int> > vp;
IT itl = split(l),itr = split(r+1);
vp.clear();
for (; itl != itr; ++itl)
vp.push_back(pair<LL,int>(itl->v, itl->r - itl->l + 1));
sort(vp.begin(), vp.end());
for (vector<pair<LL,int> >::iterator it=vp.begin();it!=vp.end();++it)
{
k -= it->second;
if (k <= 0) return it->first;
}
return -1LL;
}
```
暴力取出排序就好了，反正也没有多少段。
```
LL sum(int l, int r, int ex, int mod)
{
IT itl = split(l),itr = split(r+1);
LL res = 0;
for (; itl != itr; ++itl)
res = (res + (LL)(itl->r - itl->l + 1) * pow(itl->v, LL(ex), LL(mod))) % mod;
return res;
}
```
暴力遍历，快速幂，然后加起来。
那么，这道题就可做了。而且我们交了一发，发现这玩意跑得完全不像暴力，最慢的点是500多ms。
## 七、一些习题
UESTC的B站讲解里还有另两道题，一道是[CF915E](https://www.luogu.org/problemnew/show/CF915E)，另一道是[BZOJ4293割草](http://ruanx.pw/bzojch/p/4293.html)(权限题)。这两道题的主流做法都是线段树，珂朵莉树也可做。但珂朵莉树仍能体现出代码量较小、易查错的优势，适合作为珂朵莉树的练习题。
```
#include<cstdio>
#include<set>
#include<vector>
#include<utility>
#include<algorithm>
#define IT set<node>::iterator
using std::set;
using std::vector;
using std::pair;
typedef long long LL;
const int MOD7 = 1e9 + 7;
const int MOD9 = 1e9 + 9;
const int imax_n = 1e5 + 7;
LL pow(LL a, LL b, LL mod)
{
LL res = 1;
LL ans = a % mod;
while (b)
{
if (b&1) res = res * ans % mod;
ans = ans * ans % mod;
b>>=1;
}
return res;
}
struct node
{
int l,r;
mutable LL v;
node(int L, int R=-1, LL V=0):l(L), r(R), v(V) {}
bool operator<(const node& o) const
{
return l < o.l;
}
};
set<node> s;
IT split(int pos)
{
IT it = s.lower_bound(node(pos));
if (it != s.end() && it->l == pos) return it;
--it;
int L = it->l, 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 add(int l, int r, LL val=1)
{
IT itl = split(l),itr = split(r+1);
for (; itl != itr; ++itl) itl->v += val;
}
void assign_val(int l, int r, LL val=0)
{
IT itl = split(l),itr = split(r+1);
s.erase(itl, itr);
s.insert(node(l, r, val));
}
LL rank(int l, int r, int k)
{
vector<pair<LL, int> > vp;
IT itl = split(l),itr = split(r+1);
vp.clear();
for (; itl != itr; ++itl)
vp.push_back(pair<LL,int>(itl->v, itl->r - itl->l + 1));
std::sort(vp.begin(), vp.end());
for (vector<pair<LL,int> >::iterator it=vp.begin();it!=vp.end();++it)
{
k -= it->second;
if (k <= 0) return it->first;
}
return -1LL;
}
LL sum(int l, int r, int ex, int mod)
{
IT itl = split(l),itr = split(r+1);
LL res = 0;
for (; itl != itr; ++itl)
res = (res + (LL)(itl->r - itl->l + 1) * pow(itl->v, LL(ex), LL(mod))) % mod;
return res;
}
int n, m;
LL seed, vmax;
LL rnd()
{
LL ret = seed;
seed = (seed * 7 + 13) % MOD7;
return ret;
}
LL a[imax_n];
int main()
{
scanf("%d %d %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]));
}
s.insert(node(n+1, n+1, 0));
int lines = 0;
for (int i =1; i <= m; ++i)
{
int op = int(rnd() % 4) + 1;
int l = int(rnd() % n) + 1;
int r = int(rnd() % n) + 1;
if (l > r)
std::swap(l,r);
int x, y;
if (op == 3)
x = int(rnd() % (r-l+1)) + 1;
else
x = int(rnd() % vmax) +1;
if (op == 4)
y = int(rnd() % vmax) + 1;
if (op == 1)
add(l, r, LL(x));
else if (op == 2)
assign_val(l, r, LL(x));
else if (op == 3)
printf("%lld\n",rank(l, r, x));
else
printf("%lld\n",sum(l, r, x, y));
}
return 0;
}
```