记录编号	538093	评测结果	AAAAAAAAAA
题目名称	[TYVJ1730]二逼平衡树	最终得分	100
用户昵称	Hale	是否通过	通过
代码语言	C++	运行时间	5.402 s
提交时间	2019-07-21 21:49:59	内存使用	67.07 MiB

#include<bits/stdc++.h>
using namespace std;
const int N=1e5+7;
const int M=2e6+7;
const int INF=0x7f7f7f7f;
int m,n,k,p,cnt;
int l[M],r[M],pri[M],sz[M],v[M],a[M];
int read()
{
	int x=0,f=1;char ch=getchar();
	while (ch<'0'||ch>'9') {if (ch=='-') f=-1;ch=getchar();}
	while (ch>='0'&&ch<='9') {x=x*10+ch-'0';ch=getchar();}
	return x*f;
}
struct FHQ_treap
{
	int root,x,y,z;
	int new_node(int a) {cnt++;sz[cnt]=1;v[cnt]=a;pri[cnt]=rand();return cnt;}
	void push_up(int x) {sz[x]=sz[l[x]]+sz[r[x]]+1;}
	int merge(int x,int y)
	{
		if (!x||!y) return x+y;
		if (pri[x]<pri[y]) {r[x]=merge(r[x],y);push_up(x);return x;}
		else {l[y]=merge(x,l[y]);push_up(y);return y;}
	}
	void split(int now,int k,int &x,int &y)
	{
		if (!now) x=0,y=0;
		else 
		{
			if (v[now]<=k) x=now,split(r[now],k,r[x],y);
			else y=now,split(l[now],k,x,l[y]);
			push_up(now);
		}
	}
	void insert(int a) {split(root,a,x,y);root=merge(merge(x,new_node(a)),y);}
	void Delete(int a) {split(root,a,x,z);split(x,a-1,x,y);y=merge(l[y],r[y]);root=merge(merge(x,y),z);}
	int K_th(int now,int k)
	{
		while (true)
		{
			if (sz[l[now]]>=k) now=l[now];
			else if (k==sz[l[now]]+1) return now;
			else k-=sz[l[now]]+1,now=r[now];
		}
	}
	int Rank(int a) {split(root,a-1,x,y);int ans=sz[x]+1;root=merge(x,y);return ans;}
	int upper(int a) {split(root,a,x,y);int ans=sz[y]?v[K_th(y,1)]:INF;root=merge(x,y);return ans;}
	int lower(int a) {split(root,a-1,x,y);int ans=sz[x]?v[K_th(x,sz[x])]:-INF;root=merge(x,y);return ans;}
	void build(int x,int y) {for (int i=x;i<=y;i++) insert(a[i]);} 
} FT[N<<2];
#define ls (p<<1)
#define rs (p<<1|1)
#define mid ((l+r)>>1)
struct segment_tree
{
	int root[N<<2];
	void build(int l,int r,int p)
	{
		FT[p].build(l,r);
		if (l!=r) build(l,mid,ls),build(mid+1,r,rs);
	}
	int Q_Rank(int nl,int nr,int p,int l,int r,int val)
	{
		if (r<nl||l>nr) return 0;
		if (nl<=l&&r<=nr) return FT[p].Rank(val)-1;
		return Q_Rank(nl,nr,ls,l,mid,val)+Q_Rank(nl,nr,rs,mid+1,r,val);
	}
	int Q_val(int l,int r,int rak)
	{
		int x=0,y=1e8,ans=-1;
		while (x<=y)
		{
			int M=(x+y)>>1;
			if (Q_Rank(l,r,1,1,n,M)+1<=rak) ans=M,x=M+1;
			else y=M-1;
		}
		return ans;
	}
	void update(int l,int r,int p,int pos,int val)
	{
		FT[p].Delete(a[pos]);
		FT[p].insert(val);
		if (l!=r)
		{
			if (pos<=mid) update(l,mid,ls,pos,val);
			else update(mid+1,r,rs,pos,val);
		}
	}
	int Lower(int nl,int nr,int p,int l,int r,int val)
	{
		if (nr<l||r<nl) return -INF;
		if (nl<=l&&r<=nr) return FT[p].lower(val);
		return max(Lower(nl,nr,ls,l,mid,val),Lower(nl,nr,rs,mid+1,r,val));
	}
	int Upper(int nl,int nr,int p,int l,int r,int val)
	{
		if (nr<l||r<nl) return INF;
		if (nl<=l&&r<=nr) return FT[p].upper(val);
		return min(Upper(nl,nr,ls,l,mid,val),Upper(nl,nr,rs,mid+1,r,val));
	}
} ST;
int main()
{
	freopen("psh.in","r",stdin);
	freopen("psh.out","w",stdout);
	srand((unsigned)time(NULL));
	n=read();int Q=read();
	for (int i=1;i<=n;i++) a[i]=read();
	ST.build(1,n,1);
	int opt,l,r,val,pos,k;
	while (Q--)
	{
		opt=read();
		if (opt==1) {l=read(),r=read(),val=read();printf("%d\n",ST.Q_Rank(l,r,1,1,n,val)+1);}
		else if (opt==2) {l=read(),r=read(),k=read();printf("%d\n",ST.Q_val(l,r,k));}
		else if (opt==3) {pos=read();val=read();ST.update(1,n,1,pos,val);a[pos]=val;}
		else if (opt==4) {l=read(),r=read(),val=read();printf("%d\n",ST.Lower(l,r,1,1,n,val));}
		else if (opt==5) {l=read(),r=read(),val=read();printf("%d\n",ST.Upper(l,r,1,1,n,val));}
	}
	return 0;
}