POJ/2104.partitiontree.cc

   1 #include <cstdio>
   2 #include <cstring>
   3 #include <algorithm>
   4
   5 using namespace std;
   6
   7 const int maxn=100001;
   8
   9 int sorted[maxn];
  10 int toLeft[20][maxn],val[20][maxn];
  11
  12 void build(int l, int r, int d, int k)
  13 //d:dep, k:order
  14 {
  15         if (l==r) return;
  16         int mid=l+r>>1,lsame=mid-l+1;
  17         for (int i=l; i<=r; ++i) if (val[d][i]<sorted[mid]) --lsame;
  18         int lpos=l,rpos=mid+1,same=0;
  19         for (int i=l; i<=r; ++i)
  20         {
  21                 if (i==l) toLeft[d][i]=0; else toLeft[d][i]=toLeft[d][i-1];
  22                 if (val[d][i]<sorted[mid])
  23                 {
  24                         ++toLeft[d][i];
  25                         val[d+1][lpos++]=val[d][i];
  26                 }
  27                 else if (val[d][i]>sorted[mid]) val[d+1][rpos++]=val[d][i];
  28                 else
  29                 {
  30                         if (same<lsame)
  31                         {
  32                                 ++same,++toLeft[d][i];
  33                                 val[d+1][lpos++]=val[d][i];
  34                         }
  35                         else val[d+1][rpos++]=val[d][i];
  36                 }
  37         }
  38         build(l,mid,d+1,k<<1);
  39         build(mid+1,r,d+1,k<<1|1);
  40 }
  41
  42 int query(int l, int r, int p, int q, int rank, int d, int k)
  43 {
  44         if (l==r) return val[d][l];
  45         int s,ss;
  46         if (l==p) s=toLeft[d][r],ss=0; else
  47                 s=toLeft[d][r]-toLeft[d][l-1],ss=toLeft[d][l-1];
  48         int m=p+q>>1;
  49         if (s>=rank)
  50         {
  51                 int newl=p+ss,newr=p+ss+s-1;
  52                 return query(newl,newr,p,m,rank,d+1,k<<1);
  53         }
  54         else
  55         {
  56                 int bb=l-p-ss,b=r-l+1-s;
  57                 int newl=m+bb+1,newr=m+bb+b;
  58                 return query(newl,newr,m+1,q,rank-s,d+1,k<<1|1);
  59         }
  60 }
  61
  62 int main()
  63 {
  64         int n,m;
  65         scanf("%d%d",&n,&m);
  66         for (int i=1; i<=n; ++i) scanf("%d",&sorted[i]);
  67         memcpy(val[0],sorted,sizeof(sorted));
  68         sort(sorted+1,sorted+n+1);
  69         build(1,n,0,1);
  70         while (m--)
  71         {
  72                 int l,r,k;
  73                 scanf("%d%d%d",&l,&r,&k);
  74                 printf("%d\n",query(l,r,1,n,k,0,1));
  75         }
  76         return 0;
  77 }