hdu2665 划分树

2019-04-13 17:35发布

站内文章 / 模拟电子
11185 0 1200
模拟了快排的过程 得到的一棵树就是划分树了 静态查询区间第k大很方便 #include #include #include #include using namespace std; #define maxn 111111 int tol[30][maxn],s[30][maxn]; int sorted[maxn]; void build(int dep,int l,int r){ if(l==r)return ; int mid=((l+r)>>1); int lpos=l,rpos=mid+1; int same=(mid-l+1); for(int i=l;i<=r;++i) if(s[dep][i]0){ s[dep+1][lpos++] = s[dep][i] ; same--; } else s[dep+1][rpos++] = s[dep][i]; tol[dep][i]=tol[dep][l-1]+lpos-l; } build(dep+1,l,mid); build(dep+1,mid+1,r); } int query(int dep,int l,int r,int L,int R,int k){ if(l == r)return s[dep][l]; int cnt=tol[dep][r]-tol[dep][l-1]; int mid=((L+R)>>1); if(cnt>=k){ int newl=L+tol[dep][l-1]-tol[dep][L-1]; int newr=newl+cnt-1; return query(dep+1,newl,newr,L,mid,k); } else{ int newr=r+(tol[dep][R]-tol[dep][r]); int newl=newr-(r-l+1-cnt)+1; return query(dep+1,newl,newr,mid+1,R,k-cnt); } } int main(){ int t;scanf("%d",&t); while(t--){ int n,m,a,b,k; memset(tol,0,sizeof tol); memset(s,0,sizeof s); scanf("%d%d",&n,&m); for(int i=1;i<=n;++i){ scanf("%d",&s[0][i]); sorted[i]=s[0][i]; } sort(sorted+1,sorted+1+n); build(0,1,n); while(m--){ scanf("%d%d%d",&a,&b,&k); printf("%d ",query(0,a,b,1,n,k)); } } return 0; }

热门文章