POJ 2104 主席树

链接：

代码：

31 struct Node { int l, r, sum; }T[MAXN * 40];
32 int a[MAXN], root[MAXN], cnt;
33 VI v;
34 
35 void update(int l, int r, int &x, int y, int pos) {
36     T[++cnt] = T[y], T[cnt].sum++, x = cnt;
37     if (l == r) return;
38     int m = (l + r) >> 1;
39     if (m >= pos) update(l, m, T[x].l, T[y].l, pos);
40     else update(m + 1, r, T[x].r, T[y].r, pos);
41 }
42 
43 int query(int l, int r, int x, int y, int k) {
44     if (l == r) return l;
45     int m = (l + r) >> 1;
46     int sum = T[T[y].l].sum - T[T[x].l].sum;
47     if (sum >= k) return query(l, m, T[x].l, T[y].l, k);
48     else return query(m + 1, r, T[x].r, T[y].r, k - sum);
49 }
50 
51 int main() {
52     int n, m;
53     cin >> n >> m;
54     rep(i, 1, n + 1) scanf("%d", a + i), v.pb(a[i]);
55     sort(all(v));
56     v.erase(unique(all(v)), v.end());
57     rep(i, 1, n + 1) a[i] = upper_bound(all(v), a[i]) - v.begin();
58     rep(i, 1, n + 1) update(1, n, root[i], root[i - 1], a[i]);
59     while (m--) {
60         int i, j, k;
61         scanf("%d%d%d", &i, &j, &k);
62         printf("%d
", v[query(1, n, root[i - 1], root[j], k) - 1]);
63     }
64     return 0;
65 }