首页 > 代码库 > 划分树 模板
划分树 模板
#include <iostream> #include <cstdio> #include <algorithm> using namespace std; #define N 100500 #define MID ((l+r)>>1) int a[N],s[N],t[20][N],num[20][N],n,m; // void build(int lft,int rht,int ind) // { // if(lft==rht) return; // // int mid=MID(lft,rht); // int same=mid-lft+1,ln=lft,rn=mid+1; // for(int i=lft;i<=rht;i++) // if(valu[ind][i]<order[mid]) same--; // for(int i=lft;i<=rht;i++) // { // int flag=0; // if((valu[ind][i]<order[mid])||(valu[ind][i]==order[mid]&&same))//划分到左区间 // { // flag=1; // valu[ind+1][ln++]=valu[ind][i]; // lsum[ind][i]=lsum[ind][i-1]+valu[ind][i]; // if(valu[ind][i]==order[mid]) same--; // } // else //划分到右区间 // { // valu[ind+1][rn++]=valu[ind][i]; // lsum[ind][i]=lsum[ind][i-1]; // } // num[ind][i]=num[ind][i-1]+flag;//划分到左区间的个数 // } // build(lft,mid,ind+1); // build(mid+1,rht,ind+1); // } // int query(int st,int ed,int k,int lft,int rht,int ind)//子区间[st,ed],大区间[lft,rht],层数ind // { // if(lft==rht) return valu[ind][lft]; // // int mid=MID(lft,rht); // int lx=num[ind][st-1]-num[ind][lft-1];//在左区间不属于子区间的个数 // int ly=num[ind][ed]-num[ind][st-1];//有多少个进入左区间 // int rx=st-1-lft+1-lx;//在右区间不属于子区间的个数 // int ry=ed-st+1-ly;//有多少个进入右区间 // if(ly>=k) return query(lft+lx,lft+lx+ly-1,k,lft,mid,ind+1); // else // { // isum+=lsum[ind][ed]-lsum[ind][st-1]; // st=mid+1+rx; // ed=mid+1+rx+ry-1; // return query(st,ed,k-ly,mid+1,rht,ind+1); // } // } void Build(int c,int l,int r) { int lm=MID-l+1,lp=l,rp=MID+1; for(int i=l;i<=MID;i++) lm-=s[i]<s[MID]; for(int i=l;i<=r;i++) { if( i==l ) num[c][i]=0; else num[c][i]=num[c][i-1]; if( t[c][i]==s[MID] ) { if( lm ) { lm--; num[c][i]++; t[c+1][lp++]=t[c][i]; } else t[c+1][rp++]=t[c][i]; } else if( t[c][i]<s[MID] ) { num[c][i]++; t[c+1][lp++]=t[c][i]; } else t[c+1][rp++]=t[c][i]; } if( l<r ) Build(c+1,l,MID),Build(c+1,MID+1,r); } int Query(int c,int l,int r,int ql,int qr,int k) { if( l==r ) return t[c][l]; int s,ss; if( l==ql ) s=0,ss=num[c][qr]; else s=num[c][ql-1],ss=num[c][qr]-num[c][ql-1]; if( k<=ss ) return Query(c+1,l,MID,l+s,l+s+ss-1,k); else return Query(c+1,MID+1,r,MID+1+ql-l-s,MID+1+qr-l-s-ss,k-ss); } int main() { scanf("%d%d",&n,&m); for(int i=1;i<=n;i++) { scanf("%d",&a[i]); s[i]=t[0][i]=a[i]; } sort(s+1,s+1+n); Build(0,1,n); while( m-- ) { int l,r,k; scanf("%d%d%d",&l,&r,&k); printf("%d\n",Query(0,1,n,l,r,k)); } return 0; } /* 10 10 0 5 2 7 5 4 3 8 7 7 2 8 3 3 5 2 1 3 1 1 9 4 1 2 2 3 5 3 5 5 1 4 6 3 1 5 4 5 7 3 8 6 2 4 3 5 8 1 7 6 2 7 2 */
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。