记录编号	364657	评测结果	AAAAAAAAAA
题目名称	[TYVJ1730]二逼平衡树	最终得分	100
用户昵称	AntiLeaf	是否通过	通过
代码语言	C++	运行时间	1.805 s
提交时间	2017-01-17 16:25:18	内存使用	21.31 MiB

#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
const int maxn=65610;
const double alpha=0.7;
struct node{
	int data,size;
	node *ch[2];
	node(int d=0):data(d),size(1){}
	inline void refresh(){size=ch[0]->size+ch[1]->size+1;}
	inline int cmp(int x){return x==data?-1:x>data;}
}nodes[maxn<<4],*pool[maxn<<4],*null=nodes,*root[maxn<<1],*b[maxn];
void modify(int,int,int);
int query(int,int,int);
int qpred(int,int,int);
int qsucc(int,int,int);
void copy(node*&,node*);
void merge(int,node*);
void insert(int,int);
node *&insert(int,node*&);
void erase(int,node*&);
int order(int,node*);
int pred(int,node*);
int succ(int,node*);
int erase_min(node*&);
void travel(node*);
void rebuild(int,int,node*&);
int cnt,top=1;
int n,M=1,m,a[maxn],d,l,r,x;
int main(){
	freopen("psh.in","r",stdin);
	freopen("psh.out","w",stdout);
	null->size=0;
	null->ch[0]=null->ch[1]=null;
	for(int i=0;i<maxn<<4;i++)pool[i]=&nodes[i];
	scanf("%d%d",&n,&m);
	while(M<n+2)M<<=1;
	fill(root+1,root+(M<<1),null);
	for(int i=1;i<=n;i++){
		scanf("%d",&a[i]);
		*(root[i+M]=pool[top++])=node(a[i]);
		root[i+M]->ch[0]=root[i+M]->ch[1]=null;
	}
	for(int i=M-1;i;i--){
		copy(root[i],root[i<<1]);
		merge(i,root[i<<1|1]);
	}
	while(m--){
		scanf("%d",&d);
		if(d==1){
			scanf("%d%d%d",&l,&r,&x);
			printf("%d\n",query(l,r,x)+1);
		}
		else if(d==2){
			scanf("%d%d%d",&l,&r,&x);
			int L=0,R=1e8,M;
			while(L<=R){
				M=(L+R)>>1;
				if(query(l,r,M)>=x)R=M-1;
				else L=M+1;
			}
			printf("%d\n",R);
		}
		else if(d==3){
			scanf("%d%d",&x,&d);
			modify(x,a[x],d);
			a[x]=d;
		}
		else if(d==4){
			scanf("%d%d%d",&l,&r,&x);
			printf("%d\n",qpred(l,r,x));
		}
		else{
			scanf("%d%d%d",&l,&r,&x);
			printf("%d\n",qsucc(l,r,x));
		}
	}
	return 0;
}
void modify(int x,int u,int v){
	for(x+=M;x;x>>=1){
		erase(u,root[x]);
		insert(v,x);
	}
}
int query(int l,int r,int d){
	int ans=0;
	for(l+=M-1,r+=M+1;l^r^1;l>>=1,r>>=1){
		if(~l&1)ans+=order(d,root[l^1]);
		if(r&1)ans+=order(d,root[r^1]);
	}
	return ans;
}
int qpred(int l,int r,int d){
	int ans=1<<31;
	for(l+=M-1,r+=M+1;l^r^1;l>>=1,r>>=1){
		if(~l&1)ans=max(ans,pred(d,root[l^1]));
		if(r&1)ans=max(ans,pred(d,root[r^1]));
	}
	return ans;
}
int qsucc(int l,int r,int d){
	int ans=(~0u)>>1;
	for(l+=M-1,r+=M+1;l^r^1;l>>=1,r>>=1){
		if(~l&1)ans=min(ans,succ(d,root[l^1]));
		if(r&1)ans=min(ans,succ(d,root[r^1]));
	}
	return ans;
}
void copy(node *&x,node *y){
	if(y==null){
		x=null;
		return;
	}
	*(x=pool[top++])=node(y->data);
	copy(x->ch[0],y->ch[0]);
	copy(x->ch[1],y->ch[1]);
	x->refresh();
}
void merge(int x,node *y){
	if(y==null)return;
	insert(y->data,x);
	merge(x,y->ch[0]);
	merge(x,y->ch[1]);
}
void insert(int x,int rt){
	node *&y=insert(x,root[rt]);
	if(y!=null){
		cnt=0;
		travel(y);
		rebuild(1,cnt,y);
	}
}
node *&insert(int x,node *&rt){
	if(rt==null){
		*(rt=pool[top++])=node(x);
		rt->ch[0]=rt->ch[1]=null;
		return null;
	}
	int d=rt->cmp(x)==1;
	node *&y=insert(x,rt->ch[d]);
	rt->refresh();
	return (max(rt->ch[0]->size,rt->ch[1]->size)>rt->size*alpha)?rt:y;
}
void erase(int x,node *&rt){
	int d=rt->cmp(x);
	if(d==-1){
		if(rt->ch[0]!=null&&rt->ch[1]!=null)rt->data=erase_min(rt->ch[1]);
		else{
			pool[--top]=rt;
			rt=rt->ch[0]!=null?rt->ch[0]:rt->ch[1];
		}
	}
	else erase(x,rt->ch[d]);
	if(rt!=null)rt->refresh();
}
int order(int x,node *rt){
	int ans=0,d;
	while(rt!=null){
		if((d=x>rt->data))ans+=rt->ch[0]->size+1;
		rt=rt->ch[d];
	}
	return ans;
}
int pred(int x,node *rt){
	int ans=1<<31,d;
	while(rt!=null){
		if((d=x>rt->data))ans=rt->data;
		rt=rt->ch[d];
	}
	return ans;
}
int succ(int x,node *rt){
	int ans=(~0u)>>1,d;
	while(rt!=null){
		if((d=x<rt->data))ans=rt->data;
		rt=rt->ch[d^1];
	}
	return ans;
}
int erase_min(node *&x){
	if(x->ch[0]==null){
		pool[--top]=x;
		int tmp=x->data;
		x=x->ch[1];
		return tmp;
	}
	else{
		int tmp=erase_min(x->ch[0]);
		x->refresh();
		return tmp;
	}
}
void travel(node *x){
	if(x==null)return;
	travel(x->ch[0]);
	b[++cnt]=x;
	travel(x->ch[1]);
}
void rebuild(int l,int r,node *&x){
	if(l>r){
		x=null;
		return;
	}
	int mid=(l+r)>>1;
	x=b[mid];
	rebuild(l,mid-1,x->ch[0]);
	rebuild(mid+1,r,x->ch[1]);
	x->refresh();
}