对于询问[i,j]
在[1..n]中我们看看小于mid的数字有多少个，显然如果个数的两倍<=j-i+1那么[1..mid]中就不存在这样的数，
反之检测大于mid有多少个
当然 如果两个都不行，就返回0
是可以递归的
#include<bits/stdc++.h> #define N 500005 using namespace std; int n,m,a[N],rt[N*100],lson[N*100],rson[N*100],tot,sum[N*100]; void build(int &now,int l,int r) { now=++tot; if(l==r) return; int mid=(l+r)>>1; build(lson[now],l,mid); build(rson[now],mid+1,r); } int update(int now,int l,int r,int x) { int newnode=++tot; lson[newnode]=lson[now]; rson[newnode]=rson[now]; sum[newnode]=sum[now]+1; if(l==r) return newnode; int mid=(l+r)>>1; if(x<=mid) lson[newnode]=update(lson[newnode],l,mid,x); else rson[newnode]=update(rson[newnode],mid+1,r,x); //pushup(now); return newnode; } inline int query(int x,int y,int l,int r,int range) { if(l==r) return l; int mid=(l+r)>>1; if(2*(sum[lson[y]]-sum[lson[x]])>range) return query(lson[x],lson[y],l,mid,range); if(2*(sum[rson[y]]-sum[rson[x]])>range) return query(rson[x],rson[y],mid+1,r,range); else return 0; } int main() { ios::sync_with_stdio(false); cin.tie(NULL);cout.tie(NULL); cin>>n>>m; build(rt[0],1,n); for(int i=1;i<=n;i++) cin>>a[i]; for(int i=1;i<=n;i++) { rt[i]=update(rt[i-1],1,n,a[i]); } for(int i=1;i<=m;i++) { int l,r; cin>>l>>r; cout<<query(rt[l-1],rt[r],1,n,r-l+1)<<'\n'; } return 0; }转载于:https://www.cnblogs.com/Patrickpwq/articles/9801520.html
