1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59
|
using namespace std; typedef long long ll; const int maxn = 5e5+10; int n,q,a[maxn]; int T[maxn],lson[maxn*30],rson[maxn*30],c[maxn*30],tot; int (int l,int r){ int ret=tot++; if(l!=r){ int mid=l+r>>1; lson[ret]=build(l,mid); rson[ret]=build(mid+1,r); }return ret; } int update(int rt,int pos){ int nrt=tot++; c[nrt]=c[rt]+1; int ret=nrt,l=1,r=n; while(l<r){ int mid=l+r>>1; if(pos<=mid){ lson[nrt]=tot++,rson[nrt]=rson[rt]; nrt=lson[nrt];rt=lson[rt];r=mid; } else { lson[nrt]=lson[rt],rson[nrt]=tot++; nrt=rson[nrt];rt=rson[rt];l=mid+1; } c[nrt]=c[rt]+1; } return ret; } int query(int lrt,int rrt,int lim){ int l=1,r=n; while(l<r){ int mid=l+r>>1; if(c[lson[rrt]]-c[lson[lrt]]>lim){ lrt=lson[lrt];rrt=lson[rrt]; r=mid; } else if(c[rson[rrt]]-c[rson[lrt]]>lim){ lrt=rson[lrt];rrt=rson[rrt]; l=mid+1; } else return 0; } return l; } int main(){ scanf("%d%d",&n,&q); for(int i=1;i<=n;i++)scanf("%d",a+i); T[0]=build(1,n); for(int i=1;i<=n;i++){ T[i]=update(T[i-1],a[i]); } int l,r; while(q--){ scanf("%d%d",&l,&r); printf("%dn",query(T[l-1],T[r],(r-l+1)/2)); } return 0; }
|
近期评论