珂朵莉树

珂朵莉树

Why Chtholly

因为这个数据结构来源于CF896C,所以叫做珂朵莉树(又名ODT(Old Driver Tree)

操作主要有:

  • 区间加
  • 将区间内所有树改为x
  • 输出区间第k大
  • 输出[l,r]区间的 $\sum_{i=l}^ra_x^i \mod y$

How To use Chtholly

太暴力了和珂朵莉一点关系都没有

构建一颗Chtholly Tree:

1
2
3
4
5
6
7
8
9
struct Node{
int l,r;
mutable int val;
Node(int ll,int rr = -1,int vall= 0):l(ll),r(rr),val(vall){};
inline bool operator < (const Node &b)const{
return l<b.l;
}
};
set<Node> s;//原始的珂朵莉树

构建完了,如果添加元素的话就 s.insert(Node(l,r,val));即可

最核心的操作:Split: 将[l,r]的区间变为[l,pos-1],[pos+1,r]两个区间

1
2
3
4
5
6
7
8
9
inline auto split(int pos){
auto it = s.lower_bound(Node(pos));
if(it!=s.end()&&it->l==pos)return it;
it--;
int L = it->l,R = it->r,v = it->val;
s.erase(it);
s.insert(Node(L,pos-1,v));
return s.insert(Node(pos,R,v)).first;//这里s.insert返回的是一个pair,first是指向insert之后的节点的。
}

但是如果只有Split,复杂度肯定会炸。所以还有一个操作,用来减少复杂度的:Assign,作用是将[l,l],[l+1,l+1],…,[r,r]合并为一 个区间[l,r]

1
2
3
4
5
inline auto assign(int l,int r,int v){//把(l,r)改为v
auto itL = split(l),itR = split(r+1);
s.erase(itL,itR);
s.insert(Node(l,r,v));
}

然后剩下的操作就更暴力了

区间加

1
2
3
4
inline void add(int l,int r,int v){//把(l,r)加上v
auto itL = split(l),itR = split(r+1);
for(;itL!=itR;itL++)itL->val+=v;
}

区间第k大(直接取出来排个序)

1
2
3
4
5
6
7
8
9
10
11
inline int rnk(int l,int r,int k){
vector<pair<int,int>> vec;
auto itL = split(l),itR = split(r+1);
for(;itL!=itR;itL++)vec.push_back(make_pair(itL->val,itL->r-itL->l+1));
sort(vec.begin(),vec.end());
for(auto it = vec.begin();it!=vec.end();it++){
k-=it->second;
if(k<=0)return it->first;
}
return -1;
}

求和也很奇怪

1
2
3
4
5
6
7
8
inline int sum(int l,int r,int ex,int mod){
auto itL = split(l),itR = split(r+1);
int res = 0;
for(;itL!=itR;itL++){
(res+=Qpow(itL->val,ex,mod)*(itL->r-itL->l+1))%=mod;
}
return res;
}

Some Codes

CF896C完整代码:

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
#include<bits/stdc++.h>
#define int long long
#define FOR(i,l,r) for(register int i=l;i<=r;++i)
using namespace std;
const int md = 1e9+7;
const int N = 1e5+10;
int n,m,seed,v_max;
int a[N];
int rnd(){
int ret = seed;
seed = (seed*7+13)%md;
return ret;
}
struct Node{
int l,r;
mutable int val;
Node(int ll,int rr = -1,int vall= 0):l(ll),r(rr),val(vall){};
inline bool operator < (const Node &b)const{
return l<b.l;
}
};
set<Node> s;//原始的珂朵莉树
inline int Qpow(int a,int b,int mod){
int ret = 1;
a%=mod;
while(b){
if(b&1)(ret*=a)%=mod;
b>>=1;
(a*=a)%=mod;
}
return ret;
}
inline auto split(int pos){
auto it = s.lower_bound(Node(pos));
if(it!=s.end()&&it->l==pos)return it;
it--;
int L = it->l,R = it->r,v = it->val;
s.erase(it);
s.insert(Node(L,pos-1,v));
return s.insert(Node(pos,R,v)).first;
}
inline auto assign(int l,int r,int v){//把(l,r)改为v
auto itL = split(l),itR = split(r+1);
s.erase(itL,itR);
s.insert(Node(l,r,v));
}
inline void add(int l,int r,int v){//把(l,r)加上v
auto itL = split(l),itR = split(r+1);
for(;itL!=itR;itL++)itL->val+=v;
}
inline int rnk(int l,int r,int k){
vector<pair<int,int>> vec;
auto itL = split(l),itR = split(r+1);
for(;itL!=itR;itL++)vec.push_back(make_pair(itL->val,itL->r-itL->l+1));
sort(vec.begin(),vec.end());
for(auto it = vec.begin();it!=vec.end();it++){
k-=it->second;
if(k<=0)return it->first;
}
return -1;
}
inline int sum(int l,int r,int ex,int mod){
auto itL = split(l),itR = split(r+1);
int res = 0;
for(;itL!=itR;itL++){
(res+=Qpow(itL->val,ex,mod)*(itL->r-itL->l+1))%=mod;
}
return res;
}
signed main(){
cin>>n>>m>>seed>>v_max;
FOR(i,1,n)s.insert(Node(i,i,rnd()%v_max+1));
FOR(i,1,m){
int op = (rnd()%4)+1,l = (rnd()%n)+1,r = (rnd()%n)+1,x,y;
// cout<<"Op "<<op<<"\n "<<l<<" "<<r<<endl;
if(l>r)swap(l,r);
if(op==3)x = rnd()%(r-l+1)+1;
else x = rnd()%v_max+1;
if(op==4)y = rnd()%v_max+1;
if(op==1)add(l,r,x);
if(op==2)assign(l,r,x);
if(op==3)cout<<rnk(l,r,x)<<endl;
if(op==4)cout<<sum(l,r,x,y)<<endl;
// bl();
}
}

最后送一个题单,虽然这些题可以用线段树等方法解决,但是学都学了,不用一下不可惜吗

https://www.luogu.com.cn/training/3592

完结★,°:.☆( ̄▽ ̄)/$:.°★

封面来源:

https://wall.alphacoders.com/big.php?i=806829

作者

Steve Li

发布于

2021-10-11

更新于

2022-01-22

许可协议

评论

Your browser is out-of-date!

Update your browser to view this website correctly.&npsb;Update my browser now

×