K-th Number POJ

K-th Number

第一道主席树...
本来暑假就该学会的东西拖到了寒假orz...
要不是看到了这个博客估计还没去学 -----链接
 1 #include <iostream>
 2 #include <cstring>
 3 #include <cstdio>
 4 #include <cmath>
 5 #include <algorithm>
 6 using namespace std;
 7 #define lson l, m
 8 #define rson m + 1, r
 9 const int maxn = 1e5+10;
10 int L[maxn<<5], R[maxn<<5], sum[maxn<<5];
11 int tot;
12 int a[maxn], T[maxn], Hash[maxn];
13 
14 int build(int l, int r){
15     int rt = (++tot);
16     sum[rt] = 0;
17     if(l < r){
18         int m = (l + r) >> 1;
19          L[rt] = build(lson);
20          R[rt] = build(rson);
21     }
22     return rt;
23 }
24 
25 int update(int pre, int l, int r, int x){
26     int rt = (++tot);
27     L[rt] = L[pre], R[rt] = R[pre], sum[rt] = sum[pre] + 1;
28     if(l < r){
29         int m = (l + r) >> 1;
30         if(x <= m) L[rt] = update(L[pre], lson, x);
31         else R[rt] = update(R[pre], rson, x);
32     }
33     return rt;
34 }
35 
36 int query(int u, int v, int l, int r, int k){
37     if(l >= r) return l;
38     int m = (l + r) >> 1;
39     int num = sum[L[v]] - sum[L[u]];
40     if(num >= k) return query(L[u], L[v], lson, k);
41     else return query(R[u], R[v], rson, k - num);
42 }
43 
44 
45 int main(){
46     int n, m;
47     while(scanf("%d %d", &n, &m) != EOF){
48         tot = 0;
49         for(int i = 1; i <= n; i++){
50             scanf("%d", &a[i]);
51             Hash[i] = a[i];
52         }
53         sort(Hash + 1, Hash + 1 + n);
54         int d = unique(Hash + 1, Hash + 1 + n) - Hash - 1;
55         T[0] = build(1, d);
56         for(int i = 1; i <= n; i++){
57             int x = lower_bound(Hash + 1, Hash + 1 + d, a[i]) - Hash;
58             //cout<<"=== " <<x<<"  === 
";
59             T[i] = update(T[i-1], 1, d, x);
60         }
61         while(m--){
62             int l, r, k;
63             scanf("%d %d %d", &l, &r, &k);
64             int x = query(T[l-1], T[r], 1, d, k);
65             printf("%d
", Hash[x]);
66         }
67     }
68 
69 }
View Code
Kth number

HDU - 2665
同上~