划分树模版

  1 //hdu 2665
  2 #include <iostream>
  3 #include <cstdio>
  4 #include <algorithm>
  5 #include <cstring>
  6 
  7 using namespace std;
  8 
  9 #define ls rt<<1
 10 #define rs rt<<1|1
 11 #define lson l,m,ls
 12 #define rson m+1,r,rs
 13 
 14 #define MAXN 100010
 15 
 16 int len;
 17 int sorted[MAXN];
 18 int toLeft[20][MAXN],val[20][MAXN];
 19 
 20 void build(int d,int l,int r)
 21 {
 22     if(l==r)return;
 23     int m=(l+r)>>1;
 24     int lsame=m-l+1;//lsame表示和val_mid相等且分到左边的
 25     for(int i=l;i<=r;i++)
 26         if(val[d][i]<sorted[m])
 27             lsame--;////先假设左边的数(mid - l + 1)个都等于val_mid,然后把实际上小于val_mid的减去
 28     int lpos=l;
 29     int rpos=m+1;
 30     int same=0;
 31     for(int i=l;i<=r;i++)
 32     {
 33         if(i==l)
 34         {
 35             toLeft[d][i]=0;//toLeft[i]表示[ l , i ]区域里有多少个数分到左边
 36         }
 37         else
 38         {
 39             toLeft[d][i]=toLeft[d][i-1];
 40         }
 41         if(val[d][i]<sorted[m])
 42         {
 43             toLeft[d][i]++;
 44             val[d+1][lpos++]=val[d][i];
 45         }
 46         else if(val[d][i]>sorted[m])
 47         {
 48             val[d+1][rpos++]=val[d][i];
 49         }
 50         else
 51         {
 52             if(same<lsame)//有lsame的数是分到左边的
 53             {
 54                 same++;
 55                 toLeft[d][i]++;
 56                 val[d+1][lpos++]=val[d][i];
 57             }
 58             else
 59             {
 60                 val[d+1][rpos++]=val[d][i];
 61             }
 62         }
 63     }
 64     build(d+1,l,m);
 65     build(d+1,m+1,r);
 66 }
 67 
 68 
 69 int query(int L,int R,int k,int d,int l,int r)
 70 {
 71     if(l==r) return val[d][l];
 72     int s;//s表示[ L , R ]有多少个分到左边
 73     int ss;//ss表示 [l , L-1 ]有多少个分到左边
 74     int m=(l+r)>>1;
 75     if(L==l)
 76     {
 77         s=toLeft[d][R];
 78         ss=0;
 79     }
 80     else
 81     {
 82         s=toLeft[d][R]-toLeft[d][L-1];
 83         ss=toLeft[d][L-1];
 84     }
 85     if(s>=k)//有多于k个分到左边,显然去左儿子区间找第k个
 86         return query(l+ss,l+ss+s-1,k,d+1,l,m);
 87     else
 88         return query(m+L-l-ss+1,m-l-ss+R-s+1,k-s,d+1,m+1,r);
 89 }
 90 int main()
 91 {
 92     int n,m,t;
 93     scanf("%d",&t);
 94     while(t--)
 95     {
 96            scanf("%d%d",&n,&m);
 97            for(int i=1;i<=n;i++)
 98         {
 99             scanf("%d",&val[0][i]);
100             sorted[i]=val[0][i];
101            }
102            sort(sorted+1,sorted+n+1);
103            build(0,1,n);
104         while(m--)
105         {
106              int l,r,k;
107                scanf("%d%d%d",&l,&r,&k);
108                 printf("%d\n",query(l,r,k,0,1,n));
109            }
110     }
111     return 0;
112 }