【BZOJ3524】【POI2014】Couriers

  裸的主席树。注意卡内存。

#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
const int maxn=500010,maxv=10000010;

struct President_Tree
{
	int sum[maxv];
	int ls[maxv],rs[maxv];
	int root[maxn];
	int n,IDs;

	#define mid ((l+r)>>1)

	void Build(int l,int r,int lnd,int &nnd,int v)
	{
		nnd=++IDs;
		sum[nnd]=sum[lnd]+1;
		if (l==r) return;
		if (v<=mid) rs[nnd]=rs[lnd],Build(l,mid,ls[lnd],ls[nnd],v);
			else ls[nnd]=ls[lnd],Build(mid+1,r,rs[lnd],rs[nnd],v);
	}

	int Query(int l,int r,int lnd,int rnd,int v)
	{
		while (l<r)
		{
			if (sum[rnd]-sum[lnd]<v) return 0;
			if (sum[ls[rnd]]-sum[ls[lnd]]>=v) lnd=ls[lnd],rnd=ls[rnd],r=mid;
			else if (sum[rs[rnd]]-sum[rs[lnd]]>=v) lnd=rs[lnd],rnd=rs[rnd],l=mid+1;
			else return 0;
		}
		return l;
	}

	void Build(int _n,int *a) {n=_n;for (int i=1;i<=n;i++) Build(1,n,root[i-1],root[i],a[i]);}
	int Query(int l,int r)
	{
		int v=((r-l+1)>>1)+1;
		return Query(1,n,root[l-1],root[r],v);
	}
}T;

int a[maxn];
int n,m;

int main()
{
	scanf("%d%d",&n,&m);
	for (int i=1;i<=n;i++) scanf("%d",&a[i]);
	T.Build(n,a);
	for (int i=1,l,r;i<=m;i++) scanf("%d%d",&l,&r),printf("%d\n",T.Query(l,r));
	return 0;
}