主席树 bzoj2653

clj的题。。。。

一开始因为下标从1开始记得闹了好长时间。。。后来才看见原来题上说了要从0开始。。。

应该算是比较基础的主席树题目

具体的可以看clj的解题报告。。不过这个报告不算很好找

#include<iostream>
#include<cstring>
#include<cstdio>
#include<algorithm>
#define MAX 2560005

using namespace std;

int child[2][MAX],value[MAX],Lmax[MAX],Rmax[MAX],tree[MAX],n,m,tot=0;

struct wbysr
{
	int num,id;
}a[MAX];

bool cmp(wbysr a1,wbysr a2)
{
	return a1.num<a2.num;
}

void up(int x)
{
	value[x]=value[child[0][x]]+value[child[1][x]];
	Lmax[x]=max(Lmax[child[0][x]],value[child[0][x]]+Lmax[child[1][x]]);//???
	Rmax[x]=max(Rmax[child[1][x]],value[child[1][x]]+Rmax[child[0][x]]);
}

int build(int la,int ra)
{
	int root=tot++;
	if(la==ra)
	{
		value[root]=Lmax[root]=Rmax[root]=1;
		return root;
	}
	int mid=(la+ra)>>1;
	child[0][root]=build(la,mid);
	child[1][root]=build(mid+1,ra);
	up(root);
	return root;
}

int insert(int root,int la,int ra,int pos,int Value)
{
	int New=tot++;
	if(la==ra)
	{
		value[New]=Lmax[New]=Rmax[New]=Value;
		return New;
	}
	int mid=(la+ra)>>1;
	if(pos<=mid)
	{
		child[0][New]=insert(child[0][root],la,mid,pos,Value);
		child[1][New]=child[1][root];
		root=child[0][root];
	}
	else
	{
		child[1][New]=insert(child[1][root],mid+1,ra,pos,Value);
		child[0][New]=child[0][root];
		root=child[1][root];
	}
	up(New);
	return New;
}

int ask_value(int x,int la,int ra,int l,int r)
{
	if(la==l&&ra==r)
		return value[x];
	int mid=(la+ra)>>1;
	if(r<=mid)
		return ask_value(child[0][x],la,mid,l,r);
	else
		if(l>mid)
			return ask_value(child[1][x],mid+1,ra,l,r);
		else
			return ask_value(child[0][x],la,mid,l,mid)+ask_value(child[1][x],mid+1,ra,mid+1,r);
}

int ask_l(int x,int la,int ra,int l,int r)
{
	if(la==l&&ra==r)
		return Lmax[x];
	int mid=(la+ra)>>1;
	if(r<=mid)
		return ask_l(child[0][x],la,mid,l,r);
	else
		if(l>mid)
			return ask_l(child[1][x],mid+1,ra,l,r);
		else
			return max(ask_l(child[0][x],la,mid,l,mid),ask_value(child[0][x],la,mid,l,mid)+ask_l(child[1][x],mid+1,ra,mid+1,r));
}

int ask_r(int x,int la,int ra,int l,int r)
{
	if(la==l&&ra==r)
		return Rmax[x];
	int mid=(la+ra)>>1;
	if(r<=mid)
		return ask_r(child[0][x],la,mid,l,r);
	else
		if(l>mid)
			return ask_r(child[1][x],mid+1,ra,l,r);
		else
			return max(ask_r(child[0][x],la,mid,l,mid)+ask_value(child[1][x],mid+1,ra,mid+1,r),ask_r(child[1][x],mid+1,ra,mid+1,r));
}

bool check(int x,int a1,int b,int c,int d)
{
	int Return=0;
	if(b+1<=c-1)
		Return+=ask_value(tree[x],0,n-1,b+1,c-1);
	Return+=ask_r(tree[x],0,n-1,a1,b);
	Return+=ask_l(tree[x],0,n-1,c,d);
	return Return>=0;
}

int main()
{
	scanf("%d",&n);
	for(int i=0;i<n;i++)
		scanf("%d",&a[i].num),a[i].id=i;
	sort(a,a+n,cmp);
	tree[0]=build(0,n-1);
	for(int i=1;i<n;i++)
		tree[i]=insert(tree[i-1],0,n-1,a[i-1].id,-1);
	scanf("%d",&m);

	int ans=0;
	while(m--)
	{
		int ask[5];
		for(int i=1;i<=4;i++)
			scanf("%d",&ask[i]);
		for(int i=1;i<=4;i++)
			ask[i]=(ask[i]+ans)%n;
		sort(ask+1,ask+5);
		int L=0,R=n-1;
		while(L<=R)
		{
			int mid=(L+R)>>1;
			if(check(mid,ask[1],ask[2],ask[3],ask[4]))
				L=mid+1,ans=a[mid].num;
			else
				R=mid-1;
		}
		printf("%d\n",ans);
	}
	return 0;
}

主席树 bzoj2653,布布扣,bubuko.com

主席树 bzoj2653

原文：http://blog.csdn.net/wbysr/article/details/20574659