【Bzoj3196】【Luogu3380】二逼平衡树

来源和评测点

Tyvj1730
Bzoj3196
Luogu3380
Caioj1135

题目

【题目大意】
您需要写一种数据结构(可参考题目标题),来维护一个有序数列,其中需要提供以下操作:
1.查询k在区间内的排名
2.查询区间内排名为k的值
3.修改某一位值上的数值
4.查询k在区间内的前驱(前驱定义为小于x,且最大的数)
5.查询k在区间内的后继(后继定义为大于x,且最小的数)
【输入格式】
第一行两个数 n,m 表示长度为n的有序序列和m个操作
第二行有n个数,表示有序序列
下面有m行,opt表示操作标号
若opt=1 则为操作1,之后有三个数l,r,k 表示查询k在区间[l,r]的排名
若opt=2 则为操作2,之后有三个数l,r,k 表示查询区间[l,r]内排名为k的数
若opt=3 则为操作3,之后有两个数pos,k 表示将pos位置的数修改为k
若opt=4 则为操作4,之后有三个数l,r,k 表示查询区间[l,r]内k的前驱
若opt=5 则为操作5,之后有三个数l,r,k 表示查询区间[l,r]内k的后继
【输出格式】
对于操作1,2,4,5各输出一行,表示查询结果
【输入样例】
9 6
4 2 2 1 9 4 0 1 1
2 1 4 3
3 4 10
2 1 4 3
1 2 5 9
4 3 9 5
5 2 8 5
【输出样例】
2
4
3
4
9

分析1

其他伸展树

第一次树套树,第一次代码行数300+

线段树关键字:位置关系
伸展树关键字:大小关系

n=m=50000,num=100000000
logn=16,lognum=27
建树2n颗,nlogn个节点,时间nlogn

接下来分析几个操作:
1.查排名,(区间logn)*(前驱logn)=256,(每个完整子区间中k的排名-1)之和+1
2.找数字,(二分lognum)*(区间logn)*(后继logn)=6912,调用操作1,二分数字,验证
3.改数字,2*(深度logn)*(伸展操作logn)=512,删除,添加
4.5.前驱后继,(区间logn)*(前驱后继logn)=256,每个完整子区间中k的前驱后继的极值
总时间:极限200000000即3s

从线段树的角度看:每个区间一个线段树
从Splay的角度看:所有的Splay都挂在超级根节点Root上,
注意我采取某些手段避免了Root向下认儿子

代码1

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
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
//Zory-2018
//*******************头文件*******************
#include<cstdio>
#include<cstring>
#include<cmath>
#include<algorithm>
using namespace std;
int mymin(int x,int y) {return x<y?x:y;}
int mymax(int x,int y) {return x>y?x:y;}
//*******************全局常量*******************
const int MAXN=50000+10;
const int NUL=-1;
const int Root=0;
const int INF=0x7fffffff;
//*******************Splay1-基础操作*******************
struct pt
{
int son[2],f;
int d;
int n,c;
pt()
{
son[0]=son[1]=f=NUL;
}
}p[30*MAXN];
int ln=0;
void update(int x)
{
p[x].c=p[x].n;
int lc=p[x].son[0],rc=p[x].son[1];
if(lc!=NUL) p[x].c+=p[lc].c;
if(rc!=NUL) p[x].c+=p[rc].c;
}
void rotate(int x,int w)
{
int f=p[x].f,ff=p[f].f;
if(ff!=Root)
{
if(p[ff].son[0]==f) p[ff].son[0]=x;
else p[ff].son[1]=x;
}
p[x].f=ff;
int xson=p[x].son[w];
if(xson!=NUL) p[xson].f=f;
p[f].son[1-w]=xson;
p[x].son[w]=f;
p[f].f=x;
update(f);
update(x);
}
void add(int d,int f)
{
ln++;
p[ln].d=d;p[ln].f=f;
p[ln].n=p[ln].c=1;
p[ln].son[0]=p[ln].son[1]=NUL;
if(f!=Root)
{
if(d<p[f].d) p[f].son[0]=ln;
else p[f].son[1]=ln;
}
}
//*******************Splay2-与根有关*******************
int root[2*MAXN];
void splay(int r,int x,int rt)
{
while(p[x].f!=rt)
{
int f=p[x].f,ff=p[f].f;
if(ff==rt)
{
if(p[f].son[0]==x) rotate(x,1);
else rotate(x,0);
}
else
{
if(p[ff].son[0]==f and p[f].son[0]==x) rotate(f,1),rotate(x,1);
else if(p[ff].son[0]==f and p[f].son[1]==x) rotate(x,0),rotate(x,1);
else if(p[ff].son[1]==f and p[f].son[0]==x) rotate(x,1),rotate(x,0);
else if(p[ff].son[1]==f and p[f].son[1]==x) rotate(f,0),rotate(x,0);
}
}
if(rt==Root) root[r]=x;
}
int findip(int r,int d)
{
int x=root[r];
while(p[x].d!=d)
{
int lc=p[x].son[0],rc=p[x].son[1];
if(d<p[x].d) { if(lc!=NUL) x=lc; else break; }
else { if(rc!=NUL) x=rc; else break; }
}
return x;
}
void ins(int r,int d)
{
if(root[r]==NUL)
{
add(d,Root);
root[r]=ln;
}
else
{
int x=findip(r,d);
if(p[x].d==d)
{
p[x].n++;
splay(r,x,Root);
}
else
{
add(d,x);
splay(r,ln,Root);
}
}
}
void del(int r,int d)
{
int x=findip(r,d);
if(p[x].d!=d) return;
splay(r,x,Root);
if(p[x].n>1)
{
p[x].n--;
update(x);
}
else
{
int lc=p[x].son[0],rc=p[x].son[1];
if(lc==NUL and rc==NUL)
{
root[r]=NUL;
}
else if(lc!=NUL and rc==NUL)
{
root[r]=lc;
p[lc].f=Root;
}
else if(lc==NUL and rc!=NUL)
{
root[r]=rc;
p[rc].f=Root;
}
else
{
int w=lc;while(p[w].son[1]>0) w=p[w].son[1];
splay(r,w,x);root[r]=w;p[w].f=Root;
p[w].son[1]=rc;p[rc].f=w;
update(w);
}
}
}
int findQ(int r,int d)
{
int x=findip(r,d);splay(r,x,Root);
if(p[x].d>=d and p[x].son[0]!=NUL)
{
x=p[x].son[0];
while(p[x].son[1]!=NUL) x=p[x].son[1];
}
if(p[x].d<d) return p[x].d;
return -INF;
}
int findH(int r,int d)
{
int x=findip(r,d);splay(r,x,Root);
if(p[x].d<=d and p[x].son[1]!=NUL)
{
x=p[x].son[1];
while(p[x].son[0]!=NUL) x=p[x].son[0];
}
if(p[x].d>d) return p[x].d;
return INF;
}
int findbf(int r,int d)//更小的
{
int x=findip(r,d);splay(r,x,Root);
int lc=p[x].son[0];
if(p[x].d==d) return p[ (lc==NUL)?0:lc ].c;
if(p[x].d>d and lc!=NUL)
{
x=lc;
while(p[x].son[1]!=NUL) x=p[x].son[1];
}
if(p[x].d<d)
{
splay(r,x,Root);lc=p[x].son[0];
return p[ (lc==NUL)?0:lc ].c+p[x].n;
}
else return 0;
}
//*******************线段树*******************
int num[MAXN];
struct mg
{
int l,r;
int lc,rc;
}s[2*MAXN];
int len=0;
int build(int l,int r)
{
int t=++len;s[t].l=l;s[t].r=r;
for(int i=l;i<=r;i++) ins(t,num[i]);
//把t作为根节点的下标
if(l==r) s[t].lc=s[t].rc=NUL;
else
{
int mid=(l+r)/2;
s[t].lc=build(l,mid);
s[t].rc=build(mid+1,r);
}
return t;
}
void change(int x,int pos,int yd,int d)//改数字
{
del(x,yd);ins(x,d);
if(s[x].l==s[x].r) return;
int mid=(s[x].l+s[x].r)/2;
if( pos<=mid ) change(s[x].lc,pos,yd,d);
else change(s[x].rc,pos,yd,d);
}
//*******************接口*******************
int solve1(int x,int l,int r,int d)//查排名
{
if(s[x].l==l and s[x].r==r) return findbf(x,d);
int lc=s[x].lc,rc=s[x].rc,mid=(s[x].l+s[x].r)/2;
if(r<=mid) return solve1(lc,l,r,d);
if(l>mid) return solve1(rc,l,r,d);
return solve1(lc,l,mid,d)+solve1(rc,mid+1,r,d);
}
int solve2(int l,int r,int k)//找数字
{
int ll=0,rr=100000000,ans=-1;
//满足运用二分的条件,因为数字与排名成正比
while(ll<=rr)
{
int mid=(ll+rr)/2,rk=solve1(1,l,r,mid)+1;
if(rk<=k) ans=mid,ll=mid+1;
else rr=mid-1;
}
return ans;
}
int solve4(int x,int l,int r,int d)//前驱
{
if(s[x].l==l and s[x].r==r)
{
int t=findQ(x,d);
return (t==NUL)?0:t;
}
int lc=s[x].lc,rc=s[x].rc,mid=mid=(s[x].l+s[x].r)/2;
if(r<=mid) return solve4(lc,l,r,d);
if(l>mid) return solve4(rc,l,r,d);
return mymax( solve4(lc,l,mid,d),solve4(rc,mid+1,r,d) );
}
int solve5(int x,int l,int r,int d)//后继
{
if(s[x].l==l and s[x].r==r)
{
int t=findH(x,d);
return (t==NUL)?0x3f3f3f3f:t;
}
int lc=s[x].lc,rc=s[x].rc,mid=(s[x].l+s[x].r)/2;
if(r<=mid) return solve5(lc,l,r,d);
if(l>mid) return solve5(rc,l,r,d);
return mymin( solve5(lc,l,mid,d),solve5(rc,mid+1,r,d) );
}
//*******************主函数*******************
int main()
{
memset(root,NUL,sizeof(root));
int n,m;scanf("%d%d",&n,&m);
for(int i=1;i<=n;i++) scanf("%d",&num[i]);
build(1,n);
while(m--)
{
int op;scanf("%d",&op);
if(op==3)
{
int pos,d;scanf("%d%d",&pos,&d);
change(1,pos,num[pos],d);num[pos]=d;
}
else
{
int l,r,k;scanf("%d%d%d",&l,&r,&k);
if(op==1) printf("%d\n",solve1(1,l,r,k)+1);
if(op==2) printf("%d\n",solve2(l,r,k));
if(op==4) printf("%d\n",solve4(1,l,r,k));
if(op==5) printf("%d\n",solve5(1,l,r,k));
}
}
}

分析2

然鹅Bzoj的评论里面有这样几句话:
“用平衡树的都是二逼青年”
“有智慧的长者都写主席树”
so,依旧被D飞
赶紧复习一波主席树

哦补充一下,我在打的时候突然想到一个问题:
假如r的lowbit覆盖了l-1,那么它不就会turn两次了?
后来经提醒发现,这种turn两次的情况理论上虽然是错的,
但因为他们都是被覆盖两次的,所以求前缀和的时候刚好抵消了……

优点就是少了一百行……,速度还快了三倍!

代码2

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
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
//Zory-2018
//*******************主函数******************
#include<cstdio>
#include<cstring>
#include<cmath>
#include<queue>
#include<vector>
#include<algorithm>
#ifdef WIN32
#define BIGN "%I64d"
#else
#define BIGN "%lld"
#endif
using namespace std;
typedef long long ll;
//*******************全局常量*******************
const int MAXN=50010,MAXM=50010;
const int INF=0x7fffffff;
//*******************全局定义*******************
int n;
int rx;
int num[MAXN+MAXM];
int now[MAXN];
//*******************主席树******************
struct Nod
{
int c;
int lc,rc;
Nod() {c=lc=rc=0;}
}p[MAXN*20*10];
int rt[MAXN];
int ust[MAXN];
int cnt=0;
void add(int &x,int l,int r,int pos,int c)
{
if(!x) x=++cnt;
p[x].c+=c;
if(l==r) return;
int mid=(l+r)>>1;
if(pos<=mid) add(p[x].lc,l,mid,pos,c);
else add(p[x].rc,mid+1,r,pos,c);
}
//*******************树状数组******************
int lowbit(int x) {return x&(-x);}
void change(int x,int pos,int c)
{
while(x<=n)
{
add(rt[x],1,rx,pos,c);
x+=lowbit(x);
}
}
int getlsum(int x)
{
int s=0;
while(x>=1)
{
s+=p[ p[ust[x]].lc ].c;
x-=lowbit(x);
}
return s;
}
int getsum(int x)
{
int s=0;
while(x>=1)
{
s+=p[ust[x]].c;
x-=lowbit(x);
}
return s;
}
int getrsum(int x)
{
int s=0;
while(x>=1)
{
s+=p[ p[ust[x]].rc ].c;
x-=lowbit(x);
}
return s;
}
void turn(int x,int tn)
{
while(x>=1)
{
if(tn==0) ust[x]=rt[x];
if(tn==-1) ust[x]=p[ ust[x] ].lc;
if(tn==1) ust[x]=p[ ust[x] ].rc;
x-=lowbit(x);
}
}
//*******************实现******************
struct Qes
{
int op;
int x,y,k;
}q[MAXM];
int qian;
int ask1(int x,int y,int l,int r,int k)
{
if(l==r) return qian;
int mid=(l+r)>>1;
if(k<=mid)
{
turn(x-1,-1);turn(y,-1);
return ask1(x,y,l,mid,k);
}
else
{
qian+=getlsum(y)-getlsum(x-1);
turn(x-1,1);turn(y,1);
return ask1(x,y,mid+1,r,k);
}
}
int solve1(int l,int r,int k)//k在区间内的排名
{
turn(l-1,0);turn(r,0);
qian=0;
return ask1(l,r,1,rx,k)+1;
}
int ask2(int x,int y,int l,int r,int k)
{
if(l==r) return num[l];
int ls=getlsum(y)-getlsum(x-1);
int mid=(l+r)>>1;
if(k<=ls)
{
turn(x-1,-1);turn(y,-1);
return ask2(x,y,l,mid,k);
}
else
{
turn(x-1,1);turn(y,1);
return ask2(x,y,mid+1,r,k-ls);
}
}
int solve2(int l,int r,int k)//区间内排名为k的值
{
turn(l-1,0);turn(r,0);
return ask2(l,r,1,rx,k);
}
void solve3(int pos,int k)//修改
{
change(pos,now[pos],-1);
now[pos]=k;
change(pos,now[pos],1);
}
int solve4(int l,int r,int k)//查询k在区间内的前驱,没有则-INF
{
int t=solve1(l,r,k)-1;
if(t==0) return -INF;
return solve2(l,r,t);
}
int solve5(int l,int r,int k)//查询k在区间内的后继,没有则INF
{
int t=solve1(l,r,k+1)-1;
if(t==(r-l+1)) return INF;
return solve2(l,r,t+1);
}
//*******************离散化******************
struct Lsh
{
int x,id,z;
}a[MAXN+MAXM];
bool cmp(Lsh a,Lsh b) {return a.x<b.x;}
void lsh(int all)
{
sort(a+1,a+all+1,cmp);
rx=0;a[0].x=-INF;
for(int i=1;i<=all;i++)
{
if(a[i-1].x!=a[i].x) num[++rx]=a[i].x;//debug
if(a[i].id<=n) a[a[i].id].z=rx;
else q[a[i].id-n].k=rx;
}
}
//*******************主函数******************
int main()
{
int m;scanf("%d%d",&n,&m);
for(int i=1;i<=n;i++) scanf("%d",&a[i].x),a[i].id=i;
int all=n;
for(int i=1;i<=m;i++)
{
scanf("%d%d",&q[i].op,&q[i].x);
if(q[i].op==2) scanf("%d%d",&q[i].y,&q[i].k);
else
{
all++;
if(q[i].op!=3) scanf("%d",&q[i].y);
scanf("%d",&a[all].x);
a[all].id=n+i;
}
}
lsh(all);
for(int i=1;i<=n;i++) now[i]=a[i].z,change(i,now[i],1);
for(int i=1;i<=m;i++)
{
if(q[i].op==1) printf("%d\n",solve1(q[i].x,q[i].y,q[i].k));
if(q[i].op==2) printf("%d\n",solve2(q[i].x,q[i].y,q[i].k));
if(q[i].op==3) solve3(q[i].x,q[i].k);
if(q[i].op==4) printf("%d\n",solve4(q[i].x,q[i].y,q[i].k));
if(q[i].op==5) printf("%d\n",solve5(q[i].x,q[i].y,q[i].k));
}
}

本文基于 知识共享署名-相同方式共享 4.0 国际许可协议发布
本文地址:http://zory.cf/posts/d7e9.html
转载请注明出处,谢谢!

哪怕是一杯奶茶,也将鼓励我继续创作!
0%