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
题解 主席树
代码
#include<cstdio> #include<cstring> #include<iostream> #include<cmath> #include<algorithm> #define N 10001 #define M 1000001 using namespace std; int n,m,sz; int root[500010],ls[10000010],rs[10000010],sum[10000010]; 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; } void update(int p,int &k,int l,int r,int x) { k=++sz; sum[k]=sum[p]+1; if (l==r) return; ls[k]=ls[p];rs[k]=rs[p]; int mid=(l+r)>>1; if (x>mid) update(rs[p],rs[k],mid+1,r,x); else update(ls[p],ls[k],l,mid,x); } int query(int p,int k,int len) { len=(len+1)>>1; int l=1,r=n; while (l!=r) { int mid=(l+r)>>1; if (sum[ls[k]]-sum[ls[p]]>len) r=mid,k=ls[k],p=ls[p]; else if (sum[rs[k]]-sum[rs[p]]>len) l=mid+1,k=rs[k],p=rs[p]; else return 0; } return l; } int main() { n=read();m=read(); for (int i=1;i<=n;i++) { int x=read(); update(root[i-1],root[i],1,n,x); } while (m--) { int l=read(),r=read(); printf("%d\n",query(root[l-1],root[r],r-l)); } return 0; }