给出一段长度为n的序列,每个数都不超过n.然后有m个询问,每个询问给出一个区间[l,r],求这其中是否有一个数出现的次数超过了区间长度的一半.如果有,输出这个数,否则输出0.

链接

原题为BZOJ权限题,故只给出DarkBZOJ的地址

DarkBZOJ

题解

主席树裸题.对于每个询问,查询一下给定区间内是否有数字出现次数达到要求即可.题目中的条件保证了这样的数字至多有一个,所以在递归的过程中可以使用区间中所有数字的出现次数来代替,具体细节见代码.

刷这道题主要是为了更新一下主席树的板子,原来的的那个传实参不大好记,改成返回新节点的值之后就可以和可持久化数据结构的板子保持一致辣~

#include<cstring>
#include<cstdio>
#include<iostream>
#include<algorithm>
#include<vector>
#include<cmath>
#define N 500010
#define l(x) (x<<1)
#define r(x) ((x<<1)+1)
#define LL long long
#define INF 0x3f3f3f3f
using namespace std;

int n,m,i,x,y,tot,k;
int a[N],root[N];

struct Tree{
    int l,r,d;
}t[N*30];

inline int Abs(int x){return (x<0)?-x:x;}
inline void Swap(int &a,int &b){a^=b^=a^=b;}
inline int Min(int a,int b){return (a<b)?a:b;}
inline int Max(int a,int b){return (a>b)?a:b;}

inline int read(){
    int p=0;    char    c=getchar();
    while (c<48||c>57)  c=getchar();
    while (c>=48&&c<=57)    p=(p<<1)+(p<<3)+c-48,c=getchar();
    return p;
}

inline int Build(int low,int high){
    int x=++tot,mid=(low+high)>>1;
    if (low==high)  return x;
    t[x].l=Build(low,mid);  t[x].r=Build(mid+1,high);
    return x;
}

inline int Insert(int pre,int low,int high,int val){
    int x=++tot,mid=(low+high)>>1;
    t[x]=t[pre];
    if (low==high)  {t[x].d++;  return x;}
    (val<=mid)?t[x].l=Insert(t[x].l,low,mid,val):t[x].r=Insert(t[x].r,mid+1,high,val);
    t[x].d=(t[t[x].l].d+t[t[x].r].d);
    return x;
}

inline int Query(int l,int r,int low,int high,int p){
    int x=0,y=0,mid=(low+high)>>1;
    if (low==high)  return low;
    x=t[t[r].r].d-t[t[l].r].d;
    y=t[t[r].l].d-t[t[l].l].d;
    if (x>=p)   return Query(t[l].r,t[r].r,mid+1,high,p);
    else if (y>=p)  return Query(t[l].l,t[r].l,low,mid,p);
    return 0;
}

int main(){
    #ifdef __Marvolo
    freopen("zht.in","r",stdin);
    freopen("zht.out","w",stdout);
    #endif
    n=read();   m=read();
    for (i=1;i<=n;i++)  a[i]=read();
    root[0]=Build(1,n);
    for (i=1;i<=n;i++)  root[i]=Insert(root[i-1],1,n,a[i]);
    for (i=1;i<=m;i++){
        x=read();   y=read();   k=((y-x+1)>>1)+1;
        printf("%d\n",Query(root[x-1],root[y],1,n,k));
    }
    return 0;
}