（WA）
by zhoukangyang @ 2020-07-06 12:26:24
禁止wyy回复
by zhoukangyang @ 2020-07-06 12:27:49
upd: 0pts
```
#include<bits/stdc++.h>
#define N 50009
#define inf 2147483647
using namespace std;
const int maxn = 1e8;
int n,m,head[N<<5],s[N<<5],ls[N<<5],rs[N<<5],tot=1;
int ch[N<<9][2],val[N<<9],key[N<<9],siz[N<<9],total,splx,sply,splz;
void upd(int now) {
siz[now] = siz[ch[now][0]] + siz[ch[now][1]] + 1;
}
void split(int now,int k,int &x,int &y) {
if(!now) x = y = 0;
else {
if(val[now] <= k) x = now , split(ch[now][1],k,ch[now][1],y);
else y = now , split(ch[now][0],k,x,ch[now][0]);
upd(now);
}
}
int merge(int x,int y) {
if(!x||!y) return x+y;
if(key[x] > key[y]) {
ch[x][1] = merge(ch[x][1],y);
return x;
}
else {
ch[y][0] = merge(x,ch[y][0]);
return y;
}
}
int new_node(int value) {
++total,val[total] = value , siz[total] = 1 ,key[total] = rand();
return total;
}
int findl(int id) {
if(ls[id] == 0) ++tot,ls[id] = tot;
return ls[id];
}
int findr(int id) {
if(rs[id] == 0) ++tot,rs[id] = tot;
return rs[id];
}
void add(int L,int R,int now,int id,int k,int flag) {
int mid = (L+R)/2;
if(flag) split(head[id],k-1,splx,sply),head[id]=merge(splx,merge(new_node(k),sply));
else split(head[id],k-1,splx,sply),split(sply,k,sply,splz),head[id]=merge(splx,splz);
if(L==R) return;
else if(now<=mid) add(L,mid,now,findl(id),k,flag);
else add(mid+1,R,now,findr(id),k,flag);
}
int kth(int L,int R,int now,int id,int l,int r) {
int mid = (L+R)/2,aans;
if(L==R) return 1;
else if(now <= mid) return kth(L,mid,now,findl(id),l,r);
if(!ls[id]) return kth(mid+1,R,now,findr(id),l,r);
split(head[ls[id]],r,splx,sply),split(splx,l-1,splx,splz),aans=siz[splz];
head[ls[id]] = merge(merge(splx,splz),sply);
return aans+kth(mid+1,R,now,findr(id),l,r);
}
int ukth(int L,int R,int id,int now,int l,int r) {
int mid = (L+R)/2,aans;
if(L==R) return L;
if(!ls[id]) return ukth(mid+1,R,findr(id),now,l,r);
split(head[ls[id]],r,splx,sply),split(splx,l-1,splx,splz),aans=siz[splz];
head[ls[id]] = merge(merge(splx,splz),sply);
if(now>aans) return ukth(mid+1,R,findr(id),now-aans,l,r);
else return ukth(L,mid,findl(id),now,l,r);
}
int main() {
int opt,l,r,k,emm;
srand(1919810);
scanf("%d%d",&n,&m);
for(int i = 1; i <= n; i++) scanf("%d",&s[i]),add(1,n,s[i],1,i,1);
while(m--) {
scanf("%d%d%d",&opt,&l,&r);
if(opt == 1) scanf("%d",&k),printf("%d\n",kth(1,n,k,1,l,r));
else if(opt == 2) scanf("%d",&k),printf("%d\n",ukth(1,n,1,k,l,r));
else if(opt == 3) add(1,n,s[l],1,l,0),s[l]=r,add(1,n,s[l],1,l,1);
else {
scanf("%d",&k),emm = kth(1,n,k+(opt==5),1,l,r);
if(opt == 4) printf("%d\n",emm==1?-inf:ukth(1,n,1,emm-1,l,r));
else printf("%d\n",emm==n+1?inf:ukth(1,n,1,emm,l,r));
}
}
return 0;
};
}
```
by zhoukangyang @ 2020-07-06 12:57:05
wyy回复: 您已经是神仙了,要学会自己调题,尽量不要天天发帖求助.
by Froggy @ 2020-07-06 13:05:29
@[Froggy](/user/100285) wyy回复:我大部分题目都是自己调的，1.5个小时调不出来才会发帖(
by zhoukangyang @ 2020-07-06 13:10:24
还有我只是一只蒟蒻/kk
by zhoukangyang @ 2020-07-06 13:10:58
您才是神仙(
by zhoukangyang @ 2020-07-06 13:11:17
upd upd : 10pts!
```
#include<bits/stdc++.h>
#define N 50009
#define inf 2147483647
using namespace std;
const int maxn = 1e8;
int n,m,head[N<<5],s[N<<5],ls[N<<5],rs[N<<5],tot=1;
int ch[N<<9][2],val[N<<9],key[N<<9],siz[N<<9],total,splx,sply,splz;
void upd(int now) {
siz[now] = siz[ch[now][0]] + siz[ch[now][1]] + 1;
}
void split(int now,int k,int &x,int &y) {
if(!now) x = y = 0;
else {
if(val[now] <= k) x = now , split(ch[now][1],k,ch[now][1],y);
else y = now , split(ch[now][0],k,x,ch[now][0]);
upd(now);
}
}
int merge(int x,int y) {
if(!x||!y) return x+y;
if(key[x] > key[y]) {
ch[x][1] = merge(ch[x][1],y);
return x;
}
else {
ch[y][0] = merge(x,ch[y][0]);
return y;
}
}
int new_node(int value) {
++total,val[total] = value , siz[total] = 1 ,key[total] = rand();
return total;
}
int findl(int id) {
if(ls[id] == 0) ++tot,ls[id] = tot;
return ls[id];
}
int findr(int id) {
if(rs[id] == 0) ++tot,rs[id] = tot;
return rs[id];
}
void add(int L,int R,int now,int id,int k,int flag) {
int mid = (L+R)/2;
if(flag) split(head[id],k-1,splx,sply),head[id]=merge(splx,merge(new_node(k),sply));
else split(head[id],k-1,splx,sply),split(sply,k,sply,splz),head[id]=merge(splx,splz);
if(L==R) return;
else if(now<=mid) add(L,mid,now,findl(id),k,flag);
else add(mid+1,R,now,findr(id),k,flag);
}
int kth(int L,int R,int now,int id,int l,int r) {
int mid = (L+R)/2,aans;
if(L==R) return 1;
else if(now <= mid) return kth(L,mid,now,findl(id),l,r);
if(!ls[id]) return kth(mid+1,R,now,findr(id),l,r);
split(head[ls[id]],r,splx,sply),split(splx,l-1,splx,splz),aans=siz[splz];
head[ls[id]] = merge(merge(splx,splz),sply);
return aans+kth(mid+1,R,now,findr(id),l,r);
}
int ukth(int L,int R,int id,int now,int l,int r) {
int mid = (L+R)/2,aans;
if(L==R) return L;
if(!ls[id]) return ukth(mid+1,R,findr(id),now,l,r);
split(head[ls[id]],r,splx,sply),split(splx,l-1,splx,splz),aans=siz[splz];
head[ls[id]] = merge(merge(splx,splz),sply);
if(now>aans) return ukth(mid+1,R,findr(id),now-aans,l,r);
else return ukth(L,mid,findl(id),now,l,r);
}
int main() {
int opt,l,r,k,emm;
srand(1919810);
scanf("%d%d",&n,&m);
for(int i = 1; i <= n; i++) scanf("%d",&s[i]),add(1,maxn,s[i],1,i,1);
while(m--) {
scanf("%d%d%d",&opt,&l,&r);
if(opt == 1) scanf("%d",&k),printf("%d\n",kth(1,maxn,k,1,l,r));
else if(opt == 2) scanf("%d",&k),printf("%d\n",ukth(1,maxn,1,k,l,r));
else if(opt == 3) add(1,maxn,s[l],1,l,0),s[l]=r,add(1,maxn,s[l],1,l,1);
else {
scanf("%d",&k),emm = kth(1,maxn,k+(opt==5),1,l,r);
if(opt == 4) printf("%d\n",emm==1?-inf:ukth(1,maxn,1,emm-1,l,r));
else printf("%d\n",emm==r-l+2?inf:ukth(1,maxn,1,emm,l,r));
}
}
return 0;
}
```
by zhoukangyang @ 2020-07-06 13:33:30
wyy回复: 树套树不都是自己调的吗（
by 囧仙 @ 2020-07-06 15:29:59