程序師世界是廣大編程愛好者互助、分享、學習的平台,程序師世界有你更精彩!
首頁
編程語言
C語言|JAVA編程
Python編程
網頁編程
ASP編程|PHP編程
JSP編程
數據庫知識
MYSQL數據庫|SqlServer數據庫
Oracle數據庫|DB2數據庫
 程式師世界 >> 編程語言 >> C語言 >> C++ >> 關於C++ >> bzoj3524【POI2014】Couriers

bzoj3524【POI2014】Couriers

編輯:關於C++

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

7 5
1 1 3 2 3 4 3
1 3
1 4
3 7
1 7
6 6

Sample Output

1
0
3
0
4

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;
}
  1. 上一頁:
  2. 下一頁:
Copyright © 程式師世界 All Rights Reserved