Steven_MengのBlog

传送门
树套树模板题(线段树套$\rm FHQ Treap$)
一开始听说$\rm FHQ Treap$常数大,会$\rm TLE$,就没敢写,最后发现$\rm FHQ Treap$还是能过的。


好了步入正题:
考虑在线段树的每个节点开一棵$\rm FHQ Treap$,维护的是线段树左右端点$[l,r]$所代表的区间$a_l…a_r$
这样不会$\rm MLE$,因为线段树最多有$\log n$层,而每一层就算填满也只有$O(n)$的空间,所以总空间复杂度是$O(n \log n)$,注意数组要开这么大

$1.$建树:对于节点$[l,r]$,暴力插入$a[l]…a[r]$,时间复杂度$O(n\log^2n)$。
$2.$替换$a[pos]$为$k$:对于包含$pos$的区间$[l,r]$,先删除$a[pos]$,再加入$k$,时间复杂度$O(\log^2n)$。
$3.$查询区间中$num$的排名:我们发现:$num$的排名为区间中小于$num$的数的数量$+1$,又发现线段树的区间查询操作其实将查询区间$[L,R]$分成许多不相交的小区间,根据这个,我们把$num$在小区间的排名$-1$,得到在小区间中小于$num$的数的数量,最后相加,发现小于$num$的数的数量不会重复计算,于是把和$+1$,得到$num$在区间$[L,R]$的排名,时间复杂度$O(\log^2n)$
这里很容易跳进的坑:不能把$num$在小区间中的排名相加,否则$num$会重复算很多次
$4.$查询区间第$k$大的数:因为$\rm FHQ Treap$只能查询$num$的排名,所以考虑二分$num$,时间复杂度$O(\log^3n)$,查询$num$排名$O(\log^2n)$,二分$O(\log n)$。
(当然按照子树大小$\rm Split$,$\rm FHQTreap$也阔以支持查询第$k$大,详情请戳这里
$5.$查询区间中,$num$的前驱:直接把小区间中$num$的所有前驱取个$max$。
$6.$查询区间中,$num$的后继:类似$5.$


注意要判断$num$的前驱后继是否存在,若不存在,相应地输出$\rm INF/-INF$。
还有修改操作做完后,要执行$a[pos]=k$,修改$a$数组。

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
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
#include <bits/stdc++.h>
#define MAXN 50005
#define MAXM 10000005
#define INF 0x7fffffff
using namespace std;
inline int read() {
int x=0,f=1;
char ch=getchar();
while (ch<'0'||ch>'9') {
if (ch=='-') f=-1;
ch=getchar();
}
while (ch>='0'&&ch<='9') {
x=(x*10)+(ch-'0');
ch=getchar();
}
return x*f;
}
int a[MAXN];
struct node{
int l,r;
int val;//每个点的权值
int pri;//优先级(随机生成)
int sz;
}tree[MAXM];
int tot;
struct FHQ_Treap{
#define lc(i) tree[i].l
#define rc(i) tree[i].r
inline void Update(int x){tree[x].sz=tree[lc(x)].sz+tree[rc(x)].sz+1;}
inline int New(int v){
tree[++tot].val=v,tree[tot].pri=rand(),tree[tot].sz=1;
return tot;
}
int Merge(int x,int y){
if (!x||!y) return x+y;
if (tree[x].pri<tree[y].pri){
rc(x)=Merge(rc(x),y),Update(x);
return x;
}
else{
lc(y)=Merge(x,lc(y)),Update(y);
return y;
}
}
void Split(int i,int k,int &x,int &y){
if (!i) x=y=0;
else {
if (tree[i].val<=k){x=i,Split(rc(i),k,rc(i),y);}
else{y=i,Split(lc(i),k,x,lc(i));}
Update(i);
}
}
int root,x,y,z;
inline void Add(int num){
Split(root,num,x,y);
root=Merge(x,Merge(New(num),y));
}
inline void Del(int num){
Split(root,num,x,z);
Split(x,num-1,x,y);
y=Merge(lc(y),rc(y));
root=Merge(Merge(x,y),z);
}
inline int Rank(int num){//获得num排名
Split(root,num-1,x,y);
int temp=tree[x].sz+1;
root=Merge(x,y);
return temp;
}
inline int Kth(int i,int rk){
if (rk<=tree[lc(i)].sz) return Kth(lc(i),rk);
if (rk==tree[lc(i)].sz+1) return tree[i].val;
return Kth(rc(i),rk-tree[lc(i)].sz-1);
}
inline int Pre(int num){
Split(root,num-1,x,y);
int ans=tree[x].sz?Kth(x,tree[x].sz):-INF;
root=Merge(x,y);
return ans;
}
inline int Nex(int num){
Split(root,num,x,y);
int ans=tree[y].sz?Kth(y,1):INF;
root=Merge(x,y);
return ans;
}
inline void BuildTree(int l,int r){
for (register int i=l;i<=r;++i){Add(a[i]);}
}
#undef lc
#undef rc
}T[MAXN<<2];
int n;
namespace SegmentTree{
#define lc i<<1
#define rc i<<1|1
void Build(int i,int l,int r){
T[i].BuildTree(l,r);
if (l==r) return ;
int mid=(l+r)>>1;
Build(lc,l,mid);
Build(rc,mid+1,r);
}
int qrank(int i,int l,int r,int L,int R,int val){
if (L<=l&&r<=R) {
return T[i].Rank(val)-1;
}
int mid=(l+r)>>1;
int ans=0;
if (L<=mid) ans+=qrank(lc,l,mid,L,R,val);
if (mid<R) ans+=qrank(rc,mid+1,r,L,R,val);
return ans;
}
inline int qval(int l,int r,int rk){
int L=0,R=0x7fffffff;
int ans=-1;
while (L<=R){
int mid=(L+R)>>1;
if (qrank(1,1,n,l,r,mid)<rk) ans=mid,L=mid+1;
else R=mid-1;
}
return ans;
}
void Update(int l,int r,int i,int k,int pos){//a[pos]=>k
T[i].Del(a[pos]),T[i].Add(k);
if (l==r) return ;
int mid=(l+r)>>1;
if (pos<=mid) Update(l,mid,lc,k,pos);
else Update(mid+1,r,rc,k,pos);
}
int qpre(int i,int l,int r,int L,int R,int val){
if (L<=l&&r<=R){
return T[i].Pre(val);
}
int mid=(l+r)>>1;
int ans=-0x7fffffff;
if (L<=mid) ans=max(ans,qpre(lc,l,mid,L,R,val));
if (mid<R) ans=max(ans,qpre(rc,mid+1,r,L,R,val));
return ans;
}
int qnex(int i,int l,int r,int L,int R,int val){
if (L<=l&&r<=R){
return T[i].Nex(val);
}
int mid=(l+r)>>1;
int ans=0x7fffffff;
if (L<=mid) ans=min(ans,qnex(lc,l,mid,L,R,val));
if (mid<R) ans=min(ans,qnex(rc,mid+1,r,L,R,val));
return ans;
}
#undef lc
#undef rc
}
using namespace SegmentTree;
int main(){
n=read();int m=read();
for (register int i=1;i<=n;++i){
a[i]=read();
}
Build(1,1,n);
while (m--){
int opr=read();
if (opr==1){
int l=read(),r=read(),k=read();
printf("%d\n",qrank(1,1,n,l,r,k)+1);
}
else if (opr==2){
int l=read(),r=read(),k=read();
printf("%d\n",qval(l,r,k));
}
else if (opr==3){
int pos=read(),k=read();
Update(1,n,1,k,pos),a[pos]=k;
}
else if (opr==4){
int l=read(),r=read(),k=read();
printf("%d\n",qpre(1,1,n,l,r,k));
}
else if (opr==5){
int l=read(),r=read(),k=read();
printf("%d\n",qnex(1,1,n,l,r,k));
}
}
}

 评论