题目链接: QwQ

Solution:

以权值为下标，对每个点建树

对于x点，以它为根的树涵盖的是1到x区间内每个数出现的次数

Code:

#include<bits/stdc++.h>

#define N 500001

using namespace std;

int n,m,tot,rt[N];

struct chair_tree{int sum,l,r;}tree[N*21];

void ins(int &x,int v,int l,int r){

    tree[++tot]=tree[x];

    x=tot;tree[x].sum++;

    if(l==r) return ;

    int mid=(l+r)>>1;

    if(v<=mid) ins(tree[x].l,v,l,mid);

    else ins(tree[x].r,v,mid+1,r);

}

int query(int p1,int p2,int u,int l,int r){

    if(l==r) return l;

    int mid=(l+r)>>1;

    if(2*(tree[tree[p2].l].sum-tree[tree[p1].l].sum)>u)

        return query(tree[p1].l,tree[p2].l,u,l,mid);

    if(2*(tree[tree[p2].r].sum-tree[tree[p1].r].sum)>u)

        return query(tree[p1].r,tree[p2].r,u,mid+1,r);

    return 0;

}

int read(){

    int x=0,f=1;char ch=getchar();

    while(!isdigit(ch)){if(ch=='-')f=-f;ch=getchar();}

    while(isdigit(ch)){x=x*10+ch-48;ch=getchar();}

    return x*f;

}

int main(){

    n=read(),m=read();

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

        int x=read();

        rt[i]=rt[i-1];

        ins(rt[i],x,1,n);

    }

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

        int l=read(),r=read();

        printf("%d\n",query(rt[l-1],rt[r],r-l+1,1,n));

    }

    return 0;

}