트 리 세트 트 리 - 구간 k 대 (수정 띠)

제목: zoj 2112
제목: 구간 k 의 큰 수 를 구하 고 수정 작업 이 있 습 니 다.
분석: 이 문 제 는 나무 로 만 들 수 있다.
인터넷 에서 블 로 그 를 많이 보고 나 서 야 이해 하 는데...자료  자료
내 가 본 것 은 나무 모양 배열 의 선분 트 리 판 이다.그리고 선분 트 리 밸 런 스 트 리.
우선 주석 트 리 로 조작 전의 데 이 터 를 유지 합 니 다.
그리고 트 리 배열 로 수정 합 니 다.
나무 모양 배열 의 모든 노드 는 선분 나무 이 고 나무 모양 배열 의 모든 노드 는 하나의 관할 구역 (나무 모양 배열 의 성질 은 변 하지 않 았 다) 이 있다.
매번 업데이트 할 때마다 log (n) 트 리 배열 의 노드 를 수정 합 니 다.그러나 수정 은 바람 직 하지 않 기 때문에 log (n) 그루 의 선분 나 무 를 새로 만 드 는 방법 을 사용 했다.
새로 만 든 선분 트 리 는 원래 버 전의 선분 트 리 를 먼저 복사 한 다음 에 수정 할 경 로 를 대체 하 는 경로 (log (n) 노드 추가) 를 추가 하 는 것 입 니 다.
코드 (트 리 배열 라인 트 리):

#include 
using namespace std;

typedef long long LL;
typedef unsigned long long ULL;
const LL INF = 1E9+9;
const int maxn = 1e5+6;
const int LOG = 20;

struct node
{
	int l,r;
	int sum;
}Node[maxn*LOG];
int root[maxn],node_cnt;  //     ，      
int BIT[maxn];              //     
int numbers[maxn],num_cnt;   //      
int a[maxn],n,q; 

struct command
{
	char op;
	int L,R,K;
}com[10006];

void build(int l,int r,int &rt)
{
	rt=++node_cnt;
	Node[rt].sum=0;
	if(l==r) return ;
	int m=l+r>>1;
	build(l,m,Node[rt].l);
	build(m+1,r,Node[rt].r);
}
void update(int pos,int v,int l,int r,int &rt,int pre)
{
	rt=++node_cnt;
	Node[rt]=Node[pre];
	Node[rt].sum+=v;
	if(l==r) return ;
	int m=(l+r)>>1;
	if(pos<=m)
		update(pos,v,l,m,Node[rt].l,Node[pre].l);
	else
		update(pos,v,m+1,r,Node[rt].r,Node[pre].r);
}

void modify(int pos,int v,int rt)
{
	for(int i=rt;i>1;
	if(k<=c)
		return query(k,l,m);
	else
		return query(k-c,m+1,r);
}

inline int Find(int x)
{
	return lower_bound(numbers+1,numbers+1+num_cnt,x)-numbers;
}
void Q(int L,int R,int K)
{
	buf_cnt1=0;
	buf1[buf_cnt1++]=root[L-1];
	for(int i=L-1;i>0;i-=(i&-i))
		buf1[buf_cnt1++]=BIT[i];
	
	buf_cnt2=0;
	buf2[buf_cnt2++]=root[R];
	for(int i=R;i>0;i-=(i&-i))
		buf2[buf_cnt2++]=BIT[i];
		
	int q=query(K,1,num_cnt);
	printf("%d
",numbers[q]);
}
void C(int pos,int v)
{
	modify(Find(a[pos]),-1,pos);
	modify(Find(v),1,pos);
	a[pos]=v;
}
int main()
{
	int nCase;
	scanf("%d",&nCase);
	while(nCase--)
	{
		scanf("%d%d",&n,&q);
		for(int i=1;i<=n;i++)
		{
			scanf("%d",&a[i]);
			numbers[i]=a[i];
		} 
		num_cnt=n;
		char ch[2];
		for(int i=1;i<=q;i++)
		{
			scanf("%s",ch);
			if(ch[0]=='Q')
			{
				scanf("%d%d%d",&com[i].L,&com[i].R,&com[i].K);
				com[i].op='Q';
			}
			else
			{
				scanf("%d%d",&com[i].L,&com[i].R);
				com[i].op='C';
				numbers[++num_cnt]=com[i].R; 
			}
		}
		
		sort(numbers+1,numbers+num_cnt+1);
		num_cnt=unique(numbers+1,numbers+num_cnt+1)-numbers-1;
		root[0]=node_cnt=0;
		build(1,num_cnt,root[0]);
		for(int i=1;i<=n;i++)
		{
			int f=Find(a[i]);
			update(f,1,1,num_cnt,root[i],root[i-1]);
		} 
		for(int i=1;i<=n;i++) //       ，         
			BIT[i]=root[0];
		for(int i=1;i<=q;i++)
			'Q'==com[i].op?Q(com[i].L,com[i].R,com[i].K):C(com[i].L,com[i].R);
	}
	return 0;
}

선분 트 리 세트 reap 은 메모 리 를 초과 합 니 다. 저 는 동적 으로 메모 리 를 분배 합 니 다. 삭제 할 때 도 delete 했 습 니 다.최대 n * log (n) 개의 node, 즉 5 * 50000 * 16 개의 int (32000 * 1000 bit) 를 사 용 했 고 별도로 연 두 배열 20000 개의 int (1600 * 1000 bit) 를 더 해 총 32813 kb 로 방금 초과 했다.
해법

#include 
using namespace std;

typedef long long LL;
typedef unsigned long long ULL;
const LL INF = 1E9+9;

struct node          //  Treap   
{
	node* son[2];     //     
	int v;   		  //  
	int p;			  //    
	int sz;           //               
	node(int x)
	{
		son[0]=son[1]=NULL;
		v=x;
		p=rand();
		sz=1;
	}
	void pushup()         //              sz 
	{
		sz=1;
		if(son[0])	sz+=son[0]->sz;
		if(son[1])	sz+=son[1]->sz;
	}
};
inline int cmp(int a,int b)
{
	if(a==b)	return -1;
	return a>b?0:1;
}
inline void Rotate(node* &root,int d)    //d 0   （       ）, d 1   （       ） 
{
	node* k = root->son[d^1];
	root->son[d^1] = k->son[d] ;
	k->son[d] = root;
	root->pushup();
	k->pushup();
	root = k ; 
}
void Insert(node* &root,int x)    
{
	if(NULL==root)
		root = new node(x);
	else
	{
		int d = root->v>x?0:1;        //              
		Insert(root->son[d],x);
		if(root->pson[d]->p)
			Rotate(root,d^1);
	}
	if(root)
		root->pushup();
}
void Erase(node* &root,int x)      
{
	int d = cmp(root->v,x);
	if(-1==d)
	{
		node* u = root;
		if(!root->son[0])
		{
			root = root->son[1];
			delete u;
		}
		else if(!root->son[1])
		{
			root = root->son[0];
			delete u;
		}
		else
		{
			int d2 = (root->son[0]->p>root->son[1]->p?1:0);
			Rotate(root,d2);
			Erase(root->son[d2],x);
		}
	}
	else
		Erase(root->son[d],x);
	if(root)
		root->pushup();
}
void Destroy(node* &root)
{
	if(root->son[0])
		Destroy(root->son[0]);
	if(root->son[1])
		Destroy(root->son[1]);
	delete root;
	root=NULL;
}

int Find(node* root,int x)
{
	if(NULL==root)
		return 0;
	int ret=0,lnum=0;
	if(root->son[0])
		lnum+=root->son[0]->sz;
	if(x>=root->v)
		return lnum+1+Find(root->son[1],x);
	else
		return Find(root->son[0],x); 
}

#define lson l,m,rt<<1
#define rson m+1,r,rt<<1|1
const int maxn = 50006;
node* tree[151000];
int a[maxn],n,m;

void update(int pos,int v,int d,int l,int r,int rt)
{
	d==1?Insert(tree[rt],v):Erase(tree[rt],v);
	if(l==r) return ;
	int m=(l+r)>>1;
	pos<=m?update(pos,v,d,lson):update(pos,v,d,rson);
}
int query(int L,int R,int x,int l,int r,int rt)
{
	if(L<=l && r<=R)
		return Find(tree[rt],x);
	int m=(l+r)>>1,ret(0);
	if(L<=m)
		ret+=query(L,R,x,lson);
	if(R>m)
		ret+=query(L,R,x,rson);
	return ret;
}

int work(node* root,int x)
{
	int ret=INF;
	while(root)
	{
		if(root->v>=x)
		{
			if(ret>root->v)
				ret=root->v;
			root=root->son[0];
		}
		else
			root=root->son[1];
	}
	return ret;
}

int q(int L,int R,int x,int l,int r,int rt)
{
	if(L<=l && r<=R)
		return work(tree[rt],x);
	int m=(l+r)>>1,ret=INF;
	if(L<=m)
		ret=min(ret,q(L,R,x,lson));
	if(R>m)
		ret=min(ret,q(L,R,x,rson));
	return ret;
}

void Q(int L,int R,int K)
{
	int down=-INF,up=INF,mid,ret;
	while(down>1;
	//	printf("%d
",mid);
		int c=query(L,R,mid,1,n,1);
		if(c>=K)
			up=mid;
		else
			down=mid+1;
	}
	printf("%d
",q(L,R,down,1,n,1));
}
void C(int pos,int v)
{
	update(pos,a[pos],0,1,n,1);
	update(pos,v,1,1,n,1);
	a[pos]=v;
}

int main()
{
	int nCase;
	scanf("%d",&nCase);
	while(nCase--)
	{
		scanf("%d%d",&n,&m);
		for(int i=1;i<=n;i++)
			scanf("%d",&a[i]);
		for(int i=0;i