主席树（可持久化权值线段树）初探...
修改一个点只对树上logn个点有影响，所以新建logn个点就行了，总共新建mlogn个点。
查询一个区间[l,r]，相当于将数一个一个加进树，询问第l到第r次操作，这个可以用前缀解决。
板子不慢。。在第三页，KPM写指针的主席树貌似跑的飞快
#include<iostream> #include<cstdlib> #include<cstring> #include<cstdio> #include<algorithm> #define ll long long using namespace std; const int maxn=500010,inf=1e9; struct poi{int size,lt,rt;}a[maxn*20]; int n,m,x,y,z,sz,ans; int root[maxn]; void read(int &k) { int f=1;k=0;char c=getchar(); while(c<'0'||c>'9')c=='-'&&(f=-1),c=getchar(); while(c<='9'&&c>='0')k=k*10+c-'0',c=getchar(); k*=f; } void build(int &x,int l,int r,int cx) { a[++sz]=a[x];a[sz].size++;x=sz; if(l==r)return; int mid=(l+r)>>1; if(cx<=mid)build(a[x].lt,l,mid,cx); else build(a[x].rt,mid+1,r,cx); } int query(int x,int y,int l,int r,int cx) { if(l==r)return l; int mid=(l+r)>>1; if(a[a[y].lt].size-a[a[x].lt].size>=cx)return query(a[x].lt,a[y].lt,l,mid,cx); else if(a[a[y].rt].size-a[a[x].rt].size>=cx)return query(a[x].rt,a[y].rt,mid+1,r,cx); else return 0; } int main() { read(n);read(m); for(int i=1;i<=n;i++) { read(x); root[i]=root[i-1]; build(root[i],1,n,x); } for(int i=1;i<=m;i++) { read(x);read(y); printf("%d ",query(root[x-1],root[y],1,n,((y-x+1)>>1)+1)); } return 0; }