```cpp
#include <bits/stdc++.h>
using namespace std;
const int N=5e5+5;
int n,m;
int a[N];
int root[N];
int cnt;
struct tree{
int lc,rc,sum;
}t[N*25];
void build(int &p,int l,int r){
p=++cnt;
t[p].sum=0;
if(l==r)return;
int mid=(l+r)>>1;
build(t[p].lc,l,mid);
build(t[p].rc,mid+1,r);
}
void modify(int &p,int o,int x,int l,int r){
p=++cnt;
t[p].lc=t[o].lc,t[p].rc=t[o].rc;
t[p].sum=t[o].sum;
if(l==r){
t[p].sum++;
return;
}
int mid=(l+r)>>1;
if(x<=mid)modify(t[p].lc,t[o].lc,x,l,mid);
else modify(t[p].rc,t[o].rc,x,mid+1,r);
t[p].sum=t[t[p].lc].sum+t[t[p].rc].sum;
}
int query(int p,int o,int l,int r,int x){
//printf("%d %d\n",t[p].sum,t[o].sum);
if(l==r)return l;
int mid=(l+r)>>1;
if(t[t[p].lc].sum-t[t[o].lc].sum>x)return query(t[p].lc,t[o].lc,l,mid,x);
if(t[t[p].rc].sum-t[t[o].rc].sum>x)return query(t[p].rc,t[o].rc,mid+1,r,x);
return 0;
}
int main(){
scanf("%d%d",&n,&m);
build(root[0],1,n);
for(int i=1;i<=n;i++){
scanf("%d",&a[i]);
modify(root[i],root[i-1],a[i],1,n);
}
while(m--){
int l,r;
scanf("%d%d",&l,&r);
printf("%d\n",query(root[r],root[l-1],1,n,(r-l+1)/2));
}
return 0;
}
by syta @ 2022-09-29 11:04:56
一会爆RE一会爆MLE的原因是……RE的部分还没MLE就先越界了，你就算调死也是不能卡到AC的。
正确的做法是优化一下做法，而不是卡数组长度……
by _Karasu_ @ 2022-09-29 11:39:26
@[_Karasu_](/user/123451) 那好吧，谢谢喵！
by syta @ 2022-09-29 12:06:44
qndmx
by NOI_AK_dreeeam @ 2022-09-29 12:15:52
@[syta](/user/505643) 做法是对的，可以对着题解改改
by a16_ @ 2022-09-29 13:09:51
@[NOI_AK_dreeeam](/user/686445) mxmz（确信
by syta @ 2022-09-29 13:34:01
@[a16_](/user/416388) 好的好的谢谢
by syta @ 2022-09-29 13:34:16
此贴结，离散化一下就好了
by syta @ 2022-09-29 14:00:35
@[syta](/user/505643) 您又在爆切主席树的题啦/kk
by Zwb0106 @ 2022-09-29 14:05:37
@[Zwb0106](/user/304837) 0又把我吊起来锤啦
by syta @ 2022-09-29 14:09:54