3524: [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
7 5
1 1 3 2 3 4 3
1 3
1 4
3 7
1 7
6 6
1 1 3 2 3 4 3
1 3
1 4
3 7
1 7
6 6
Sample Output
1
0
3
0
4
0
3
0
4
HINT
【数据范围】
n,m≤500000
这还是一道主席树の题
#include<cstdio>
#define MaxN 500010
#define MaxT 10000010
int N,Q,tot;
int Ans;
struct point{
int l,r,sum;
point (int x=0,int y=0,int s=0){
l=x; r=y; sum=s;
}
}P[MaxT];
int root[MaxN];
int Get(){
char Ch;
while ((Ch=getchar())<'0'||Ch>'9');
int Num=Ch-'0';
while ((Ch=getchar())>='0'&&Ch<='9')
Num=Num*10+Ch-'0';
return Num;
}
void Insert(const int &y,int &x,const int &l,const int &r,const int &p){
P[x=++tot]=P[y];
++P[x].sum;
if (l==r) return;
int mid=(l+r)/2;
if (p<=mid) Insert(P[y].l,P[x].l,l,mid,p);
else Insert(P[y].r,P[x].r,mid+1,r,p);
}
void find(const int &y,const int &x,const int &l,const int &r,const int &c){
if (l==r){
if (P[x].sum-P[y].sum>c) Ans=l;
return;
}
int tmp=P[P[x].l].sum-P[P[y].l].sum;
int mid=(l+r)/2;
if (tmp>c) find(P[y].l,P[x].l,l,mid,c);
else find(P[y].r,P[x].r,mid+1,r,c);
}
int main(){
N=Get(); Q=Get();
for (int i=1;i<=N;++i)
Insert(root[i-1],root[i],1,N,Get());
for (;Q--;){
int l=Get(),r=Get();
Ans=0;
find(root[l-1],root[r],1,N,(r-l+1)/2);
printf("%d\n",Ans);
}
}
评论 (0)
