HDU --2665

Kth number

Time Limit: 15000/5000 MS (Java/Others)    Memory Limit: 32768/32768 K (Java/Others)
Total Submission(s): 4349    Accepted Submission(s): 1381

Problem Description

Give you a sequence and ask you the kth big number of a inteval.

Input

The first line is the number of the test cases. 
For each test case, the first line contain two integer n and m (n, m <= 100000), indicates the number of integers in the sequence and the number of the quaere. 
The second line contains n integers, describe the sequence. 
Each of following m lines contains three integers s, t, k. 
[s, t] indicates the interval and k indicates the kth big number in interval [s, t]

Output

For each test case, output m lines. Each line contains the kth big number.

Sample Input

1
10 1
1 4 2 3 5 6 7 8 9 0
1 3 2

Sample Output

2

AC代码：

 #include<iostream>
 #include<algorithm>
 #include<cstdio>
 #define MAX 100005
 using namespace std;
 class TreeNode
 {
     public:
         int left, right, mid;
 };
 TreeNode node[*MAX];
 int val[][MAX];
 int ToLeft[][MAX];
 int sorted[MAX];
 void BuildTree(int k, int d, int l, int r)
 {
     node[k].left = l;
     node[k].right = r;
     node[k].mid = (l + r) >> ;
     if(l == r)
         return ;
     int mid = (l + r) >> ;
     int lsame = mid - l + ;
     for(int i = l;i <= r;i ++)
     {
         if(val[d][i] < sorted[mid])
             lsame --;
     }
     int lpos = l;
     int rpos = mid + ;
     for(int i = l;i <= r;i ++)
     {
         if(i == l)
             ToLeft[d][i] = ;
         else
             ToLeft[d][i] = ToLeft[d][i-];
         if(val[d][i] < sorted[mid])
         {
             ToLeft[d][i] ++;
             val[d+][lpos ++] = val[d][i];
         }
         else if(val[d][i] > sorted[mid])
         {
             val[d+][rpos ++] = val[d][i];
         }
         else
         {
             if(lsame)
             {
                 ToLeft[d][i] ++;
                 val[d+][lpos ++] = val[d][i];
                 lsame --;
             }
             else
                 val[d+][rpos ++] = val[d][i];
         }
     }
     BuildTree(k << , d+, l, mid);
     BuildTree(k << |, d+, mid + , r);
 }

 int Query(int l, int r, int k, int d, int idx)
 {
     if(l == r)
         return val[d][l];
     int s;
     int ss;
     if(l == node[idx].left)
     {
         s = ToLeft[d][r];
         ss = ;
     }
     else
     {
         s = ToLeft[d][r] - ToLeft[d][l-];
         ss = ToLeft[d][l-];
     }
     if(s >= k)
     {
         int newl = node[idx].left + ss;
         int newr = node[idx].left + ss + s - ;
         return Query(newl, newr, k, d + , idx << );
     }
     else
     {
         int mid = node[idx].mid;
         int b = r - l - s + ;
         int bb = l - node[idx].left - ss;
         int newl = mid + bb + ;
         int newr = mid + bb + b;
         return Query(newl, newr, k - s, d + ,  idx << |);
     }
 }

 int main(int argc, char const *argv[])
 {
     int c, n, m, l, r, k;
     //freopen("in.c", "r", stdin);
     scanf("%d", &c);
     while(c--)
     {
         scanf("%d%d", &n, &m);
         for(int i = ;i <= n;i ++)
         {
             scanf("%d", &val[][i]);
             sorted[i] = val[][i];
         }
         sort(sorted + , sorted + n + );
         BuildTree(, , , n);
         for(int i = ; i< m;i ++)
         {
             scanf("%d%d%d", &l, &r, &k);
             printf("%d\n", Query(l, r, k, , ));
         }
     }
     return ;
 }