介绍
珂朵莉树，学名珂朵莉树，又学名老司机树（ $ ODT $ ），常用来解决“区间推平”（把区间改为某一个数）等的操作，只适用于随机数据，可以定向卡掉；
其实这玩意就是暴力，没啥可说的，分块都比不上她暴力；
但人家毕竟是她，所以对于一些题还是有用的；
实现
只要你会 $ C++ \ STL $ 里的 $ set $，搞定她完全不是问题；
当然，你还需要一些基本的指针操作；
主要思想：维护一段序列的所有连续的子区间（这里的“连续”指的是值连续）；
对于 $ set $ 里的每一个元素，其为三元组，记录 $ l, r, v $，分别代表本段连续区间的左端点，右端点，值；
当然，$ set $ 中的元素是按 $ l $ 升序排列的；
声明：
struct sss{
long long l, r;
mutable long long v;
bool operator <(const sss &A) const {
return l < A.l;
}
};
操作一 spilt
分裂操作，即指定一个 $ pos $，将整个序列分成两部分；
显然，最多只会对一个子区间进行操作；
借助 $ set $ 中的 $ lower \ bound $ 函数，我们可以快速查找出 $ pos $ 在哪个子区间里，此时会有这么几种情况：
- 此区间的 $ l = pos $；
直接返回此区间即可；
- 此区间的上一个区间的 $ r < pos $；
我们可以发现，此时 $ pos $ 太大了，已经超出了区间长度，所以直接返回迭代器即可；
- $ pos $ 在此区间的上一个区间中；
把此区间的上一个区间拆分成 $ l, pos - 1, v $ 和 $ pos, r, v $ 两个区间即可；
一个技巧：$ set $ 的 $ insert $ 函数有一个返回值，是 $ pair $ 类型的，$ first $ 返回插入元素的迭代器，$ second $ 返回这个元素是否被插入（因为 $ set $ 不可重）；
set<sss>::iterator spilt(long long pos) {
set<sss>::iterator it = s.lower_bound(sss{pos, 0, 0});
if (it != s.end() && it -> l == pos) return it;
it--;
if (it -> r < pos) return s.end();
long long l = it -> l;
long long r = it -> r;
long long v = it -> v;
s.erase(it);
s.insert(sss{l, pos - 1, v});
return s.insert(sss{pos, r, v}).first;
}
注：$ it -> l $ 等价于 $ *it.l $；
操作二 assign
区间推平操作，设要修改的区间为 $ [l, r] $，我们可以先 $ spilt(r - 1) $，再 $ spilt(l) $，（顺序不能颠倒，不然会 $ RE $），最后删除这两步操作所对应的迭代器之间的所有元素（子区间），并插入要修改的元素（区间）即可；
void assign(long long l, long long r, long long x) {
set<sss>::iterator rit = spilt(r + 1), lit = spilt(l);
s.erase(lit, rit);
s.insert(sss{l, r, x});
}
注：$ s.erase(a, b) $ 指的是删除 $ [a, b) $ 之间的元素；
操作三 其它暴力操作
几乎所有区间上的操作，只要你会暴力，就能用她做；
对于一段要操作的区间 $ [l, r] $，直接暴力遍历其中所有的元素，在进行操作即可；
对于第三个操作，发现用线段树不太好做，又发现数据随机，所以直接珂朵莉树搞它就行；
点击查看代码
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <set>
#include <vector>
using namespace std;
long long n, m, seed, vmax;
long long a[1000005];
struct sss{
long long l, r;
mutable long long v;
bool operator <(const sss &A) const {
return l < A.l;
}
};
set<sss> s;
set<sss>::iterator spilt(long long pos) {
set<sss>::iterator it = s.lower_bound(sss{pos, 0, 0});
if (it != s.end() && it -> l == pos) return it;
it--;
if (it -> r < pos) return s.end();
long long l = it -> l;
long long r = it -> r;
long long v = it -> v;
s.erase(it);
s.insert(sss{l, pos - 1, v});
return s.insert(sss{pos, r, v}).first;
}
void assign(long long l, long long r, long long x) {
set<sss>::iterator rit = spilt(r + 1), lit = spilt(l);
s.erase(lit, rit);
s.insert(sss{l, r, x});
}
long long rnd() {
long long ret = seed;
seed = (seed * 7 + 13) % 1000000007;
return ret;
}
void add(long long l, long long r, long long d) {
set<sss>::iterator rit = spilt(r + 1), lit = spilt(l);
for (set<sss>::iterator it = lit; it != rit; it++) {
it -> v += d;
}
}
vector<pair<long long, long long> > v;
long long ask_kth(long long l, long long r, long long k) {
set<sss>::iterator rit = spilt(r + 1), lit = spilt(l);
v.clear();
for (set<sss>::iterator it = lit; it != rit; it++) {
v.push_back({it -> v, it -> r - it -> l + 1});
}
sort(v.begin(), v.end());
long long o = 0;
while(1) {
k -= v[o].second;
if (k <= 0) return v[o].first;
o++;
}
}
long long ksm(long long a, long long b, long long c) {
long long ans = 1;
while(b) {
if (b & 1) ans = ans * a % c;
a = a * a % c;
b >>= 1;
}
return ans;
}
long long mo(long long l, long long r, long long x, long long y) {
set<sss>::iterator rit = spilt(r + 1), lit = spilt(l);
long long ans = 0;
for (set<sss>::iterator it = lit; it != rit; it++) {
ans = (ans + ksm(it -> v % y, x, y) * (it -> r - it -> l + 1) % y) % y;
}
return ans;
}
int main() {
cin >> n >> m >> seed >> vmax;
for (long long i = 1; i <= n; i++) {
a[i] = (rnd() % vmax) + 1;
s.insert(sss{i, i, a[i]});
}
for (long long i = 1; i <= m; ++i) {
long long op, l, r, x, y;
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) {
cout << ask_kth(l, r, x) << endl;
} else if (op == 4) {
cout << mo(l, r, x, y) << endl;
}
}
return 0;
}