复习主席树，这东西掌握得不好。
#include<cstdio> #include<cstring> #include<algorithm> using namespace std; struct chair { int lc,rc,c; }tr[21000000];int cnt,rt[510000]; int maketree(int x,int l,int r,int p) { if(x==0)x=++cnt; tr[x].c++; if(l<r) { int mid=(l+r)/2; if(p<=mid)tr[x].lc=maketree(tr[x].lc,l,mid,p); else tr[x].rc=maketree(tr[x].rc,mid+1,r,p); } return x; } int merge(int x,int y) { if(x==0||y==0)return x+y; tr[x].c+=tr[y].c; tr[x].lc=merge(tr[x].lc,tr[y].lc); tr[x].rc=merge(tr[x].rc,tr[y].rc); return x; } bool bk; void ask(int x,int y,int l,int r,int k) { if(bk==true)return ; if(tr[x].c-tr[y].c<k)return ; if(l==r){bk=true;printf("%d ",l);return ;} int mid=(l+r)/2; ask(tr[x].lc,tr[y].lc,l,mid,k); ask(tr[x].rc,tr[y].rc,mid+1,r,k); } int a[510000]; int main() { int n,m; scanf("%d%d",&n,&m); for(int i=1;i<=n;i++)scanf("%d",&a[i]); cnt=0;memset(rt,0,sizeof(rt)); for(int i=1;i<=n;i++) { rt[i]=maketree(rt[i],1,500000,a[i]); rt[i]=merge(rt[i],rt[i-1]); } int x,y; for(int i=1;i<=m;i++) { scanf("%d%d",&x,&y); bk=false; ask(rt[y],rt[x-1],1,500000,(y-x+1)/2+1); if(bk==false)printf("0 "); } return 0; }