【BZOJ2223】【COCI2009】PATULJCI

  裸的主席树。

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

struct President_Tree
{
	int sum[maxv];
	int ls[maxv],rs[maxv];
	int root[maxn];
	int n,lim,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 _lim,int *a) {n=_n;lim=_lim;for (int i=1;i<=n;i++) Build(1,lim,root[i-1],root[i],a[i]);}
	int Query(int l,int r) {return Query(1,lim,root[l-1],root[r],((r-l+1)>>1)+1);}
}T;

int a[maxn];
int n,m,lim;

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