题解 P3380 【【模板】二逼平衡树（树套树）】
司马智泽
2018-05-08 20:39:18
啥玩意啊？咋回事啊？那咋整啊？——萌新三连
为啥没有暴力线段树套线段树啊。。。。。。
外面普通线段树，里面动态加点权值线段树，嗯，就是这么暴力。
上代码
```
//lgp3380
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
const int maxn=50000+9;
const int inf=2147483647;
int n,m,num[maxn],map[maxn<<1],cntm;
struct node{
int opt,l,r,k;
}ask[maxn];
struct seg_{
int lson,rson;
int sum,tmax,tmin;
}seg[maxn*200];
int root[maxn<<2],cnt;
void clear(int now){
seg[now].tmax=1;
seg[now].tmin=cntm;
}
void up(int now){
int lson=seg[now].lson,rson=seg[now].rson;
seg[now].tmax=max(seg[lson].tmax,seg[rson].tmax);
seg[now].tmin=min(seg[lson].tmin,seg[rson].tmin);
}
void ins2(int &now,int segl,int segr,int pos,int x){
if(now==0) now=++cnt;
seg[now].sum+=x;
if(segl==segr){
if(seg[now].sum==0) clear(now);
else seg[now].tmax=seg[now].tmin=segl;
return;
}
int mid=(segl+segr)>>1;
if(pos<=mid) ins2(seg[now].lson,segl,mid,pos,x);
else ins2(seg[now].rson,mid+1,segr,pos,x);
up(now);
}
void ins1(int now,int segl,int segr,int pos,int x,int y){
ins2(root[now],1,cntm,x,y);
if(segl==segr) return;
int mid=(segl+segr)>>1;
if(pos<=mid) ins1(now<<1,segl,mid,pos,x,y);
else ins1(now<<1|1,mid+1,segr,pos,x,y);
}
int tmp[maxn],ind;
void ppr(int now,int segl,int segr,int l,int r){
if(l<=segl&&segr<=r){
tmp[++ind]=root[now];
return;
}
int mid=(segl+segr)>>1;
if(l<=mid) ppr(now<<1,segl,mid,l,r);
if(mid+1<=r) ppr(now<<1|1,mid+1,segr,l,r);
}
int main(){
scanf("%d %d",&n,&m);
map[++cntm]=-inf,map[++cntm]=inf;
for(int i=1;i<=n;i++) scanf("%d",&num[i]),map[++cntm]=num[i];
for(int i=1;i<=m;i++){
node &in=ask[i];
scanf("%d",&in.opt);
if(in.opt==3){
scanf("%d %d",&in.l,&in.k);
}
else scanf("%d %d %d",&in.l,&in.r,&in.k);
if(in.opt!=2) map[++cntm]=in.k;
}
sort(map+1,map+cntm+1);
cntm=unique(map+1,map+cntm+1)-map-1;
for(int i=1;i<=n;i++) num[i]=lower_bound(map+1,map+cntm+1,num[i])-map;
for(int i=1;i<=m;i++) if(ask[i].opt!=2) ask[i].k=lower_bound(map+1,map+cntm+1,ask[i].k)-map;
clear(0);
for(int i=1;i<=n;i++){
ins1(1,1,n,i,num[i],1);
}
for(int ddf=1;ddf<=m;ddf++){
node &in=ask[ddf];
if(in.opt==1){
int ans=0;
ind=0;
ppr(1,1,n,in.l,in.r);
int l=1,r=cntm;
while(l!=r){
int mid=(l+r)>>1;
if(in.k<=mid){
for(int i=1;i<=ind;i++) tmp[i]=seg[tmp[i]].lson;
r=mid;
}
else{
for(int i=1;i<=ind;i++) ans+=seg[seg[tmp[i]].lson].sum,tmp[i]=seg[tmp[i]].rson;
l=mid+1;
}
}
printf("%d\n",ans+1);
}
else if(in.opt==2){
ind=0;
ppr(1,1,n,in.l,in.r);
int l=1,r=cntm;
while(l!=r){
int mid=(l+r)>>1;
int tmp2=0;
for(int i=1;i<=ind;i++) tmp2+=seg[seg[tmp[i]].lson].sum;
if(in.k<=tmp2){
for(int i=1;i<=ind;i++) tmp[i]=seg[tmp[i]].lson;
r=mid;
}
else {
for(int i=1;i<=ind;i++) tmp[i]=seg[tmp[i]].rson;
in.k-=tmp2;
l=mid+1;
}
}
printf("%d\n",map[l]);
}
else if(in.opt==3){
ins1(1,1,n,in.l,num[in.l],-1);
num[in.l]=in.k;
ins1(1,1,n,in.l,num[in.l],1);
}
else if(in.opt==4){
ind=0;
ppr(1,1,n,in.l,in.r);
int ans=1,l=1,r=cntm;
while(l!=r){
int mid=(l+r)>>1;
if(in.k<=mid){
for(int i=1;i<=ind;i++) tmp[i]=seg[tmp[i]].lson;
r=mid;
}
else {
for(int i=1;i<=ind;i++){
ans=max(ans,seg[seg[tmp[i]].lson].tmax);
tmp[i]=seg[tmp[i]].rson;
}
l=mid+1;
}
}
printf("%d\n",map[ans]);
}
else {
ind=0;
ppr(1,1,n,in.l,in.r);
int ans=cntm,l=1,r=cntm;
while(l!=r){
int mid=(l+r)>>1;
if(in.k<=mid){
for(int i=1;i<=ind;i++){
ans=min(ans,seg[seg[tmp[i]].rson].tmin);
tmp[i]=seg[tmp[i]].lson;
}
r=mid;
}
else {
for(int i=1;i<=ind;i++){
tmp[i]=seg[tmp[i]].rson;
}
l=mid+1;
}
}
printf("%d\n",map[ans]);
}
}
return 0;
}
```