bzoj 3196/tyvj p1730 二逼平衡樹，bzoj3196
原題鏈接：http://www.tyvj.cn/p/1730
樹套樹。。。
如下：
![]()
1 #include<cstdio>
2 #include<cstdlib>
3 #include<cstring>
4 #include<algorithm>
5 #define lc root<<1
6 #define rc root<<1|1
7 #define INF 0x3f3f3f3f
8 #define _max(a,b) ((a)>(b)?(a):(b))
9 #define _min(a,b) ((a)>(b)?(b):(a))
10 const int Max_N = 50100;
11 struct SBT *null;
12 struct SBT{
13 int v, s, c;
14 SBT *ch[2];
15 SBT(int _v = 0) : v(_v){
16 c = s = 1;
17 ch[0] = ch[1] = null;
18 }
19 inline void push_up(){
20 s = ch[0]->s + ch[1]->s + c;
21 }
22 inline int cmp(int x) const{
23 return v == x ? -1 : x > v;
24 }
25 }stack[Max_N << 5], *ptr[Max_N << 2];
26 int sz = 0, sum = 0, arr[Max_N];
27 void init(){
28 null = &stack[sz++];
29 null->s = null->c = 0;
30 }
31 inline void rotate(SBT* &x, int d){
32 SBT *k = x->ch[!d];
33 x->ch[!d] = k->ch[d];
34 k->ch[d] = x;
35 k->s = x->s;;
36 x->push_up();
37 x = k;
38 }
39 void Maintain(SBT* &x, int d){
40 if (x->ch[d] == null) return;
41 if (x->ch[d]->ch[d]->s > x->ch[!d]->s){
42 rotate(x, !d);
43 } else if (x->ch[d]->ch[!d]->s > x->ch[d]->s){
44 rotate(x->ch[d], d), rotate(x, !d);
45 } else {
46 return;
47 }
48 Maintain(x, 0), Maintain(x, 1);
49 }
50 void insert(SBT* &x, int v){
51 if (x == null){
52 x = &stack[sz++];
53 x->v = v;
54 x->ch[0] = x->ch[1] = null;
55 } else {
56 x->s++;
57 int d = x->cmp(v);
58 if (-1 == d){
59 x->c++;
60 return;
61 }
62 insert(x->ch[d], v);
63 x->push_up();
64 Maintain(x, d);
65 }
66 }
67 void del(SBT* &x, int v){
68 if (x == null) return;
69 int d = x->cmp(v);
70 x->s--;
71 if (-1 == d){
72 if (x->c > 1){
73 x->c--;
74 } else if (x->ch[0] == null || x->ch[1] == null){
75 x = x->ch[0] != null ? x->ch[0] : x->ch[1];
76 } else {
77 SBT *ret = x->ch[1];
78 for (; ret->ch[0] != null; ret = ret->ch[0]);
79 del(x->ch[1], x->v = ret->v);
80 }
81 } else {
82 del(x->ch[d], v);
83 }
84 if (x != null) x->push_up();
85 }
86 int sbt_rank(SBT *x, int v){
87 int t = 0, cur = 0;
88 for (; x != null;){
89 t = x->ch[0]->s;
90 if (v == x->v) return cur + t;
91 else if (v < x->v) x = x->ch[0];
92 else cur += t + x->c, x = x->ch[1];
93 }
94 return cur;
95 }
96 int sbt_pred(SBT *x, int v){
97 int t = -1;
98 for (; x != null;){
99 if (x->v < v){
100 t = x->v;
101 x = x->ch[1];
102 }
103 else x = x->ch[0];
104 }
105 return t == -1 ? -INF : t;
106 }
107 int sbt_succ(SBT *x, int v){
108 int t = -1;
109 for (; x != null;){
110 if (x->v > v){
111 t = x->v;
112 x = x->ch[0];
113 }
114 else x = x->ch[1];
115 }
116 return t == -1 ? INF : t;
117 }
118 void seg_built(int root, int l, int r){
119 ptr[root] = null;
120 for (int i = l; i <= r; i++) insert(ptr[root], arr[i]);
121 if (l == r) return;
122 int mid = (l + r) >> 1;
123 seg_built(lc, l, mid);
124 seg_built(rc, mid + 1, r);
125 }
126 void seg_rank(int root, int l, int r, int x, int y, int v){
127 if (x > r || y < l) return;
128 if (x <= l && y >= r){
129 sum += sbt_rank(ptr[root], v);
130 return;
131 }
132 int mid = (l + r) >> 1;
133 seg_rank(lc, l, mid, x, y, v);
134 seg_rank(rc, mid + 1, r, x, y, v);
135 }
136 void seg_modify(int root, int l, int r, int pos, int v){
137 if (pos > r || pos < l) return;
138 del(ptr[root], arr[pos]);
139 insert(ptr[root], v);
140 if (l == r) return;
141 int mid = (l + r) >> 1;
142 seg_modify(lc, l, mid, pos, v);
143 seg_modify(rc, mid + 1, r, pos, v);
144 }
145 int seg_pred(int root, int l, int r, int x, int y, int v){
146 if (x > r || y < l) return -INF;
147 if (x <= l && y >= r) return sbt_pred(ptr[root], v);
148 int mid = (l + r) >> 1;
149 int v1 = seg_pred(lc, l, mid, x, y, v);
150 int v2 = seg_pred(rc, mid + 1, r, x, y, v);
151 return _max(v1, v2);
152 }
153 int seg_succ(int root, int l, int r, int x, int y, int v){
154 if (x > r || y < l) return INF;
155 if (x <= l && y >= r) return sbt_succ(ptr[root], v);
156 int mid = (l + r) >> 1;
157 int v1 = seg_succ(lc, l, mid, x, y, v);
158 int v2 = seg_succ(rc, mid + 1, r, x, y, v);
159 return _min(v1, v2);
160 }
161 void gogo(int n, int a, int b, int k){
162 int mid, l = 0, r = 100000000;
163 while (l < r){
164 sum = 0;
165 mid = (l + r) >> 1;
166 seg_rank(1, 1, n, a, b, mid);
167 if (sum < k) l = mid + 1;
168 else r = mid;
169 }
170 printf("%d\n", l - 1);
171 }
172 int main(){
173 #ifdef LOCAL
174 freopen("in.txt", "r", stdin);
175 freopen("out.txt", "w+", stdout);
176 #endif
177 init();
178 int i, n, m, a, b, c, d;
179 scanf("%d %d", &n, &m);
180 for (i = 1; i <= n; i++) scanf("%d", &arr[i]);
181 seg_built(1, 1, n);
182 while (m--){
183 scanf("%d", &a);
184 switch (a){
185 case 1:
186 sum = 1;
187 scanf("%d %d %d", &b, &c, &d);
188 seg_rank(1, 1, n, b, c, d);
189 printf("%d\n",sum);
190 break;
191 case 2:
192 scanf("%d %d %d", &b, &c, &d);
193 gogo(n, b, c, d);
194 break;
195 case 3:
196 scanf("%d %d", &b, &c);
197 seg_modify(1, 1, n, b, c), arr[b] = c;
198 break;
199 case 4:
200 scanf("%d %d %d", &b, &c, &d);
201 printf("%d\n", seg_pred(1, 1, n, b, c, d));
202 break;
203 case 5:
204 scanf("%d %d %d", &b, &c, &d);
205 printf("%d\n", seg_succ(1, 1, n, b, c, d));
206 break;
207 }
208 }
209 return 0;
210 }
View Code
