[pixiv] https://www.pixiv.net/member_illust.php?mode=medium&illust_id=62485671

向大(hei)佬(e)势力学(di)习(tou)

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

没想到我竟已经会了主席树（水题）

#include<cstdio>

#include<cstring>

#include<algorithm>

using namespace std;

const int N=500000+5;

struct Node{

    Node *ls,*rs;

    int sum;

}*root[N],*null,pool[N*40],*tail=pool;

int n,m,aa;

Node *newnode(){

    Node *rt=++tail;

    rt->ls=rt->rs=null;

    rt->sum=0;

    return rt;

}

void insert(Node *&ndn,Node *ndp,int le,int ri,int pos){

    ndn=newnode();

    ndn->sum=ndp->sum+1;

    if(le==ri) return ;

    ndn->ls=ndp->ls,ndn->rs=ndp->rs;

    int mid=(le+ri)>>1;

    if(pos<=mid) insert(ndn->ls,ndp->ls,le,mid,pos);

    else insert(ndn->rs,ndp->rs,mid+1,ri,pos);

}

int query(Node *ndn,Node *ndp,int le,int ri,int limit){

    if(le==ri) return le;

    int mid=(le+ri)>>1;

    int lsum=ndn->ls->sum - ndp->ls->sum;

    int rsum=ndn->rs->sum - ndp->rs->sum;

    int rt=0;

    if(lsum>limit) rt=query(ndn->ls,ndp->ls,le,mid,limit);

    if(rsum>limit) rt=query(ndn->rs,ndp->rs,mid+1,ri,limit);

    return rt;

}

int main(){

    null=++tail;

    null->ls=null->rs=null;

    null->sum=0;

    root[0]=null;

    scanf("%d%d",&n,&m);

    for(int i=1;i<=n;i++){

        scanf("%d",&aa);

        insert(root[i],root[i-1],1,n,aa);

    }

    int x,y;

    while(m--){

        scanf("%d%d",&x,&y);

        printf("%d\n",query(root[y],root[x-1],1,n,(y-x+1)/2));

    }

    return 0;

}