珂朵莉树（ODT）是一种在随机数据下复杂度优秀的维护存在区间赋值操作的数据结构。
在随机数据下，期望不同的值的个数并不多，因此可以合为一个节点处理，便得到了珂朵莉树。
ODT 珂朵莉树
例题：CF896C Willem, Chtholly and Seniorious
给定序列 $a_1,a_2,\cdots,a_n$。维护操作：
- 将 $a_l,a_{l+1},\cdots,a_r$ 增加 $x$。
- 将 $a_l,a_{l+1},\cdots,a_r$ 修改为 $x$。
- 输出 $a_l,a_{l+1},\cdots,a_r$ 中第 $k$ 小的数。
- 输出 $\displaystyle\sum_{i=l}^ra_i^x\bmod y$。
数据随机生成。
可以考虑使用 ODT 维护。
原理
ODT 其实是一种较为暴力的数据结构。
ODT 将原序列划分为了若干段，每一段内的元素值均相同。
在维护区间操作时，可以在这些段上操作，配合段的分裂等操作即可实现。
节点存储
每一个点（段）需要维护三个信息：
- 区间左右端点。
- 区间维护信息。
以例题中维护区间内的值为例。
1
2
3
4
struct node{
int l,r;
mutable int value;
};
其中，mutable 是 C++ 关键字，可以突破 const 的限制，修改其值。便于我们使用其他数据结构维护时更改信息。
我们可以使用平衡树按照区间左端点维护节点。一般使用 set。因此需要重载运算符 <：
1
2
3
friend bool operator <(node a,node b){
return a.l<b.l;
}
基础操作
split 操作
split 操作是 ODT 的核心操作。split 操作接受参数 $x$，将包含 $x$ 的区间 $[l,r]$ 切割为了两端区间 $[l,x-1),[x,r]$，并返回 $[x,r]$ 的迭代器。
1
2
3
4
5
6
7
8
9
10
11
auto split(int x){
auto p=t.lower_bound({x});
if(p!=t.end()&&p->l==x){
return p;
}
p=prev(p);
int l=p->l,r=p->r,value=p->value;
t.erase(p);
t.insert({l,x-1,value});
return t.insert({x,r,value}).first;
}
assign 操作
即区间赋值。配合 split 操作即可删除 $[l,r]$ 内的所有区间，插入新的 $[l,r]$ 维护信息即可。
split 顺序问题
split(r+1) 和 split(l) 的顺序不能反，否则 set 的迭代器会失效。
1
2
3
4
5
6
void assign(int l,int r,int value){
auto pr=split(r+1);
auto pl=split(l);
t.erase(pl,pr);
t.insert({l,r,value});
}
perform 操作
perform 操作可以找到在 $[l,r]$ 内的所有点，用于查询信息。
1
2
3
4
5
6
7
void perform(int l,int r){
auto pr=split(r+1);
auto pl=split(l);
for(auto i=pl;i!=pr;i=next(i)){
//...
}
}
初始化
在所有的 split 操作之前，需要向 ODT 中插入一个包含所有区间的极长区间。例如有效区间为 $[1,n]$，就可以插入 $[1,n+1]$。
例题操作
其实都可以简单地基于 assign 操作和 perform 操作得到。
区间加
1
2
3
4
5
6
7
void add(int l,int r,int x){
auto pr=split(r+1);
auto pl=split(l);
for(auto i=pl;i!=pr;i=next(i)){
i->value+=x;
}
}
第 $k$ 小
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
int rank(int l,int r,int x){
vector<pair<int,int> >s;
auto pr=split(r+1);
auto pl=split(l);
for(auto i=pl;i!=pr;i=next(i)){
s.push_back({i->value,i->r - i->l + 1});
}
sort(s.begin(),s.end());
for(auto i:s){
x-=i.second;
if(x<=0){
return i.first;
}
}
}
幂次和
1
2
3
4
5
6
7
8
9
int sum(int l,int r,int x,int P){
auto pr=split(r+1);
auto pl=split(l);
int ans=0;
for(auto i=pl;i!=pr;i=next(i)){
ans=(ans + qpow(i->value,x,P)*(i->r - i->l + 1ll))%P;
}
return ans;
}
时间复杂度
在随机数据下，使用 set 实现的 ODT 复杂度为 $\mathcal O(n\log\log n)$。
如果在 perform 操作后立即对同一区间进行 assign 操作，则均摊复杂度为 $\mathcal O(m\log n)$，$m$ 为操作次数。
但是如果 perform 操作次数过多，则会严重影响 ODT 的复杂度，请勿滥用。甚至于可能获得高于平方量级的复杂度。
参见此处。
例题 AC 代码
一个坑点：快速幂底数需要先取一遍模。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
//#include<bits/stdc++.h>
#include<algorithm>
#include<iostream>
#include<cstring>
#include<iomanip>
#include<cstdio>
#include<string>
#include<vector>
#include<cmath>
#include<ctime>
#include<deque>
#include<queue>
#include<stack>
#include<list>
#include<set>
using namespace std;
#define int long long
constexpr const int N=1e5;
namespace data{
constexpr const int P=1000000007;
int s,v;
int rand(){
int pl=s;
s=(s*7ll+13)%P;
return pl;
}
void generate(int n,int a[]){
for(int i=1;i<=n;i++){
a[i]=rand()%v+1;
}
}
void generate(int n,int &op,int &l,int &r,int &x,int &y){
op=rand()%4+1;
l=rand()%n+1;
r=rand()%n+1;
if(l>r){
swap(l,r);
}
if(op==3){
x=rand()%(r-l+1)+1;
}else{
x=rand()%v+1;
}
if(op==4){
y=rand()%v+1;
}
}
}
int n,a[N+1];
int qpow(int base,int n,int P){
base%=P;
int ans=1;
while(n){
if(n&1){
ans=1ll*ans*base%P;
}
base=1ll*base*base%P;
n>>=1;
}
return ans;
}
struct ODT{
struct node{
int l,r;
mutable int value;
};
friend bool operator <(node a,node b){
return a.l<b.l;
}
set<node>t;
void build(int l,int r){
t.clear();
t.insert({l,r+1});
}
auto split(int x){
auto p=t.lower_bound({x});
if(p!=t.end()&&p->l==x){
return p;
}
p=prev(p);
int l=p->l,r=p->r,value=p->value;
t.erase(p);
t.insert({l,x-1,value});
return t.insert({x,r,value}).first;
}
void assign(int l,int r,int value){
auto pr=split(r+1);
auto pl=split(l);
t.erase(pl,pr);
t.insert({l,r,value});
}
void add(int l,int r,int x){
auto pr=split(r+1);
auto pl=split(l);
for(auto i=pl;i!=pr;i=next(i)){
i->value+=x;
}
}
int rank(int l,int r,int x){
vector<pair<int,int> >s;
auto pr=split(r+1);
auto pl=split(l);
for(auto i=pl;i!=pr;i=next(i)){
s.push_back({i->value,i->r - i->l + 1});
}
sort(s.begin(),s.end());
for(auto i:s){
x-=i.second;
if(x<=0){
return i.first;
}
}
}
int sum(int l,int r,int x,int P){
auto pr=split(r+1);
auto pl=split(l);
int ans=0;
for(auto i=pl;i!=pr;i=next(i)){
ans=(ans + qpow(i->value,x,P)*(i->r - i->l + 1ll))%P;
}
return ans;
}
}t;
main(){
/*freopen("test.in","r",stdin);
freopen("test.out","w",stdout);*/
ios::sync_with_stdio(false);
cin.tie(0);cout.tie(0);
int m;
cin>>n>>m>>data::s>>data::v;
data::generate(n,a);
t.build(1,n);
for(int i=1;i<=n;i++){
t.assign(i,i,a[i]);
}
while(m--){
int op,l,r,x,y;
data::generate(n,op,l,r,x,y);
switch(op){
case 1:
t.add(l,r,x);
break;
case 2:
t.assign(l,r,x);
break;
case 3:
cout<<t.rank(l,r,x)<<'\n';
break;
case 4:
cout<<t.sum(l,r,x,y)<<'\n';
break;
}
}
cout.flush();
/*fclose(stdin);
fclose(stdout);*/
return 0;
}
