@[皎月半洒花](/space/show?uid=28313) A辣，开心
by かなで @ 2018-06-26 18:03:32
好像没啥坑啊
贴代码（巨丑见谅）
```cpp
#include<bits/stdc++.h>
using namespace std;
const int N=500001;
int rk[N],rt[N],num[N],ord;
struct p{int x,id;}a[N];
struct T{int l,r,v;}tree[N*20];
inline bool cmp(p a,p b){return a.x<b.x;}
int build(int s,int t){
int r=++ord;
if(s!=t){
int mid=s+t>>1;
tree[r].l=build(s,mid),tree[r].r=build(mid+1,t);
}
return r;
}
int insert(int pre,int x,int s,int t){
int r=++ord;
tree[r].l=tree[pre].l,tree[r].r=tree[pre].r,tree[r].v=tree[pre].v+1;
if(s!=t){
int mid=s+t>>1;
if(x<=mid) tree[r].l=insert(tree[pre].l,x,s,mid);
else tree[r].r=insert(tree[pre].r,x,mid+1,t);
}
return r;
}
int query(int x,int y,int s,int t,int k){
if(s==t) return s;
int mid=s+t>>1;
if(tree[tree[y].l].v-tree[tree[x].l].v>=k)
return query(tree[x].l,tree[y].l,s,mid,k);
else if(tree[tree[y].r].v-tree[tree[x].r].v>=k)
return query(tree[x].r,tree[y].r,mid+1,t,k);
else return 0;
}
int main(){
int n,m,s=0,x,y,z;
scanf("%d%d",&n,&m);
for(int i=1;i<=n;i++) scanf("%d",&a[i].x),a[i].id=i;
sort(a+1,a+n+1,cmp);
for(int i=1;i<=n;i++){
if(a[i].x!=a[i-1].x) a[++s].x=a[i].x;
rk[a[i].id]=s;
}
build(1,s);
for(int i=1;i<=n;i++) rt[i]=insert(rt[i-1],rk[i],1,s);
while(m--){
scanf("%d%d",&x,&y);
printf("%d\n",a[query(rt[x-1],rt[y],1,s,y-x+3>>1)]);
}
return 0;
}
```
by かなで @ 2018-06-26 18:06:02
@[かなで](/space/show?uid=100018) 蟹蟹QAQ……是我的$N$和$Len$写挂了的缘故……
by 皎月半洒花 @ 2018-06-26 20:20:54
@[皎月半洒花](/space/show?uid=28313) 哎..Rk1就很舒服
by かなで @ 2018-06-26 21:59:06