就是裸的主席树嘛。。。
表扬一下自己1A
#include<cstdio> #include<iostream> #include<cstring> #include<cstdlib> #include<algorithm> #include<cmath> using namespace std; struct chairman_tree { int lc,rc,c; }tr[1100000];int trlen,rt[51000]; int maketree(int now,int l,int r,int p) { if(now==0) { now=++trlen; tr[now].lc=tr[now].rc=0; tr[now].c=0; } tr[now].c++; if(l==r)return now; else { int mid=(l+r)/2; if(p<=mid)tr[now].lc=maketree(tr[now].lc,l,mid,p); else tr[now].rc=maketree(tr[now].rc,mid+1,r,p); } return now; } int merge(int x,int y) { if(x==0||y==0)return x+y; tr[x].c+=tr[y].c; tr[x].lc=merge(tr[x].lc,tr[y].lc); tr[x].rc=merge(tr[x].rc,tr[y].rc); return x; } //-------------init------------------- int check(int x,int y,int l,int r,int tot) { if(l==r)return l; int lsum=tr[tr[y].lc].c-tr[tr[x].lc].c; int rsum=tr[tr[y].rc].c-tr[tr[x].rc].c; int mid=(l+r)/2; if(lsum>=tot/2+1)return check(tr[x].lc,tr[y].lc,l,mid,tot); else if(rsum>=tot/2+1)return check(tr[x].rc,tr[y].rc,mid+1,r,tot); else return 0; } int main() { int n,m=50000,Q,x; scanf("%d%d",&n,&Q); trlen=0;memset(rt,0,sizeof(rt)); for(int i=1;i<=n;i++) { scanf("%d",&x); rt[i]=maketree(rt[i],1,m,x); rt[i]=merge(rt[i],rt[i-1]); } int l,r; while(Q--) { scanf("%d%d",&l,&r); printf("%d ",check(rt[l-1],rt[r],1,m,r-l+1)); } return 0; }