思路：
卡空间，sb题；
代码：
#include <bits/stdc++.h> using namespace std; #define maxn 500005 #define maxn_ maxn*19 int n,m,lc[maxn_],rc[maxn_],dis[maxn_],ans; int ai[maxn],bi[maxn],root[maxn],tot,size; inline void in(int &now) { char Cget=getchar();now=0; while(Cget>'9'||Cget<'0') Cget=getchar(); while(Cget>='0'&&Cget<='9') { now=now*10+Cget-'0'; Cget=getchar(); } } void build(int &now,int l,int r) { now=++tot; if(l==r) return; int mid=l+r>>1; build(lc[now],l,mid); build(rc[now],mid+1,r); } inline void add(int &now,int pre,int l,int r,int to) { now=++tot,dis[now]=dis[pre]+1; if(l==r) return; int mid=l+r>>1; if(to<=mid) add(lc[now],lc[pre],l,mid,to),rc[now]=rc[pre]; else add(rc[now],rc[pre],mid+1,r,to),lc[now]=lc[pre]; } inline void query(int now,int pre,int l,int r,int k) { if(l==r) {ans=l;return;}; int mid=l+r>>1,di=dis[lc[now]]-dis[lc[pre]]; if(di>=k) {query(lc[now],lc[pre],l,mid,k);return;} di=dis[rc[now]]-dis[rc[pre]]; if(di>=k) {query(rc[now],rc[pre],mid+1,r,k);return;} ans=0;return; } int main() { in(n),in(m);int l,r,to; for(int i=1;i<=n;i++) in(ai[i]),bi[i]=ai[i]; sort(bi+1,bi+n+1),size=unique(bi+1,bi+n+1)-bi-1; build(root[0],1,size); for(int i=1;i<=n;i++) { to=lower_bound(bi+1,bi+size+1,ai[i])-bi; add(root[i],root[i-1],1,size,to); } while(m--) { in(l),in(r); query(root[r],root[l-1],1,size,(r-l+1>>1)+1); printf("%d ",bi[ans]); } return 0; }