如下源码
```cpp
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<iostream>
//using namespace std;
const int maxn=500005;
#define ll long long
template <typename T>
inline T const& read(T &x){
x=0;int fh=1;
char ch=getchar();
while(!isdigit(ch)){
if(ch=='-')
fh=-1;
ch=getchar();
}
while(isdigit(ch)){
x=(x<<3)+(x<<1)+ch-'0';
ch=getchar();
}
x*=fh;
}
int n,m;
int A[maxn];
struct chairman_tree{
int l,r,cnt;
chairman_tree *ls,*rs;
};
struct chairman_tree byte[maxn*19],*pool=byte,*root[maxn];
chairman_tree* New(){
return ++pool;
}
chairman_tree* update(chairman_tree* &node){
node->cnt=node->ls->cnt+node->rs->cnt;
}
inline bool outofrange(chairman_tree* &node,const int L,const int R){
return (node->r<L)||(R<node->l);
}
chairman_tree* Build(const int L,const int R){
chairman_tree *u=New();
u->l=L,u->r=R;
if(L==R){
u->cnt++;
u->ls=u->rs=NULL;
}else{
int Mid=(L+R)>>1;
u->ls=Build(L,Mid);
u->rs=Build(Mid+1,R);
update(u);
}
return u;
}
void modify(chairman_tree* &pre,chairman_tree* &now,const int p){
*now=*pre;
if(pre->l==p && pre->r==p){
now->cnt++;
return;
}
if(!outofrange(pre->ls,p,p)){
now->ls=New();
modify(pre->ls,now->ls,p);
update(now);
}else{
now->rs=New();
modify(pre->rs,now->rs,p);
update(now);
}
}
int query(chairman_tree* <ree,chairman_tree* &rtree,const int half){
if(rtree->cnt-ltree->cnt<=half)//不满足条件
return 0;
if(ltree->l==ltree->r)//已经找到
return ltree->l;
int lcnt=rtree->ls->cnt-ltree->ls->cnt;//左区间的数的个数
if(lcnt>half) return query(ltree->ls,rtree->ls,half);//左区间的数的个数是否大于一半
else return query(ltree->rs,rtree->rs,half);
}
signed main(){
read(n),read(m);
for(int i=1;i<=n;++i)
read(A[i]);
root[0]=Build(1,n);
printf("QAQ\n");
for(int i=1;i<=n;++i)
modify(root[i-1],root[i]=New(),A[i]);
for(int i=0,l,r;i<m;++i)
printf("%d\n",query(root[l-1],root[r],(r-l+1)>>1));
return 0;
}
```
为了卡空间，后来又把结构体里 l r 变成参数带着了，但是还是 MLE
by 一铭君一 @ 2021-07-03 16:31:33
不卡啊
by rui_er @ 2021-07-03 16:31:43
@[rui_er](/user/122461)
是因为指针双倍空间的问题么
by 一铭君一 @ 2021-07-03 16:33:03
@[一铭君一](/user/307143) 不清楚，我不是指针写法，之前过了
by rui_er @ 2021-07-03 16:33:42
~~建议二分数组长度找到合适大小~~
by koishi_offical @ 2021-07-03 16:39:58
@[第114514恋厨](/user/147401) 评测姬：我是猴子吗？
by hanyuchen2019 @ 2021-07-03 16:42:54
@[第114514恋厨](/user/147401)
~~已经二分了，但是 no solution 我也没办法~~
by 一铭君一 @ 2021-07-03 16:52:50
@[一铭君一](/user/307143) 你再二分试试，我就是二分出来的（大雾
by FANTASTlC @ 2021-07-03 16:57:50
不卡吧，一遍就过了
by ctldragon @ 2021-09-30 09:48:28