珂朵莉树·颜色段均摊
这玩意名字也是真多，珂朵莉树，ODT（Old Driver Tree），颜色段均摊都是它。其实我觉得硬说这是一种数据结构（尤其是“树”）是不恰当的，这更多应该是一种技巧。 与线段树等传统数据结构的区别在于：它可以更方便地维护每个被覆盖区间的值。如模板题中的操作 4：求 \(\sum_{i=l}^ra_i^x\bmod y\)。 我很喜欢这个东西，它比线段树好写且在随机数据下表现十分优异。
实现
一般用 std::set 实现。似乎用链表可以省下一个 \(\log\)？不过能用到 ODT
的题应该不差这点时间。
节点
1 | struct node{ |
\(l\) 和 \(r\) 表示这一段的区间，\(val\) 表示这一段的权值，使用
mutable 修饰是为了使得结构体或函数在被 const
修饰后仍能修改 \(val\)
的值，这样，我们就可以直接修改在 set 内部的元素的 \(val\)。
split
用于将一个区间为 \([l,r]\)
的区间分裂为 \([l,pos)\) 和 \([pos,r]\)，并返回指向后者的迭代器的函数。
1
2
3
4
5
6
7
8
9
10auto split(int pos){
auto it=odt.lower_bound(node(pos));
if(it!=odt.end()&&it->l==pos)
return it;//pos已是左端点，无需分割
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;//右区间
}std::set::insert() 返回一个
std::pair<iterator,bool>，表示插入元素的迭代器及插入是否成功。
现代编译器应当都可以将 auto 识别为
std::set<node>::iterator。
assign
用于区间赋值。同时也是时间复杂度的保证，以模板题为例，大约 \(\dfrac{1}{4}\) 的操作调用了
assign，而这个操作可以大幅减小 set 的大小。
特别注意：在截取 \([l,r]\)
时一定要先调用 split(r+1) 再调用
split(l)，否则可能导致 RE。 具体原因可以看这里。 1
2
3
4
5
6void assign(int l,int r,int val){
auto itr=split(r+1),itl=split(l);//截取[l,r]
odt.erase(itl,itr);//删除[l,r]
odt.insert(node(l,r,val));//插入新值
return;
}
模板题
对于 1 操作，3 操作和 4 操作，直接分离出对应区间后暴力求解。2
操作直接用 assign。 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
using namespace std;
typedef long long ll;
struct node{
int l,r;
mutable ll val;
node(int l,int r=0,ll val=0):l(l),r(r),val(val){}
bool operator<(const node &x)const{
return l<x.l;
}
};
ll qpow(ll a,int b,int mod){
ll res=1;
a%=mod;
while(b){
if(b&1)
res=res*a%mod;
a=a*a%mod;
b>>=1;
}
return res;
}
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;
ll 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){
auto itr=(split(r+1)),itl=split(l);
odt.erase(itl,itr);
odt.insert(node(l,r,val));
return;
}
void add(int l,int r,int val){
auto itr=split(r+1),itl=split(l);
for(;itl!=itr;itl++)
itl->val+=val;
return;
}
ll kth(int l,int r,int k){
auto itr=split(r+1),itl=split(l);
vector<pair<ll,int>> b;
for(;itl!=itr;itl++)
b.push_back(make_pair(itl->val,itl->r-itl->l+1));
sort(b.begin(),b.end());
for(auto t:b){
k-=t.second;
if(k<=0)
return t.first;
}
}
ll sum(int l,int r,int x,int mod){
ll res=0;
auto itr=split(r+1),itl=split(l);
for(;itl!=itr;itl++)
res=(res+(qpow(itl->val,x,mod)*(itl->r-itl->l+1))%mod)%mod;
return res;
}
const int N=1e5+10;
int n,m,seed,vmax,a[N],op,x,y,l,r;
int rnd(){
int ret=seed;
seed=(seed*7ll+13)%1000000007;
return ret;
}
int main(){
ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
cin>>n>>m>>seed>>vmax;
for(int i=1;i<=n;i++){
a[i]=(rnd()%vmax)+1;
odt.insert(node(i,i,a[i]));
}
for(int i=1;i<=m;i++){
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<<kth(l,r,x)<<'\n';
else
cout<<sum(l,r,x,y)<<'\n';
}
return 0;
}十年 OI 一场空，不开
long long 见祖宗。
复杂度分析
我们可以从模板题中发现，这玩意除区间赋值外都需要暴力，所以是一种暴力数据结构。对于模板题，均摊时间复杂度
\(O(m\log
n)\)。其时间复杂度保证完全依赖于
assign，所以仅适用于数据随机生成且带区间赋值操作的题。比如区间染色问题。