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

[ Submit][ Status][ Discuss]

分析： 显然主席树 如果一个数在区间内出现了超过一半的次数 那么从小到大排序后，在区间正中间位置的数一定就是所求 但是也存在无解的情况

所以我们先区间查找到第 (r−l+1)/2 ( r − l + 1 ) / 2 大 之后判断这个数在区间内出现的次数是否大于 (r−l+1)/2 ( r − l + 1 ) / 2

一开始我很天真的以为，我们可以在查找第k大的时候就计算出这个数的出现次数 但是我们在查找第k大的时候只能确定值， 这个第k大有可能是区间最大的数，也有可能是取件最小的数

总而言之，我们必须在找到第k大之后 重新ask一下这个值在区间内的出现次数

tip

建立的是权值线段树 因此在线段树查找的过程，可以视为是对答案的一个二分 当 l==r l == r 时， l l 即为答案

询问第k大的时候：

int tmp=t[t[y].l].sum-t[t[x].l].sum;

不要记错了

主席树空间：nlognnlogn

#include<cstdio> #include<cstring> #include<iostream> using namespace std; const int N=500005; int root[N],a[N],n,m,top=0; struct node{ int sum,l,r; }; node t[N*20]; void insert(int &now,int l,int r,int x) { top++; t[top]=t[now]; now=top; t[now].sum++; if (l==r) return; int mid=(l+r)>>1; if (x<=mid) insert(t[now].l,l,mid,x); else insert(t[now].r,mid+1,r,x); } int ask(int x,int y,int l,int r,int k) //返回第k大 { if (l==r) return l; int tmp=t[t[y].l].sum-t[t[x].l].sum; int mid=(l+r)>>1; if (tmp>=k) return ask(t[x].l,t[y].l,l,mid,k); else return ask(t[x].r,t[y].r,mid+1,r,k-tmp); } int point(int x,int y,int l,int r,int z) { if (l==r) return t[y].sum-t[x].sum; int mid=(l+r)>>1; if (z<=mid) return point(t[x].l,t[y].l,l,mid,z); else return point(t[x].r,t[y].r,mid+1,r,z); } int main() { scanf("%d%d",&n,&m); for (int i=1;i<=n;i++) { scanf("%d",&a[i]); root[i]=root[i-1]; insert(root[i],1,n,a[i]); } for (int i=1;i<=m;i++) { int x,y; scanf("%d%d",&x,&y); int cnt=(y-x+1)/2; int z=ask(root[x-1],root[y],1,n,cnt+1); //find cnt+1 int ans=point(root[x-1],root[y],1,n,z); if (ans>cnt) printf("%d\n",z); else printf("0\n"); } return 0; }