双倍经验主席树。内存开大。
#include<iostream> #include<cstdio> #include<cstring> #include<algorithm> #define maxn 500500 #define maxv 10000500 using namespace std; int n,m,ls[maxv],rs[maxv],sum[maxv],root[maxn],x,tot=0,l,r; inline int read() { char ch=getchar();int data=0; while (ch<'0' || ch>'9') ch=getchar(); while (ch>='0' && ch<='9') {data=data*10+ch-'0';ch=getchar();} return data; } void update(int left,int right,int last,int &now,int x) { int mid=(left+right)>>1; now=++tot; sum[now]=sum[last]+1; if (left==right) return; ls[now]=ls[last];rs[now]=rs[last]; if (x<=mid) update(left,mid,ls[last],ls[now],x); else update(mid+1,right,rs[last],rs[now],x); } int ask(int left,int right,int last,int now,int tmp) { if (left==right) return left; int mid=(left+right)>>1; int ll=sum[ls[now]]-sum[ls[last]],rr=sum[rs[now]]-sum[rs[last]]; if (sum[ls[now]]-sum[ls[last]]>tmp) return ask(left,mid,ls[last],ls[now],tmp); else if (sum[rs[now]]-sum[rs[last]]>tmp) return ask(mid+1,right,rs[last],rs[now],tmp); else return 0; } int main() { n=read();m=read(); for (int i=1;i<=n;i++) { x=read(); update(1,n,root[i-1],root[i],x); } for (int i=1;i<=m;i++) { l=read();r=read(); printf("%d ",ask(1,n,root[l-1],root[r],(r-l+1)/2)); } return 0; }