POJ2104 K-th Number(线段树)

 1 #include <cstdio>
 2 #include <cstring>
 3 #include <iostream>
 4 #include <algorithm>
 5 
 6 using namespace std;
 7 
 8 #define rep(i, a, b)    for (int i(a); i <= (b); ++i)
 9 #define lson        i << 1, L, mid
10 #define rson        i << 1 | 1, mid + 1, R
11 
12 const int N = 100010;
13 
14 struct node{
15     int l, r;
16 } tree[N << 2];
17 
18 int a[N], b[N], d[N * 20];
19 int cnt = 0;
20 int n, q;
21 
22 
23 void build(int i, int L, int R){
24     if (L == R){
25         d[++cnt] = a[L];
26         tree[i].l = cnt;
27         tree[i].r = cnt;
28         return;
29     }
30 
31     int mid = (L + R) >> 1;
32     build(lson);
33     build(rson);
34     tree[i].l = cnt + 1;
35     int l1 = tree[i << 1].l, r1 = tree[i << 1].r;
36     int l2 = tree[i << 1 | 1].l, r2 = tree[i << 1 | 1].r;
37 
38     while (l1 <= r1 && l2 <= r2){
39         if (d[l1] < d[l2]) d[++cnt] = d[l1++];
40         else d[++cnt] = d[l2++];
41     }
42 
43     while (l1 <= r1) d[++cnt] = d[l1++];
44     while (l2 <= r2) d[++cnt] = d[l2++];
45     tree[i].r = cnt;
46 }
47 
48 int binary(int l, int r, int tmp){
49     if (tmp >= d[r]) return r - l + 1;
50     if (tmp < d[l]) return 0;
51     int L = l, R = r;
52     while (L < R){
53         int mid = (L + R) >> 1;
54         if (d[mid] > tmp) R = mid; else L = mid + 1;
55     }
56 
57     return L - l;
58 }
59 
60 int query(int i, int L, int R, int l, int r, int tmp){
61     if (l <= L && R <= r) return binary(tree[i].l, tree[i].r, tmp);
62     int mid = (L + R) >> 1, ret = 0;
63     if (l <= mid) ret += query(lson, l, r, tmp);
64     if (r > mid) ret += query(rson, l, r, tmp);
65     return ret;
66 }
67 
68 int main(){
69 
70 
71     scanf("%d%d", &n, &q);
72     rep(i, 1, n) scanf("%d", a + i);
73     build(1, 1, n);
74     rep(i, 1, n) b[i] = a[i];
75     sort(b + 1, b + n + 1);
76 
77     rep(i, 1, q){
78         int l, r, tmp;
79         scanf("%d%d%d", &l, &r, &tmp);
80         int s = 1, t = n;
81         while (s < t){
82             int mid = (s + t) >> 1;
83             int t1 = query(1, 1, n, l, r, b[mid]);
84             if (t1 < tmp) s = mid + 1;
85             else t = mid;
86         }
87 
88 
89         printf("%d
", b[s]);
90     }
91 
92     return 0;
93 }