[TYVJ1730]二逼平衡树 - 天一阁 - 310694

记录编号	310694	评测结果	AAAAAAAAAA
题目名称	[TYVJ1730]二逼平衡树	最终得分	100
用户昵称	天一阁	是否通过	通过
代码语言	C++	运行时间	3.478 s
提交时间	2016-09-22 21:42:51	内存使用	6.04 MiB
显示代码纯文本
#include <iostream>
#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <ctime>

#define N 50010
#define INF 0x3f3f3f3f
#define elif else if
#define l(x) ch[x][0]
#define r(x) ch[x][1]

using namespace std;

struct node{
	node *ch[2];
	int sum,r,cnt,v;
	node* init(int x);
	void update(){
		sum=cnt;
		if(ch[0]!=NULL) sum+=ch[0]->sum;
		if(ch[1]!=NULL) sum+=ch[1]->sum;
	}
}Null;

int a[N],n,m,totn,ch[N<<1][2];
bool flag;

inline void qread(int &x){
	char ch;
	int k=1;
	while(!isdigit(ch=getchar()))
		if(ch=='-') k=-1;
	x=ch-'0';
	while(isdigit(ch=getchar()))
		x=(x<<1)+(x<<3)+ch-'0';
	x*=k;
}

node *root[N*25];

node* node::init(int x){
	v=x;
	r=rand();
	sum=1;
	cnt=1;
	ch[0]=ch[1]=&Null;
	return this;
}

void rot(node* &o,int x){
	node* tmp=o->ch[x];
	o->ch[x]=tmp->ch[x^1];
	tmp->ch[x^1]=o;
	o->update(); o=tmp;
	o->update();
}

void insert(node* &o,int x){
	if(o==&Null){
		o=new node();
		o=o->init(x);
	}
	else if(o->v==x) o->cnt++,o->sum++;
	else{
  		int d= x<=o->v? 0:1;
		insert(o->ch[d],x);
		o->update();
		if(o->ch[d]->r > o->r) rot(o,d);
	}
}

int qrank(node* &o,int x){
	if(o==&Null) return 0;
	if(o->v==x){
		flag=true;
		return o->ch[0]->sum;
	}
	if(x<o->v) return qrank(o->ch[0],x);
	return o->ch[0]->sum+qrank(o->ch[1],x)+o->cnt;
}

void del(node* &o,int x){
	if(o->v==x){
		if(o->cnt>1) o->cnt--,o->sum--;
		else{
			if(o->ch[0]==&Null && o->ch[1]==&Null) o=&Null;
			elif(o->ch[0]==&Null) o=o->ch[1];
			elif(o->ch[1]==&Null) o=o->ch[0];
			else{
				int d2 = (o->ch[0]->r >
					o->ch[1]->r?1:0);
				rot(o,d2^1);
				del(o->ch[d2],x);
			}
		}
	}
	else{
		if(x<=o->v) del(o->ch[0],x);
		else del(o->ch[1],x);
	}
	if(o!=&Null) o->update();
}

int qpre(node* &o,int x){	//x的前驱 
	if(o==&Null) return 0;
	if(x>o->v) return max(o->v,qpre(o->ch[1],x));
	return qpre(o->ch[0],x);
}

int qsuc(node* &o,int x){	//x的后继 
	if(o==&Null) return INF;
	if(x<o->v) return min(o->v,qsuc(o->ch[0],x));
	return qsuc(o->ch[1],x);
}

int build(int l,int r){
	int x=++totn;
	root[x]=&Null;
    for(int i=l;i<=r;i++){
		insert(root[x],a[i]);
	}
	if(l==r) return x;
	int mid=(l+r)>>1;
	l(x)=build(l,mid);
	r(x)=build(mid+1,r);
	return x;
}

int askk(int x,int l,int r,int ql,int qr,int qv){
	if(ql<=l && r<=qr) return qrank(root[x],qv);
	int mid=(l+r)>>1,ans=0;
	if(ql<=mid) ans+=askk(l(x),l,mid,ql,qr,qv);
	if(mid<qr) ans+=askk(r(x),mid+1,r,ql,qr,qv);
	return ans;
}

inline int ask_rank(int l,int r,int x){
	node* tmp=root[1];
	flag=0;
	int t=askk(1,1,n,l,r,tmp->v),ans;
	while(tmp!=&Null){
		if(t+1<=x){
			if(flag) ans=tmp->v;
			tmp=tmp->ch[1];
   			if(tmp!=&Null){
				flag=0;
				t=askk(1,1,n,l,r,tmp->v);
      		}
		}
		else{
            tmp=tmp->ch[0];
			if(tmp!=&Null){
				flag=0;
				t=askk(1,1,n,l,r,tmp->v);
   			}
		}
	}
	return ans;
}

void change(int x,int l,int r,int qx,int qw){
	del(root[x],a[qx]);
	insert(root[x],qw);
	if(l==r) return;
	int mid=(l+r)>>1;
	if(qx<=mid) change(l(x),l,mid,qx,qw);
	else change(r(x),mid+1,r,qx,qw);
}

int ask_pre(int x,int l,int r,int ql,int qr,int qx){
	if(ql<=l && r<=qr) return qpre(root[x],qx);
	int mid=(l+r)>>1,ans=-INF;
	if(ql<=mid) ans=max(ans,ask_pre(l(x),l,mid,ql,qr,qx));
	if(mid<qr) ans=max(ans,ask_pre(r(x),mid+1,r,ql,qr,qx));
	return ans;
}

int ask_suc(int x,int l,int r,int ql,int qr,int qx){
	if(ql<=l && r<=qr) return qsuc(root[x],qx);
	int mid=(l+r)>>1,ans=INF;
	if(ql<=mid) ans=min(ans,ask_suc(l(x),l,mid,ql,qr,qx));
	if(mid<qr) ans=min(ans,ask_suc(r(x),mid+1,r,ql,qr,qx));
	return ans;
}

int main(){
	freopen("psh.in","r",stdin);
	freopen("psh.out","w",stdout);
	srand(time(NULL));
	scanf("%d%d",&n,&m);
	for(int i=1;i<=n;i++) qread(a[i]);
	build(1,n);
	for(int i=1,cmd,x,y,z;i<=m;i++){
		qread(cmd);
		if(cmd==1){
			qread(x);
			qread(y);
			qread(z);
			printf("%d\n",askk(1,1,n,x,y,z)+1);
		}
		elif(cmd==2){
            qread(x);
			qread(y);
			qread(z);
            printf("%d\n",ask_rank(x,y,z));
		}
		elif(cmd==3){
			qread(x);
			qread(y);
			change(1,1,n,x,y);
			a[x]=y;
		}
		elif(cmd==4){
			qread(x);
			qread(y);
			qread(z);
			printf("%d\n",ask_pre(1,1,n,x,y,z));
		}
		else{
			qread(x);
			qread(y);
			qread(z);
			printf("%d\n",ask_suc(1,1,n,x,y,z));
		}
	}
	return 0;
}
/*
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
*/