hdu 4417 Super Mario/樹套樹，hdu4417
原題鏈接：http://acm.hdu.edu.cn/showproblem.php?pid=4417
題意很簡單，給定一個序列求一個區間 [L, R,]中小於等於H的元素的個數。
好像函數式線段樹可解吧，可弱弱的沙茶一直沒弄懂其精髓，只好用樹套樹暴力碾壓了
額樹套樹，線段樹的每一個節點套一個sb樹。
當查詢[l,r]區間中的值小於等於H的個數，先用線段樹找到相應的區間，
然後再查詢該區間下對應的平衡樹中小於等於H的個數，累加即可。
一直以為會超時，結果400+ms就過了，數據應該很弱吧(自己對拍了一組(N,M)10w規模的跑了2s多o(╯□╰)o)。
![]()
1 #include<cstdio>
2 #include<cstdlib>
3 #include<cstring>
4 #include<algorithm>
5 #define lc root<<1
6 #define rc root<<1|1
7 const int Max_N = 100100;
8 struct SBT{
9 int v, s, c;
10 SBT *ch[2];
11 inline void set(int _v = 0){
12 v = _v, c = s = 1;
13 ch[0] = ch[1] = null;
14 }
15 inline void push_up(){
16 s = ch[0]->s + ch[1]->s + c;
17 }
18 inline int cmp(int x) const{
19 return v == x ? -1 : x > v;
20 }
21 }*null, stack[Max_N << 3], *ptr[Max_N << 2];
22 int sz = 0, sum = 0, arr[Max_N];
23 void init(){
24 null = &stack[sz++];
25 null->v = null->s = null->c = 0;
26 }
27 inline void rotate(SBT* &x, int d){
28 SBT *k = x->ch[!d];
29 x->ch[!d] = k->ch[d];
30 k->ch[d] = x;
31 k->s = x->s;;
32 x->push_up();
33 x = k;
34 }
35 void Maintain(SBT* &x, int d){
36 if (x->ch[d] == null) return;
37 if (x->ch[d]->ch[d]->s > x->ch[!d]->s){
38 rotate(x, !d);
39 } else if (x->ch[d]->ch[!d]->s > x->ch[d]->s){
40 rotate(x->ch[d], d), rotate(x, !d);
41 } else {
42 return;
43 }
44 Maintain(x, 0), Maintain(x, 1);
45 }
46 void insert(SBT* &x, int v){
47 if (x == null){
48 x = &stack[sz++];
49 x->set(v);
50 } else {
51 x->s++;
52 int d = x->cmp(v);
53 if (-1 == d){
54 x->c++;
55 return;
56 }
57 insert(x->ch[d], v);
58 x->push_up();
59 Maintain(x, d);
60 }
61 }
62 int sbt_rank(SBT *x, int key){
63 int t, cur;
64 for (t = cur = 0; x != null;){
65 t = x->ch[0]->s;
66 if (key < x->v) x = x->ch[0];
67 else if (key >= x->v) cur += x->c + t, x = x->ch[1];
68 }
69 return cur;
70 }
71 void seg_built(int root, int l, int r){
72 ptr[root] = null;
73 for (int i = l; i <= r; i++) insert(ptr[root], arr[i]);
74 if (l == r) return;
75 int mid = (l + r) >> 1;
76 seg_built(lc, l, mid);
77 seg_built(rc, mid + 1, r);
78 }
79 void seg_rank(int root, int l, int r, int x, int y, int v){
80 if (x > r || y < l) return;
81 if (x <= l && y >= r){
82 sum += sbt_rank(ptr[root], v);
83 return;
84 }
85 int mid = (l + r) >> 1;
86 seg_rank(lc, l, mid, x, y, v);
87 seg_rank(rc, mid + 1, r, x, y, v);
88 }
89 int main(){
90 #ifdef LOCAL
91 freopen("in.txt", "r", stdin);
92 freopen("out.txt", "w+", stdout);
93 #endif
94 int i, t, n, m, a, b, c, k = 1;
95 scanf("%d", &t);
96 while (t--){
97 sz = 0, init();
98 scanf("%d %d", &n, &m);
99 printf("Case %d:\n", k++);
100 for (i = 1; i <= n; i++) scanf("%d", &arr[i]);
101 seg_built(1, 1, n);
102 while (m--){
103 scanf("%d %d %d", &a, &b, &c);
104 sum = 0;
105 seg_rank(1, 1, n, a + 1, b + 1, c);
106 printf("%d\n", sum);
107 }
108 }
109 return 0;
110 }
View Code
