[나무 커버 트 리] [BZOJ 3196] 이 강 밸 런 스 트 리.

[제목 설명]
질서 있 는 수열 을 유지 하기 위해 서 는 데이터 구조 (제목 참조) 를 써 야 합 니 다. 그 중에서 다음 과 같은 조작 을 제공 해 야 합 니 다. 1. x 구간 내 순 위 를 조회 합 니 다.2. 구간 내 순위 가 k 인 값 을 조회 합 니 다.3. 특정한 위치의 수 치 를 수정 합 니 다.4. x 가 구간 내 에서 의 전 추 를 조회 합 니 다 (전 추 는 x 보다 작고 최대 의 수 로 정의 합 니 다).5. 조회 x 구간 내 후계 (후계 정 의 는 x 보다 크 고 가장 작은 수).
[형식 입력]
첫 번 째 줄 의 두 개의 수 n, m 는 길이 가 n 인 질서 있 는 서열 과 m 개의 조작 을 나타 낸다.두 번 째 줄 은 n 개의 수가 있 는데 질서 있 는 서열 을 나타 낸다.다음은 m 줄 이 있 고 각 줄 의 첫 번 째 수 는 조작 유형 을 나타 낸다. 1. 그 다음 에 세 개의 수 l, r, x 는 x 가 구간 [l, r] 에서 의 순 위 를 조회 하 는 것 을 나타 낸다.2. 그 다음 에 세 개의 수 l, r, k 는 조회 구간 [l, r] 내 순위 가 k 인 수 를 나타 낸다.3. 그 다음 에 두 개의 pos 가 있 는데 x 는 pos 위치의 수 를 x 로 수정 하 는 것 을 나타 낸다.4. 그 다음 에 세 개의 수 l, r, x 는 조회 구간 [l, r] 내 x 의 전 추 를 나타 낸다.5. 그 다음 에 세 개의 수 l, r, x 는 조회 구간 [l, r] 내 x 의 후계 임 을 나타 낸다.
[출력 형식]
조작 1, 2, 4, 5 각 출력 한 줄 에 대해 조회 결 과 를 표시 합 니 다.
매우 전형 적 인 트 리 제목 인 데, 여 기 는 선분 트 리 의 균형 트 리 를 사용 하 는 방법 이다.
조작 1 에 대해 우 리 는 모든 구간 이 조회 값 보다 작은 수의 수량 을 누적 + 1 하면 된다 는 것 을 고려 합 니 다. 조회 과정 은 엄격 한 작은 접 두 사 를 뿌리 로 돌리 기만 하면 됩 니 다.
조작 2 에 대해 우 리 는 2 분 의 1 수 를 고려 한 다음 에 조작 1 의 방법 을 참조 하여 2 분 의 1 보다 작은 수의 수량 을 조회 하면 이것 은 단조 로 운 증가 이기 때문에 2 분 의 1 이 가능 하 다 는 것 을 알 수 있다. 조작 1 과 다른 것 은 여기 서 우 리 는 엄격 하지 않 은 작은 접 두 사 를 뿌리 로 돌려 야 한 다 는 것 이다.
조작 3 에 대해 서 는 이 위 치 를 포함 하 는 구간 마다 한 번 에 삭제 하고 한 번 에 삽입 하면 된다.
조작 4 에 대해 서 는 각 구간 의 엄격 한 작은 접 두 사 를 조회 하여 비교적 큰 값 을 취한 다.
조작 5 에 대해 서 는 각 구간 의 엄격 한 접 두 사 를 조회 하여 작은 값 을 취한 다.

#include
#include
#include
#include
#include
#include
#include
using namespace std;
int n,m,a[50005],root[200005],sign,ans,op,sum;
struct Tree
{
	int ch[2],fa;
	int recy,sum;
	int v;
}tree[1650005];
int crepoint(int v,int fa)
{
	sign++;
	tree[sign].v=v;
	tree[sign].fa=fa;
	tree[sign].recy=tree[sign].sum=1;
	return sign;
}
int whoson(int x)
{
	return (tree[tree[x].fa].ch[0]==x)?0:1;
}
void connect(int x,int fa,int son)
{
	tree[x].fa=fa;
	tree[fa].ch[son]=x;
}
void push_up(int k)
{
	tree[k].sum=tree[tree[k].ch[0]].sum+tree[tree[k].ch[1]].sum+tree[k].recy;
}
void rotate(int x)
{
	int y=tree[x].fa;
	int mroot=tree[y].fa;
	int yson=whoson(x);
	int mrootson=whoson(y);
	int B=tree[x].ch[yson^1];
	connect(B,y,yson);
	connect(y,x,yson^1);
	connect(x,mroot,mrootson);
	push_up(y);
	push_up(x);
}
void Splay(int x,int to,int k)
{
	while(tree[x].fa!=to)
	{
		int y=tree[x].fa,z=tree[y].fa;
		if(z!=to)
		{
			if(whoson(x)^whoson(y)) rotate(x);
			else rotate(y);
		}
		rotate(x);
	}
	if(!to) root[k]=x;
}
void find(int nowroot,int v,int k)
{
	int now=nowroot;
	while(now)
	{
		if(v==tree[now].v)
		{
			Splay(now,0,k);
			return ;
		}
		int nex=(v1)
	{
		tree[nowroot].recy--;
		tree[nowroot].sum--;
		return ;
	}
	int ls=tree[nowroot].ch[0],rs=tree[nowroot].ch[1];
	if(!ls&&!rs)
	{
		nowroot=0;
		return ;
	}
	if(!ls)
	{
		nowroot=rs;
		tree[rs].fa=0;
		return ;
	}
	if(!rs)
	{
		nowroot=ls;
		tree[ls].fa=0;
		return ;
	}
	while(tree[ls].ch[1]) ls=tree[ls].ch[1];
	Splay(ls,0,k);
	tree[nowroot].ch[1]=rs;
	if(rs) tree[rs].fa=nowroot;
}
void build(int k,int l,int r)
{
	for(int i=l;i<=r;i++) push(root[k],a[i],k);
	if(l==r) return ;
	int mid=(l+r)>>1;
	build(k<<1,l,mid);
	build(k<<1|1,mid+1,r);
}
int super(int nowroot,int v)
{
	int maxx=-0x7fffffff,nows=0;
	int now=nowroot;
	while(now)
	{
		if(tree[now].vv) if(minn>tree[now].v) minn=tree[now].v,nows=now;
		int nex=(v>1;
	if(ql<=mid) ask(k<<1,l,mid,ql,qr,v);
	if(mid>1;
	if(ql<=mid) ask2(k<<1,l,mid,ql,qr,v);
	if(mid>1;
	if(x<=mid) change(k<<1,l,mid,x,v1,v2);
	else change(k<<1|1,mid+1,r,x,v1,v2);
}
void ask3(int k,int l,int r,int ql,int qr,int v)
{
	if(ql<=l&&r<=qr)
	{
		int now=super(root[k],v);
		if(now) Splay(now,0,k);
		return ;
	}
	int mid=(l+r)>>1;
	if(ql<=mid) ask3(k<<1,l,mid,ql,qr,v);
	if(mid>1;
	if(ql<=mid) ask4(k<<1,l,mid,ql,qr,v);
	if(mid>1;
				sum=0;
				ask2(1,1,n,x,y,mid);
				if(sum>=z) ans=mid,r=mid-1;
				else l=mid+1;
			}
			printf("%d
",ans);
		}
		else if(op==3)
		{
			scanf("%d%d",&x,&y);
			change(1,1,n,x,a[x],y);
			a[x]=y;
		}
		else if(op==4)
		{
			scanf("%d%d%d",&x,&y,&z);
			ans=-0x7fffffff;
			ask3(1,1,n,x,y,z);
			printf("%d
",ans);
		}
		else
		{
			scanf("%d%d%d",&x,&y,&z);
			ans=0x7fffffff;
			ask4(1,1,n,x,y,z);
			printf("%d
",ans);
		}
	}
}