[算法]珂朵莉树
wangyibo201026
·
·
个人记录
何为珂朵莉树
珂朵莉树，又名老司机树（\text{ODT}），是由毒瘤 lxl 发明的一种暴力数据结构。
\text{ODT} 的前置知识
需掌握 set 的用法。
\text{ODT} 题目
以 \text{ODT} 的祖宗 CF896C 为例，来进行以下讲解。
基本操作
注意：以下代码在 c++14 下可以编译成功。
1. 定义
```cpp
struct Node{
int l, r;
mutable int val;
Node(int L, int R = -1, int v = 0){
l = L;
r = R;
val = v;
}
bool operator<(const Node &x) const{
return l < x.l;
}
};
```
~~很迷吧！~~
首先解释 `mutable` 是什么意思，因为 `set` 的特质，要修改一个元素必须取出，修改，删除，插入，十分复杂，而 `mutable` 可以使得任何元素（包括 `const`）都能任意修改。
然后就是初始化了，其中 `R = -1, v = 0` 表示如果没有参数就自动设为 $-1$ 和 $0$，这里也没有什么好讲的。
接下来就是重载运算符，因为 `set` 自动排序，不能删。
### 2. 分裂区间（$\text{split}$）
首先这个函数只有一个参数，根据这个参数找到所在区间 $[l, r]$，然后分裂成 $[l, pos - 1]$ 和 $[pos, r]$，你要说为什么不像线段树那样分裂成 $[l, pos]$ 和 $[pos + 1, r]$，那我也不知道辣！
为什么需要这个操作呢，因为在别的操作的时候，可能会有的节点的左端点跳过操作的左端点，但右端点还在里面，反正需要就对了。
就比如说这样：
蓝色代表存在 `set` 里的节点，这些节点代表一个区间，里面的值都相同。而蓝色区间表示查询区间，从这张图我们就可以看出，需要将第二个节点和第四个节点分裂，才能操作完成。
好了，废话不多说，直接上代码：
```cpp
auto split(int pos){ //返回的是分裂完之后的迭代器
auto it = odt.lower_bound(Node(pos));
if(it != odt.end() && it -> l == pos){ //如果的区间左端点就不需要分裂
return it;
}
it--; //这里因为使用 lower_bound，所以要-1才能是包含 pos 的区间
int l = it -> l, r = it -> r, val = it -> val;
odt.erase(it); //删除这段区间，分成两段区间
odt.insert(Node(l, pos - 1, val));
return odt.insert(Node(pos, r, val)).first; //这里因为区间起始点是 pos，所以需要返回
}
```
至于一些问题，要等到下面才能解释清。
### 3. 区间推平（$\text{assign}$）
首先，我们应该解决上面那个问题。
有的人显然就会说：
```cpp
auto itl = split(l), itr = split(r + 1) //这里为什么是 r + 1, 因为返回的迭代器正好是包含 r 的迭代器多 1，后面好处理
```
恭喜你，成功的 $\color{purple}\text{RE}$ 了。
首先，我们考虑为何会 $\color{purple}\text{RE}$。
因为你把 `l` $\text{split}$ 后，没有什么问题，但是如果 $\text{split}$ `r + 1` 的时候，就会出大问题，因为我们已经把区间给删掉了，这样就会导致有些情况会出大问题，~~听不懂没关系，反正我也听不懂~~。
那么代码就好写了：
```cpp
void assign(int l, int r, int val){
auto itr = split(r + 1), itl = split(l);
odt.erase(itl, itr); //这里删除是删除 [itl, itr - 1]
odt.insert(Node(l, r, val)); //重新插入就行了
}
```
没错，就是这么简单。
### 4. 修改操作（$\text{update}$）
跟推平操作一样，还是：
```cpp
auto itr = split(r + 1), itl = split(l);
```
然后针对 $[itl, itr - 1]$ 这个区间内的修改的就行了。
模板：
```cpp
void update(int l, int r, int val){
auto itr = split(r + 1), itl = split(l);
for(auto i = itl; i != itr; i++){ //这里 != itr 就是 <，但由于迭代器特性，所以不能用 <
//more
}
}
```
由于是区间加，显然就是这样：
```cpp
void update(int l, int r, int val){
auto itr = split(r + 1), itl = split(l);
for(auto i = itl; i != itr; i++){
i -> val += val; //这里的 -> 就相当于结构体的.，只不过是指针用法
}
}
```
### 5. 其他神奇操作
区间排名，直接全部扔进维克托（$\text{vector}$）里，排个序再神奇乱搞就可以了：
```cpp
int rnk(int l, int r, int x){
vector< pair<int, int> > num;
init
for(auto i = itl; i != itr; i++){
num.push_back(make_pair(i -> val, (i -> r) - (i -> l) + 1));
}
sort(num.begin(), num.end());
for(auto i = num.begin(); i != num.end(); i++){ //这就是用 auto 的好处
x -= i -> second;
if(x <= 0){
return i -> first;
}
}
return -1; //如果没有返回 -1
}
```
区间幂次，直接暴力就行了：
```cpp
int query(int l, int r, int x, int p){
auto itr = split(r + 1), itl = split(l);
int ans = 0;
for(auto i = itl; i != itr; i++){
ans = (ans + fastpow(i -> val, x, p) * ((i -> r) - (i -> l) + 1)) % p;
}
return ans;
}
```
海油各种神奇操作，比如说最大子段和，最长上升/下降/不上升/不下降子序列，还有更多。
## 代码
CF896C 代码：
```cpp
#include<bits/stdc++.h>
#define init auto itr = split(r + 1), itl = split(l);
#define int long long //话说今年一金牌选手 Qiu**（为保护当事人隐私，已打码），没开 long long，无缘全国前五......
using namespace std;
const int mod = 1e9 + 7;
const int N = 1e5 + 5;
int n, m, seed, vmax;
int a[N];
int rnd(){
int ret = seed;
seed = (seed * 7 + 13) % mod;
return ret;
}
int fastpow(int a, int b, int p){
int ans = 1;
while(b){
if(b & 1){
ans = a % p * ans % p % p;
}
b >>= 1;
a = a % p * a % p % p;
}
return ans;
}
struct Node{
int l, r;
mutable int val;
Node(int L, int R = -1, int v = 0){
l = L;
r = R;
val = v;
}
bool operator<(const Node &x) const{
return l < x.l;
}
};
set<Node> odt;
auto split(int pos){
auto it = odt.lower_bound(Node(pos));
if(it != odt.end() && it -> l == pos){
return it;
}
it--;
int l = it -> l, r = it -> r, val = it -> val;
odt.erase(it);
odt.insert(Node(l, pos - 1, val));
return odt.insert(Node(pos, r, val)).first;
}
void assign(int l, int r, int val){
init
odt.erase(itl, itr);
odt.insert(Node(l, r, val));
}
void update(int l, int r, int val){
init
for(auto i = itl; i != itr; i++){
i -> val += val;
}
}
int rnk(int l, int r, int x){
vector< pair<int, int> > num;
init
for(auto i = itl; i != itr; i++){
num.push_back(make_pair(i -> val, (i -> r) - (i -> l) + 1));
}
sort(num.begin(), num.end());
for(auto i = num.begin(); i != num.end(); i++){
x -= i -> second;
if(x <= 0){
return i -> first;
}
}
return -1;
}
int query(int l, int r, int x, int p){
init
int ans = 0;
for(auto i = itl; i != itr; i++){
ans = (ans + fastpow(i -> val, x, p) * ((i -> r) - (i -> l) + 1)) % p;
}
return ans;
}
signed main(){
cin >> n >> m >> seed >> vmax;
for(int i = 1; i <= n; i++){
a[i] = rnd() % vmax + 1;
odt.insert(Node(i, i, a[i]));
}
while(m--){
int op = rnd() % 4 + 1, l = rnd() % n + 1, r = rnd() % n + 1, x, y;
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){
update(l, r, x);
}
else if(op == 2){
assign(l, r, x);
}
else if(op == 3){
cout << rnk(l, r, x) << '\n';
}
else{
cout << query(l, r, x, y) << '\n';
}
}
return 0;
}
```
## 时间复杂度分析
由于期望只有 $\log n$ 个节点，又因为排序需要时间，所以**期望**时间复杂度为 $O(n \log n \log n)$，出题人卡 $\text{ODT}$ 很简单，不给区间赋值就卡了。
## $\text{ODT}$ 题目
题单：[](https://www.luogu.com.cn/training/210300)这里有东西哦。
题目：[这里](https://www.luogu.com.cn/problem/U239135)