记录编号	477415	评测结果	AAAAAAAAAA
题目名称	[TYVJ1730]二逼平衡树	最终得分	100
用户昵称	FoolMike	是否通过	通过
代码语言	C++	运行时间	2.024 s
提交时间	2017-12-02 21:26:56	内存使用	229.96 MiB

#include<bits/stdc++.h>
using namespace std;
const int N=5e4+10,M=2e7+10;
struct node{int l,r,v;}nd[M];
int n,m,id,a[N];
int add(int x,int l,int r,int p,int d){
	int now=++id;
	nd[now]=nd[x];
	nd[now].v+=d;
	if (l==r) return now;
	int mid=(l+r)>>1;
	if (p>mid) nd[now].r=add(nd[x].r,mid+1,r,p,d);
		else nd[now].l=add(nd[x].l,l,mid,p,d);
	return now;
}
int query(int x,int l,int r,int L,int R){
	if (l>=L&&r<=R) return nd[x].v;
	int mid=(l+r)>>1,ans=0;
	if (L<=mid) ans+=query(nd[x].l,l,mid,L,R);
	if (R>mid) ans+=query(nd[x].r,mid+1,r,L,R);
	return ans;
}
int root[N];
void add(int p,int v,int d){
	for (;p<=n;p+=p&-p) root[p]=add(root[p],0,1e8,v,d);
}
int rk(int p,int v){
	if (v<=0) return 0;
	v=min(v,(int)1e8+1);
	int ans=0;
	for (;p;p-=p&-p) ans+=query(root[p],0,1e8,0,v-1);
	return ans;
}
int rk(int l,int r,int v){
	return rk(r,v)-rk(l-1,v)+1;
}
int ql[N],cl,qr[N],cr;
int find(int l,int r,int v){
	for (cr=0;r;r-=r&-r) qr[++cr]=root[r];
	for (cl=0,l--;l;l-=l&-l) ql[++cl]=root[l];
	int L=0,R=1e8;
	while (L<R){
		int mid=(L+R)>>1,s=0;
		for (int i=1;i<=cl;i++) s-=nd[nd[ql[i]].l].v;
		for (int i=1;i<=cr;i++) s+=nd[nd[qr[i]].l].v;
		if (v<=s){
			for (int i=1;i<=cl;i++) ql[i]=nd[ql[i]].l;
			for (int i=1;i<=cr;i++) qr[i]=nd[qr[i]].l;
			R=mid;
		}
		else{
			for (int i=1;i<=cl;i++) ql[i]=nd[ql[i]].r;
			for (int i=1;i<=cr;i++) qr[i]=nd[qr[i]].r;
			L=mid+1;v-=s;
		}
	}
	return L;
}
int pre(int l,int r,int k){
	return find(l,r,rk(l,r,k)-1);
}
int suf(int l,int r,int k){
	return find(l,r,rk(l,r,k+1));
}
int main()
{
	freopen("psh.in","r",stdin);
	freopen("psh.out","w",stdout);
	scanf("%d%d",&n,&m);
	for (int i=1;i<=n;i++) scanf("%d",&a[i]),add(i,a[i],1);
	for (int i=1;i<=m;i++){
		int tp,l,r,v;
		scanf("%d%d%d",&tp,&l,&r);
		if (tp==3) add(l,a[l],-1),add(l,a[l]=r,1);
			else scanf("%d",&v);
		if (tp==1) printf("%d\n",rk(l,r,v));
		if (tp==2) printf("%d\n",find(l,r,v));
		if (tp==4) printf("%d\n",pre(l,r,v));
		if (tp==5) printf("%d\n",suf(l,r,v));
	}
	return 0;
}