bzoj3524【POI2014】Couriers

Description

給一個長度為n的序列a。1≤a[i]≤n。
m組詢問，每次詢問一個區間[l,r]，是否存在一個數在[l,r]中出現的次數大於(r-l+1)/2。如果存在，輸出這個數，否則輸出0。

Input

第一行兩個數n，m。
第二行n個數，a[i]。
接下來m行，每行兩個數l,r，表示詢問[l,r]這個區間。

Output

m行，每行對應一個答案。

Sample Input

Sample Output

HINT

【數據范圍】

n,m≤500000

Source

By Dzy

第一道可持久化線段樹題。

至於可持久化線段樹的知識，就不在這裡贅述了。(因為我知道我肯定說不清楚……=_=)

這道題的做法是對於權值建立可持久化線段樹，記錄每個區間內數的出現次數sum。對於區間[l,r]的詢問，我們只需要用r的線段樹減去l-1的線段樹(權值線段樹是可以加減的)，在這棵線段樹中逐層遞歸，判斷是否滿足條件sum>(r-l+1)/2。如果遞歸到最後一層都滿足條件則找到了答案，否則輸出0。

因為是第一次寫可持久化線段樹，寫一點自己的理解吧：這道題利用了前綴和的思想，將區間操作轉化成兩個前綴和相減，而可持久化線段樹的構造方式也類似於前綴和，所以這樣操作起來就方便了許多。

#include
#include
#include
#include
#include
#include
#define F(i,j,n) for(int i=j;i<=n;i++)
#define D(i,j,n) for(int i=j;i>=n;i--)
#define ll long long
#define maxn 500005
#define maxm 10000005
using namespace std;
int n,m,tot;
int rt[maxn],ls[maxm],rs[maxm],sum[maxm];
inline int read()
{
	int x=0,f=1;char ch=getchar();
	while (ch<'0'||ch>'9'){if (ch=='-') f=-1;ch=getchar();}
	while (ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
	return x*f;
}
inline void update(int l,int r,int x,int &y,int v)
{
	y=++tot;
	sum[y]=sum[x]+1;
	if (l==r) return;
	ls[y]=ls[x];rs[y]=rs[x];
	int mid=(l+r)>>1;
	if (v<=mid) update(l,mid,ls[x],ls[y],v);
	else update(mid+1,r,rs[x],rs[y],v);
}
inline int query(int u,int v)
{
	int l=1,r=n,mid,x=rt[u-1],y=rt[v],tmp=(v-u+1)>>1;
	while (l!=r)
	{
		if (sum[y]-sum[x]<=tmp) return 0;
		mid=(l+r)>>1;
		if (sum[ls[y]]-sum[ls[x]]>tmp){r=mid;x=ls[x];y=ls[y];}
		else if (sum[rs[y]]-sum[rs[x]]>tmp){l=mid+1;x=rs[x];y=rs[y];}
		else return 0;
	}
	return l;
}
int main()
{
	n=read();m=read();
	F(i,1,n)
	{
		int x=read();
		update(1,n,rt[i-1],rt[i],x);
	}
	F(i,1,m)
	{
		int l=read(),r=read();
		printf("%d\n",query(l,r));
	}
	return 0;
}