学步园

http://www.lydsy.com/JudgeOnline/problem.php?id=3196

线段树套平衡树

被虐了两个小时，还是namespace大法好！看到zky用的struct，不过据我测试会影响速度。。。。。

发现理解起来比神马主席树好多了，感觉树套树就是把平衡树的功能区间化了，而且必须满足减法规则

就是代码量有点感人。。。。。。

个人感觉我的代码过程比较清晰

空间不会算re了一次

二分边界没有改wa了一次

求空间大小如何计算。？

//#define _TEST _TEST
#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <iostream>
#include <cmath>
#include <algorithm>
using namespace std;
/************************************************
Code By willinglive    Blog:http://willinglive.cf
************************************************/
#define rep(i,l,r) for(int i=l,___t=(r);i<=___t;i++)
#define per(i,r,l) for(int i=r,___t=(l);i>=___t;i--)
#define MS(arr,x) memset(arr,x,sizeof(arr))
#define LL long long
#define INE(i,u,e) for(int i=head[u];~i;i=e[i].next)
inline const int getint()
{
    int r=0,k=1;char c=getchar();
    for(;c<'0'||c>'9';c=getchar())if(c=='-')k=-1;
    for(;c>='0'&&c<='9';c=getchar())r=r*10+c-'0';
    return k*r;
}
/////////////////////////////////////////////////
int n,m;
int a[50010],ans;
/////////////////////////////////////////////////
namespace Treap
{////////////////////////////////
#define LS T[o].l
#define RS T[o].r
int root[131100],sz;
struct data{int l,r,s,rnd,cnt,w;}T[2000000];
void update(int o){T[o].s=T[LS].s+T[RS].s+T[o].cnt;}
void l_rot(int &o){int t=RS;RS=T[t].l;T[t].l=o;T[t].s=T[o].s;update(o);o=t;}
void r_rot(int &o){int t=LS;LS=T[t].r;T[t].r=o;T[t].s=T[o].s;update(o);o=t;}
void insert(int &o,int x)
{
	if(o==0)
	{
		o=++sz; T[o].s=T[o].cnt=1; T[o].rnd=rand()*rand(); T[o].w=x;
		return;
	}
	T[o].s++;
	if(x>T[o].w)
	{
		insert(RS,x);
		if(T[o].rnd>T[RS].rnd) l_rot(o);
	}
	else if(x<T[o].w)
	{
		insert(LS,x);
		if(T[o].rnd>T[LS].rnd) r_rot(o);
	}
	else T[o].cnt++;
}
void del(int &o,int x)
{
	if(o==0) return;
	if(T[o].w==x)
	{
		if(T[o].cnt>1) T[o].cnt--,T[o].s--;
		else if(LS==0||RS==0) o=LS+RS;
		else if(T[LS].rnd<T[RS].rnd) r_rot(o),del(o,x);
		else l_rot(o),del(o,x);
		return;
	}
	T[o].s--;
	if(T[o].w<x) del(RS,x);
	else del(LS,x);
}
int getrank(int o,int x)
{
	if(o==0) return 1;
	if(x<T[o].w) return getrank(LS,x);
	else if(x>T[o].w) return T[LS].s+T[o].cnt+getrank(RS,x);
	else return T[LS].s+1;
}
void getbefore(int o,int x)
{
	if(o==0)return;
	if(T[o].w<x) ans=T[o].w,getbefore(RS,x);
	else getbefore(LS,x);
}
void getafter(int o,int x)
{
	if(o==0)return;
	if(T[o].w>x) ans=T[o].w,getafter(LS,x);
	else getafter(RS,x);
}
#undef LS
#undef RS
}////////////////////////////////
namespace SegTree
{////////////////////////////////
#define LS o<<1,L,mid
#define RS o<<1|1,mid+1,R
void insert(int pos,int x,int o,int L,int R)
{
	Treap::insert(Treap::root[o],x);
	if(L==R) return;
	int mid=L+R>>1;
	if(pos<=mid) insert(pos,x,LS);
	else insert(pos,x,RS);
}
int getrank(int l,int r,int k,int o,int L,int R)
{
	if(l<=L && R<=r)
		return Treap::getrank(Treap::root[o],k);
	int mid=L+R>>1;
	if(r<=mid) return getrank(l,r,k,LS);
	else if(l>mid) return getrank(l,r,k,RS);
	else return getrank(l,mid,k,LS)+getrank(mid+1,r,k,RS)-1;
}
int getnum(int l,int r,int k)
{
	int ll=0,rr=100000000,mid;
	while(ll<rr)
	{
		mid=ll+rr+1>>1;
		if(getrank(l,r,mid,1,1,n)<=k) ll=mid;
		else rr=mid-1;
	}
	return ll;
}
void modify(int pos,int x,int t,int o,int L,int R)
{
	using namespace Treap;
	Treap::del(root[o],t); Treap::insert(root[o],x);
	if(L==R) return;
	int mid=L+R>>1;
	if(pos<=mid) modify(pos,x,t,LS);
	else modify(pos,x,t,RS);
}
int getbefore(int l,int r,int k,int o,int L,int R)
{
	using namespace Treap;
	if(l<=L && R<=r)
		return Treap::getbefore(root[o],k),ans;
	int mid=L+R>>1;
	if(r<=mid) return getbefore(l,r,k,LS);
	else if(l>mid) return getbefore(l,r,k,RS);
	return max(getbefore(l,r,k,LS),getbefore(l,r,k,RS));
}
int getafter(int l,int r,int k,int o,int L,int R)
{
	using namespace Treap;
	if(l<=L && R<=r)
		return Treap::getafter(root[o],k),ans;
	int mid=L+R>>1;
	if(r<=mid) return getafter(l,r,k,LS);
	else if(l>mid) return getafter(l,r,k,RS);
	return min(getafter(l,r,k,LS),getafter(l,r,k,RS));
}
#undef LS
#undef RS
}////////////////////////////////
/////////////////////////////////////////////////
void input()
{
    n=getint(); m=getint();
    rep(i,1,n) a[i]=getint();
}
void solve()
{
	using namespace SegTree;
    int op,l,r,pos,k;
    rep(i,1,n) insert(i,a[i],1,1,n);
	while(m--)
    {
    	scanf("%d",&op);
    	if(op==1)
    	{
    		scanf("%d%d%d",&l,&r,&k);
    		printf("%d\n",getrank(l,r,k,1,1,n));
    	}
    	else if(op==2)
    	{
    		scanf("%d%d%d",&l,&r,&k);
    		printf("%d\n",getnum(l,r,k));
    	}
    	else if(op==3)
    	{
    		scanf("%d%d",&pos,&k);
    		modify(pos,k,a[pos],1,1,n); a[pos]=k;
    	}
    	else if(op==4)
    	{
    		scanf("%d%d%d",&l,&r,&k);
    		ans=0;
    		printf("%d\n",getbefore(l,r,k,1,1,n));
    	}
    	else if(op==5)
    	{
    		scanf("%d%d%d",&l,&r,&k);
    		ans=100000000;
    		printf("%d\n",getafter(l,r,k,1,1,n));
    	}
    }
}
/////////////////////////////////////////////////
int main()
{
    #ifndef _TEST
    freopen("std.in","r",stdin); freopen("std.out","w",stdout);
    #endif
    input();
    solve();
    return 0;
}