挺裸的，没啥可讲的。
不带修改的主席树裸题
Code:
#include<cstdio>
#include<algorithm>
using namespace std;
const int maxn = 500000 + 5;
int n, m ,root[maxn];
struct Chair_Tree{
int cnt_Tree;
int lson[maxn * 50], rson[maxn * 50], sumv[maxn * 50];
void build(int l, int r, int &o){
if(l > r) return ;
o = ++cnt_Tree;
if(l == r) return ;
int mid = (l + r) >> 1;
build(l, mid, lson[o]);
build(mid + 1, r, rson[o]);
}
int insert(int l, int r, int pos, int o){
int oo = ++cnt_Tree;
lson[oo] = lson[o], rson[oo] = rson[o], sumv[oo] = sumv[o] + 1;
if(l == r) return oo;
int mid = (l + r) >> 1;
if(pos <= mid) lson[oo] = insert(l, mid, pos, lson[o]);
else rson[oo] = insert(mid + 1, r, pos, rson[o]);
return oo;
}
int query(int l, int r, int k, int pre_o, int cur_o){
if(l == r) return l;
int lsum = sumv[lson[cur_o]] - sumv[lson[pre_o]];
int cur_sum = sumv[cur_o] - sumv[pre_o];
int mid = (l + r) >> 1;
if(k <= lsum) return query(l, mid, k, lson[pre_o], lson[cur_o]);
else if(cur_sum - lsum >= k) return query(mid + 1, r, k, rson[pre_o], rson[cur_o]);
else return 0;
}
}T;
int main(){
scanf("%d%d",&n,&m);
T.build(1, n, root[0]);
for(int i = 1;i <= n; ++i)
{
int cur_num;
scanf("%d",&cur_num);
root[i] = T.insert(1, n, cur_num, root[i - 1]);
}
while(m--){
int l, r, k;
scanf("%d%d",&l,&r);
k = (r - l + 1)/2 + 1;
printf("%d
", T.query(1, n, k, root[l - 1], root[r]));
}
return 0;
}