这个题比一般主席树还要简单，但是用来练习主席树再好不过了，在这里我再放一下主席树板子。
代码：
#include<iostream> #include<cstdio> #include<cmath> #include<ctime> #include<queue> #include<algorithm> #include<cstring> using namespace std; #define duke(i,a,n) for(register int i = a;i <= n;i++) #define lv(i,a,n) for(register int i = a;i >= n;i--) #define clean(a) memset(a,0,sizeof(a)) const int INF = 1 << 30; typedef long long ll; typedef double db; template <class T> void read(T &x) { char c; bool op = 0; while(c = getchar(), c < '0' || c > '9') if(c == '-') op = 1; x = c - '0'; while(c = getchar(), c >= '0' && c <= '9') x = x * 10 + c - '0'; if(op) x = -x; } template <class T> void write(T x) { if(x < 0) putchar('-'), x = -x; if(x >= 10) write(x / 10); putchar('0' + x % 10); } const int N = 6e5 + 5; struct node { int l,r,sum; }tree[N * 20]; int root[N]; int cnt = 0,n,m; void insert(int lst,int &now,int l,int r,int pos) { tree[++cnt] = tree[lst]; now = cnt; ++tree[now].sum; if(l == r) return; int mid = (l + r) >> 1; if(pos <= mid) insert(tree[lst].l,tree[now].l,l,mid,pos); else insert(tree[lst].r,tree[now].r,mid + 1,r,pos); } int query(int lst,int now,int l,int r,int val) { if(l == r) return tree[now].sum > val ? l : 0;; int tmp = tree[tree[now].l].sum - tree[tree[lst].l].sum; // cout<<lst<<" "<<now<<" "<<l<<" "<<r<<endl; int mid = (l + r) >> 1; if(tmp > val) return query(tree[lst].l,tree[now].l,l,mid,val); else if(tree[tree[now].r].sum - tree[tree[lst].r].sum > val) return query(tree[lst].r,tree[now].r,mid + 1,r,val); return 0; } int a,tot; int main() { read(n);read(m); duke(i,1,n) { read(a); insert(root[i - 1],root[i],1,n,a); } /*for(int i = 1;i <= 20;i++) { printf("%d %d %d ",tree[i].l,tree[i].r,tree[i].sum); }*/ while(m--) { int x,y; read(x);read(y); printf("%d ",query(root[x - 1],root[y],1,n,(y - x + 1) >> 1)); } return 0; }