poj 2104 （划分树模板）

 1 #include <cstdio>
 2 #include <algorithm>
 3 #include <cstring>
 4 #include <cmath>
 5 using namespace std;
 6 typedef long long LL;
 7 const int maxn = 1e5 + 10;
 8 int a[maxn], sorted[maxn];
 9 int num[20][maxn], val[20][maxn];
10 
11 void build(int l, int r, int ceng) {
12     if (l == r) return ;
13     int mid = (l + r) >> 1, same = mid - l + 1;
14     for (int i = l ; i <= r ; i++)
15         if (val[ceng][i] < sorted[mid]) same--;
16     int ln = l, rn = mid + 1;
17     for (int i = l ; i <= r ; i++) {
18         if (i == l) num[ceng][i] = 0;
19         else num[ceng][i] = num[ceng][i - 1];
20         if (val[ceng][i] < sorted[mid] || val[ceng][i] == sorted[mid] && same > 0) {
21             val[ceng + 1][ln++] = val[ceng][i];
22             num[ceng][i]++;
23             if (val[ceng][i] == sorted[mid]) same--;
24         } else val[ceng + 1][rn++] = val[ceng][i];
25     }
26     build(l, mid, ceng + 1);
27     build(mid + 1, r, ceng + 1);
28 }
29 
30 int query(int ceng, int L, int R, int l, int r, int k) {
31     if (L == R)  return val[ceng][L];
32     int lsum;
33     if (l == L) lsum = 0;
34     else lsum = num[ceng][l - 1];
35     int tot = num[ceng][r] - lsum;
36     if (tot >= k) return query(ceng + 1, L, (L + R) / 2, L + lsum, L + num[ceng][r] - 1, k);
37     else {
38         int lr = (L + R) / 2 + 1 + (l - L - lsum);
39         return query(ceng + 1, (L + R) / 2 + 1, R, lr, lr + r - l + 1 - tot - 1, k - tot);
40     }
41 }
42 
43 int main() {
44     int n, m, l, r, k;
45     while(scanf("%d%d", &n, &m) != EOF) {
46         for (int i = 1 ; i <= n ; i++) {
47             scanf("%d", &val[0][i]);
48             sorted[i] = val[0][i];
49         }
50         sort(sorted + 1, sorted + n + 1);
51         build(1, n, 0);
52         while(m--) {
53             scanf("%d%d%d", &l, &r, &k);
54             printf("%d\n", query(0, 1, n, l, r, k ));
55         }
56     }
57     return 0;
58 }