题目描述

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

题目分析

发现这里的众数可以进行加减= =
那么直接主席树即可
判定方法:
如果左儿子的差大于(r-l+1)/2 进入左儿子
如果右儿子的差大于(r-l+1)/2 进入右儿子
否则直接返回0

#include <cstdio>
#include <cstring>
#include <set>
#include <map>
#include <vector>
#include <cmath>
#include <queue>
#include <algorithm>
using namespace std;
int n,m;
int val[500010];
struct your
{
    int lson,rson;
    int size;
}a[500010*40];
int root[500010],tot;
void update(int x,int &y,int l,int r,int c)
{
    y=++tot;
    a[y]=a[x],a[y].size++;
    if(l==r) return ;
    int mid=(l+r)>>1;
    if(c<=mid) update(a[x].lson,a[y].lson,l,mid,c);
    else update(a[x].rson,a[y].rson,mid+1,r,c);
}
int ask(int x,int y,int l,int r,int c)
{
    if(l==r) return l;
    int mid=(l+r)>>1;
    if(a[a[y].lson].size-a[a[x].lson].size>c) return ask(a[x].lson,a[y].lson,l,mid,c);
    if(a[a[y].rson].size-a[a[x].rson].size>c) return ask(a[x].rson,a[y].rson,mid+1,r,c);
    return 0;
}
int main()
{
    scanf("%d%d",&n,&m);
    for(int i=1;i<=n;i++) scanf("%d",&val[i]);
    for(int i=1;i<=n;i++)
        update(root[i-1],root[i],1,1e9,val[i]);
    for(int x,y,i=1;i<=m;i++)
        scanf("%d%d",&x,&y),printf("%d\n",ask(root[x-1],root[y],1,1e9,(y-x+1)/2) );
    return 0;
}
/*

    for(int x,y,i=1;i<=m;i++)
    {
        scanf("%d%d",&x,&y);
        int tmp=ask(root[x-1],root[y],1,1e9,(y-x+1)/2);
        if(tmp==0) printf("no\n");
        else printf("yes %d\n",tmp);
    }
*/