1 ///划分树模板，找区间第k小的数 2 const int mx=1e5+5; 3 int tree[30][mx]; 4 int sortt[mx]; 5 int sum[30][mx]; 6  7 void build(int l,int r,int c) 8 { 9     if (l==r) return ;10     int m=(l+r)>>1;11     int isame=m-l+1;12     int pl=l,pr=m+1;13     for (int i=l;i<m;i++)14         if (tree[c][i]<sortt[m]) isame--;15     for (int i=l;i<=r;i++){16         if (i==l) sum[c][i]=0;17         else sum[c][i]=sum[c][i-1];18         if (tree[c][i]<sortt[m]){19             tree[c+1][pl++]=tree[c][i];20             sum[c][i]++;21         }22         else if ( tree[c][i]==sortt[m]&&isame){23             isame--;24             tree[c+1][pl++]=tree[c][i];25             sum[c][i]++;26         }27         else tree[c+1][pr++]=tree[c][i];28     }29     build(l,m,c+1);30     build(m+1,r,c+1);31 }32 33 int query(int L,int R,int l,int r,int c,int k){34     if (L==R) return tree[c][L];35     int s,ss;36     if (l==L){37         s=0;38         ss=sum[c][r];39     }40     else{41         s=sum[c][l-1];42         ss=sum[c][r]-s;43     }44     int m=(L+R)>>1;45     if (k<=ss) return query(L,m,L+s,L+s+ss-1,c+1,k);46     return query(m+1,R,m+1+l-L-s,m+1+r-L-s-ss,c+1,k-ss);47 }