给一个长度为n的序列a。1≤a[i]≤n。 m组询问,每次询问一个区间[l,r],是否存在一个数在[l,r]中出现的次数大于(r-l+1)/2。如果存在,输出这个数,否则输出0。
第一行两个数n,m。 第二行n个数,a[i]。 接下来m行,每行两个数l,r,表示询问[l,r]这个区间。
m行,每行对应一个答案。
【数据范围】 n,m≤500000
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一下这个值在区间内的出现次数
建立的是权值线段树 因此在线段树查找的过程,可以视为是对答案的一个二分 当 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; }