珂朵莉树

珂朵莉树

珂朵莉树是一颗树,我们用集合来维护,c++中集合是红黑树,所以我们借助此集合来完成珂朵莉树。
我们将区间分段,那么各段有唯一的左端点,我们将左端点放入集合,当我们遍历集合的时候,我们就得到了我们要的序列,此时我们维护了结构,但未维护值,进一步发现我们可以使用map,用键值对来维护更多信息,键用来维护树的结构,值来维护序列的值。

split

因为我们要维护区间信息,所以我们需要操作split来提取区间,本质上提取区间为提取单点,这一点在splay中表现的很出色,当我们提取出左端点和右端点的时候,区间也就被提取出来了,如果提取位置x,在红黑树中我们二分到x的位置,若此处是一个区间[l,r],我们将此区间拆分为[l,x-1][x,r]即可。

assign

我们提取出区间,删掉这些节点然后,插入一个新的节点即可

add

我们提取出区间,暴力更新所有节点即可

sum

我们提取出区间,暴力计算所有节点,使用快速幂

kth

我们提取出区间,还是暴力

什么时候选择此数据结构

数据随机且含有区间赋值操作,此数据结构的操作可以在splay上实现,并维护更多信息,map法仅仅只是编码简单了很多。

例题

C. Willem, Chtholly and Seniorious
odt代码
cf896cview raw
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
#include <bits/stdc++.h>
using namespace std;
/*
* cf896c
* 区间加,区间赋值,求区间k次方和,求区间第k小,数据随机,复杂度(n+m)lgn
*
* ODT -> old driver tree -> 珂朵莉树
*
* */
typedef long long ll;
ll qpow(ll a,ll b,ll p){ll r=1;for(;b;b>>=1,a=a*a%p)if(b&1)r=r*a%p;return r;}
typedef map<int,ll>::iterator IT;
IT split(map<int,ll>&t,int x){//将x分出来,使得这是某个区间的左端点
IT it=t.lower_bound(x);
if(it->first==x) return it;
return t.emplace(x,(--it)->second).first;
}
void assign(map<int,ll>&t,int l,int r,int w){
t.erase(split(t,l),split(t,r+1)), t.emplace(l,w);
}
void add(map<int,ll>&t,int l,int r,int w){
for(IT i=split(t,l),j=split(t,r+1);i!=j;++i) i->second+=w;
}
int sum(map<int,ll>&t,int l,int r,int y,int p){
int res=0;
for(IT j=split(t,l),k=split(t,r+1),i=j++;i!=k;i=j++) {// i=j++写在最后执行
res=(res+qpow(i->second%p,y,p)*(j->first-i->first))%p;
}
return res;
}
ll kth(map<int,ll>&t,int l,int r,int k){// 1<=k<=r-l+1
vector<pair<ll,int>>v;
for(IT j=split(t,l),k=split(t,r+1),i=j++;i!=k;i=j++) {
v.emplace_back(i->second,j->first-i->first);
}
sort(v.begin(),v.end());
for(auto x:v) {
if(k<=x.second) return x.first;
else k-=x.second;
}
assert(false);// k>r-l+1
}

ll seed;
ll rnd(){
ll ret = seed;
seed = (seed * 7 + 13) % 1000000007;
return ret;
}

int main(){
map<int,ll>tr;
int n,m,vmax;
cin>>n>>m>>seed>>vmax;
for(int i=1;i<=n;i++) tr[i]=rnd()%vmax+1;
tr[n+1]=-1;// 终点哨兵
int op,l,r,x,y;
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;
switch(op){
case 1:add(tr,l,r,x);break;
case 2:assign(tr,l,r,x);break;
case 3:printf("%lld\n",kth(tr,l,r,x));break;
case 4:printf("%d\n",sum(tr,l,r,x,y));break;
}
}
}