首先用到bzoj2456的做法，因为要求这个数出现次数超过了一半，如果其与不同的数两两相消的话最终一定会剩下自身（如果不保证存在可能会剩下别的，但保证存在了只会剩下自身），然后再用可持久化线段树维护即可
1 #include<bits/stdc++.h> 2 using namespace std; 3 #define N 500005 4 #define mid (l+r>>1) 5 map<int,int>mat; 6 int V,n,m,x,y,r[N],a[N],f[N*20],ls[N*20],rs[N*20]; 7 void update(int k1,int &k2,int l,int r,int x){ 8 k2=++V; 9 if (l==r){ 10 f[k2]=f[k1]+1; 11 return; 12 } 13 ls[k2]=ls[k1]; 14 rs[k2]=rs[k1]; 15 if (x<=mid)update(ls[k1],ls[k2],l,mid,x); 16 else update(rs[k1],rs[k2],mid+1,r,x); 17 f[k2]=f[ls[k2]]+f[rs[k2]]; 18 } 19 int query(int k1,int k2,int l,int r,int x){ 20 if (l==r)return l; 21 if (f[ls[k2]]-f[ls[k1]]>x)return query(ls[k1],ls[k2],l,mid,x); 22 if (f[rs[k2]]-f[rs[k1]]>x)return query(rs[k1],rs[k2],mid+1,r,x); 23 return 0; 24 } 25 int main(){ 26 scanf("%d%d",&n,&m); 27 for(int i=1;i<=n;i++){ 28 scanf("%d",&x); 29 if (!mat[x]){ 30 mat[x]=++y; 31 a[y]=x; 32 } 33 update(r[i-1],r[i],1,n,mat[x]); 34 } 35 for(int i=1;i<=m;i++){ 36 scanf("%d%d",&x,&y); 37 printf("%d ",a[query(r[x-1],r[y],1,n,(y-x+1)/2)]); 38 } 39 }