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

AC代码：

  1 #include<iostream>
  2 #include<algorithm>
  3 #include<cstdio>
  4 #define MAX 100005
  5 using namespace std;
  6 class TreeNode
  7 {
  8     public:
  9         int left, right, mid;
 10 };
 11 TreeNode node[4*MAX];
 12 int val[30][MAX];
 13 int ToLeft[30][MAX];
 14 int sorted[MAX];
 15 void BuildTree(int k, int d, int l, int r)
 16 {
 17     node[k].left = l;
 18     node[k].right = r;
 19     node[k].mid = (l + r) >> 1;
 20     if(l == r)
 21         return ;
 22     int mid = (l + r) >> 1;
 23     int lsame = mid - l + 1;
 24     for(int i = l;i <= r;i ++)
 25     {
 26         if(val[d][i] < sorted[mid])
 27             lsame --;
 28     }
 29     int lpos = l;
 30     int rpos = mid + 1;
 31     for(int i = l;i <= r;i ++)
 32     {
 33         if(i == l)
 34             ToLeft[d][i] = 0;
 35         else
 36             ToLeft[d][i] = ToLeft[d][i-1];
 37         if(val[d][i] < sorted[mid])
 38         {
 39             ToLeft[d][i] ++;
 40             val[d+1][lpos ++] = val[d][i];
 41         }
 42         else if(val[d][i] > sorted[mid])
 43         {
 44             val[d+1][rpos ++] = val[d][i];
 45         }
 46         else
 47         {
 48             if(lsame)
 49             {
 50                 ToLeft[d][i] ++;
 51                 val[d+1][lpos ++] = val[d][i];
 52                 lsame --;
 53             }
 54             else
 55                 val[d+1][rpos ++] = val[d][i];
 56         }
 57     }
 58     BuildTree(k << 1, d+1, l, mid);
 59     BuildTree(k << 1|1, d+1, mid + 1, r);
 60 }
 61 
 62 int Query(int l, int r, int k, int d, int idx)
 63 {
 64     if(l == r)
 65         return val[d][l];
 66     int s;
 67     int ss;
 68     if(l == node[idx].left)
 69     {
 70         s = ToLeft[d][r];
 71         ss = 0;
 72     }
 73     else
 74     {
 75         s = ToLeft[d][r] - ToLeft[d][l-1];
 76         ss = ToLeft[d][l-1];
 77     }
 78     if(s >= k)
 79     {
 80         int newl = node[idx].left + ss;
 81         int newr = node[idx].left + ss + s - 1;
 82         return Query(newl, newr, k, d + 1, idx << 1);
 83     }
 84     else
 85     {
 86         int mid = node[idx].mid;
 87         int b = r - l - s + 1;
 88         int bb = l - node[idx].left - ss;
 89         int newl = mid + bb + 1;
 90         int newr = mid + bb + b;
 91         return Query(newl, newr, k - s, d + 1,  idx << 1|1);
 92     }
 93 }
 94 
 95 int main(int argc, char const *argv[])
 96 {
 97     int c, n, m, l, r, k;
 98     //freopen("in.c", "r", stdin);
 99     scanf("%d", &c);
100     while(c--)
101     {
102         scanf("%d%d", &n, &m);
103         for(int i = 1;i <= n;i ++)
104         {
105             scanf("%d", &val[0][i]);
106             sorted[i] = val[0][i];
107         }
108         sort(sorted + 1, sorted + n + 1);
109         BuildTree(1, 0, 1, n);
110         for(int i = 0; i< m;i ++)
111         {
112             scanf("%d%d%d", &l, &r, &k);
113             printf("%d
", Query(l, r, k, 0, 1));
114         }
115     }
116     return 0;
117 }