HDU4417 Super Mario (主席树)

主席树另一模板。

查询的是[L,R]中<=h的个数。

 1 #include <bits/stdc++.h>
 2 using namespace std;
 3 #define lc tr[i].ch[0]
 4 #define rc tr[i].ch[1]
 5 #define Lc tr[j].ch[0]
 6 #define Rc tr[j].ch[1]
 7 #define mid ((l + r) >> 1)
 8 const int N = 1e5 + 10;
 9 int n, m, a[N], b[N];
10 int cnt, rt[N];
11 struct node {
12     int num, ch[2];
13 }tr[N * 20];
14 void update(int &i, int j, int l, int r, int k) {
15     i = ++ cnt;
16     tr[i] = tr[j];
17     tr[i].num ++;
18     if (l == r) return ;
19     if (k <= mid) update(lc, Lc, l, mid, k);
20     else update(rc, Rc, mid + 1, r, k);
21 }
22 int query(int i, int j, int l, int r, int k) {
23     if (l == r) return tr[j].num - tr[i].num;
24     int ans = 0;
25     if (k <= mid) ans += query(lc, Lc, l, mid, k);
26     else {
27         ans += tr[Lc].num - tr[lc].num;
28         ans += query(rc, Rc, mid + 1, r, k);
29     }
30     return ans;
31 }
32 int main() {
33     scanf("%d %d", &n, &m);
34     for (int i = 1; i <= n; i ++) {
35         scanf("%d", &a[i]);
36         b[i] = a[i];
37     }
38     sort(b + 1, b + n + 1);
39     int tot = unique(b + 1, b + n + 1) - b - 1;
40     cnt = 0, rt[0] = 0;
41     for (int i = 1; i <= n; i ++)
42         update(rt[i], rt[i - 1], 1, tot, lower_bound(b + 1, b + tot + 1, a[i]) - b);
43     int l, r, h;
44     while (m --) {
45         scanf("%d %d %d", &l, &r, &h);
46         l ++, r ++;
47         int k = upper_bound(b + 1, b + tot + 1, h) - b - 1;//!!!!!
48         if (k) printf("%d\n", query(rt[l - 1], rt[r], 1, tot, k));
49         else printf("0\n");//有可能h<所有a[i] 此时k = 0 
50     }    
51     return 0;
52 }