2015 HSYIT代码暂存楼[0]

smileandyxu

仿照hr567的格式开楼~

大家可以把没有做完的题目代码暂存在这里留一个备份，免得再重写或是遇到一些麻烦的事情......

smileandyxu

1. #include <iostream>
   
2. #include <cstring>
   
3. #include <cstdio>
   
4. #include <cctype>
   
5. #define INF 0x7fffffff
   
6. using namespace std;
   
7. inline int getint()
   
8. {
   
9.     char c = getchar();
   
10.     while (!isdigit(c))
    
11.         c = getchar();
    
12.     int x = 0;
    
13.     while (isdigit(c)) {
    
14.         x = x * 10 + c - '0';
    
15.         c = getchar();
    
16.     }
    
17.     return x;
    
18. }
    
19. int END[4000001], FLOW[4000001], NEXT[4000001];
    
20. int DIS[1000001], GAP[1000001], HEAD[1000001];
    
21. int S, T;
    
22. int n, m, eid;
    
23. void addedge(int u, int v, int w)
    
24. {
    
25.     END[eid] = v, FLOW[eid] = w, NEXT[eid] = HEAD[u], HEAD[u] = eid++;
    
26.     END[eid] = u, FLOW[eid] = 0, NEXT[eid] = HEAD[v], HEAD[v] = eid++;
    
27. }
    
28. void init()
    
29. {
    
30.     n = getint();
    
31.     m = getint();
    
32.     for (int i = 1; i <= m * n; ++i)
    
33.         HEAD[i] = -1;
    
34.     for (int i = 1; i <= n; ++i) {
    
35.         for (int j = 1, w; j <= m - 1; ++j) {
    
36.             w = getint();
    
37.             addedge((i - 1) * m + j, (i - 1) * m + j + 1, w);
    
38.         }
    
39.     }
    
40.     for (int i = 1; i <= n - 1; ++i) {
    
41.         for (int j = 1, w; j <= m; ++j) {
    
42.             w = getint();
    
43.             addedge((i - 1) * m + j, i * m + j, w);
    
44.         }
    
45.     }
    
46.     for (int i = 1; i <= n - 1; ++i) {
    
47.         for (int j = 1, w; j <= m - 1; ++j) {
    
48.             w = getint();
    
49.             addedge((i - 1) * m + j, i * m + j + 1, w);
    
50.         }
    
51.     }
    
52. }
    
53. int augment(int pos, int flow)
    
54. {
    
55.     if (pos == m * n)
    
56.         return flow;
    
57.     else {
    
58.         int cur, aug;
    
59.         cur = 0;
    
60.         for (int i = HEAD[pos]; i != -1; i = NEXT[i]) {
    
61.             int j = END[i];
    
62.             if (FLOW[i] && DIS[pos] == DIS[j] + 1) {
    
63.                 aug = augment(j, min(flow - cur, FLOW[i]));
    
64.                 FLOW[i] -= aug;
    
65.                 FLOW[i ^ 1] += aug;
    
66.                 cur += aug;
    
67.                 if (cur == flow || DIS[S] >= m * n)
    
68.                     return cur;
    
69.             }
    
70.         }
    
71.         if (!cur) {
    
72.             if (--GAP[DIS[pos]] == 0) {
    
73.                 DIS[S] = m * n;
    
74.                 return cur;
    
75.             }
    
76.             int mindis = m * n;
    
77.             for (int i = HEAD[pos]; i != -1; i = NEXT[i])
    
78.                 if (FLOW[i])
    
79.                     mindis = min(mindis, DIS[END[i]] + 1);
    
80.             DIS[pos] = mindis;
    
81.             ++GAP[DIS[pos]];
    
82.         }
    
83.         return cur;
    
84.     }
    
85. }
    
86. int isap()
    
87. {
    
88.     int max_flow = 0;
    
89.     S = 1;
    
90.     T = m * n;
    
91.     GAP[0] = m * n; //***//
    
92.     while (DIS[S] < m * n)
    
93.         max_flow += augment(S, INF);
    
94.     return max_flow;
    
95. }
    
96. int main()
    
97. {
    
98.     init();
    
99.     if (m == 1 && n == 1)
    
100.         printf("%d", 0);
     
101.     else
     
102.         printf("%d", isap());
     
103.     return 0;
     
104. }
     

复制代码

smileandyxu

1. #include <iostream>
   
2. #define INF 0x3fffffff
   
3. using namespace std;
   
4. inline int abs(int x)
   
5. {
   
6.     return (x > 0 ? x : -x);
   
7. }
   
8. struct node {
   
9.     node* ch[2];
   
10.     int v;
    
11.     int s;
    
12. };
    
13. node* null = new node();
    
14. node* newnode(int x)
    
15. {
    
16.     node* tmp = new node();
    
17.     tmp->ch[0] = null;
    
18.     tmp->ch[1] = null;
    
19.     tmp->v = x;
    
20.     tmp->s = 1;
    
21.     return tmp;
    
22. }
    
23. node* prec(node* o, node* p, int v)
    
24. {
    
25.     if (o == null)
    
26.         return p;
    
27.     else if (v < o->v)
    
28.         return prec(o->ch[0], p, v);
    
29.     return prec(o->ch[1], o, v);
    
30. }
    
31. node* succ(node* o, node* p, int v)
    
32. {
    
33.     if (o == null)
    
34.         return p;
    
35.     else if (v > o->v)
    
36.         return prec(o->ch[1], p, v);
    
37.     return prec(o->ch[0], o, v);
    
38. }
    
39. void rotate(node* &o, int d)
    
40. {
    
41.     node* k = o->ch[d ^ 1];
    
42.     o->ch[d ^ 1] = k->ch[d];
    
43.     k->ch[d] = o;
    
44.     k->s = o->s;
    
45.     o->s = o->ch[0]->s + o->ch[1]->s + 1;
    
46.     o = k;
    
47. }
    
48. void maintain(node* &o, bool d)
    
49. {
    
50.     if (!d) {
    
51.         if (o->ch[0]->ch[0]->s > o->ch[1]->s)
    
52.             rotate(o, 1);
    
53.         else if (o->ch[0]->ch[1]->s > o->ch[1]->s) {
    
54.             rotate(o->ch[0], 0);
    
55.             rotate(o, 1);
    
56.         }
    
57.         else
    
58.             return;
    
59.     }
    
60.     else {
    
61.         if (o->ch[1]->ch[1]->s > o->ch[0]->s)
    
62.             rotate(o, 0);
    
63.         else if (o->ch[1]->ch[0]->s > o->ch[0]->s) {
    
64.             rotate(o->ch[1], 1);
    
65.             rotate(o, 0);
    
66.         }
    
67.         else
    
68.             return;
    
69.     }
    
70.     maintain(o->ch[0], false);
    
71.     maintain(o->ch[1], true);
    
72.     maintain(o, false);
    
73.     maintain(o, true);
    
74. }
    
75. void insert(node* &o, int v)
    
76. {
    
77.     if (o == null)
    
78.         o = newnode(v);
    
79.     else {
    
80.         ++o->s;
    
81.         insert(o->ch[v >= o->v], v);
    
82.         maintain(o, false);
    
83.         maintain(o, true);
    
84.     }
    
85. }
    
86. void print(node* o)
    
87. {
    
88.     if (o != null) {
    
89.         print(o->ch[0]);
    
90.         cout << o->v << " ";
    
91.         print(o->ch[1]);
    
92.     }
    
93. }
    
94. node* T;
    
95. int n, ans;
    
96. int main()
    
97. {
    
98.     null->ch[0] = null;
    
99.     null->ch[1] = null;
    
100.     T = null;
     
101.     cin >> n;
     
102.     for (int i = 0, x; i != n; ++i) {
     
103.         cin >> x;
     
104.         node* p = prec(T, null, x);
     
105.         node* q = succ(T, null, x);
     
106.         int t = ans;
     
107.         if (p == null)
     
108.             ans += q->v - x;
     
109.         else if (q == null)
     
110.             ans += x - p->v;
     
111.         else
     
112.             ans += min(q->v - x, x - p->v);
     
113.         cout <<"==>" <<  ans - t << endl;
     
114.         insert(T, x);
     
115.     }
     
116.     cout << ans;
     
117.     return 0;
     
118. }
     

复制代码

smileandyxu

1. #include <iostream>
   
2. #include <algorithm>
   
3. #include <stack>
   
4. using namespace std;
   
5. int P[200001];
   
6. int Q[200001];
   
7. int head, tail;
   
8. int m, d, t, n;
   
9. int main()
   
10. {
    
11.     cin >> m >> d;
    
12.     for (int i = 0; i != m; ++i) {
    
13.         char c;
    
14.         int x;
    
15.         cin >> c >> x;
    
16.         if (c == 'A') {
    
17.             ++n;
    
18.             x = (x + t) % d;
    
19.             while (head < tail && Q[tail - 1] <= x)
    
20.                 --tail;
    
21.             Q[tail] = x;
    
22.             P[tail] = tail;
    
23.             ++tail;
    
24.         }
    
25.         if (c == 'Q') {
    
26.             int p = lower_bound(P, P + tail, tail - x) - P;
    
27.             t = Q[p];
    
28.             cout << Q[p] << endl;
    
29.         }
    
30.     }
    
31.     return 0;
    
32. }
    
33. /*
    
34. 8 10000
    
35. A 101
    
36. A 200
    
37. Q 1
    
38. Q 2
    
39. A 10
    
40. Q 1
    
41. Q 2
    
42. Q 3
    
43. */
    

复制代码

smileandyxu

1. #include <iostream>
   
2. #define father(x) (x >> 1)
   
3. #define lchild(x) (x << 1)
   
4. #define rchild(x) (x << 1 | 1)
   
5. using namespace std;
   
6. struct node {
   
7.     int sum;
   
8.     int add;
   
9.     int left;
   
10.     int right;
    
11. };
    
12. node T[800001];
    
13. int L, R;
    
14. int n, m;
    
15. void update(int i)
    
16. {
    
17.     while (i > 0) {
    
18.         T[i].sum = T[lchild(i)].sum + T[rchild(i)].sum;
    
19.         i = father(i);
    
20.     }
    
21. }
    
22. void build(int i, int l, int r)
    
23. {
    
24.     T[i].left = l;
    
25.     T[i].right = r;
    
26.     if (l != r) {
    
27.         int d = (l + r) >> 1;
    
28.         build(lchild(i), l, d);
    
29.         build(rchild(i), d + 1, r);
    
30.         T[i].sum = T[lchild(i)].sum + T[rchild(i)].sum;
    
31.     }
    
32. }
    
33. int add(int i, int l, int r, int x)
    
34. {
    
35.     if (l == T[i].left && r == T[i].right) {
    
36.         T[i].sum += x * (r - l + 1);
    
37.         T[i].add += x;
    
38.         return x * (r - l + 1);
    
39.     }
    
40.     else {
    
41.         int d = (T[i].left + T[i].right) >> 1;
    
42.         int s = 0;
    
43.         if (l <= d)
    
44.             s += add(lchild(i), l, d, x);
    
45.         if (r >= d + 1)
    
46.             s += add(rchild(i), d + 1, r, x);
    
47.         T[i].sum += s;
    
48.         return s;
    
49.     }
    
50. }
    
51. void pushdown(int i)
    
52. {
    
53.     int len = (T[i].right - T[i].left + 1) >> 1;
    
54.     T[lchild(i)].sum += T[i].add * len;
    
55.     T[rchild(i)].sum += T[i].add * len;
    
56.     T[lchild(i)].add += T[i].add;
    
57.     T[rchild(i)].add += T[i].add;
    
58.     T[i].add = 0;
    
59. }
    
60. int query(int i, int l, int r)
    
61. {
    
62.     if (l == T[i].left && r == T[i].right)
    
63.         return T[i].sum;
    
64.     else {
    
65.         int d = (T[i].left + T[i].right) >> 1;
    
66.         T[i].sum = 0;
    
67.         pushdown(i);
    
68.         if (l <= d)
    
69.             T[i].sum += query(lchild(i), l, d);
    
70.         if (r >= d + 1)
    
71.             T[i].sum += query(rchild(i), d + 1, r);
    
72.         return T[i].sum;
    
73.     }
    
74. }
    
75. void print()
    
76. {
    
77.     cout << " ==> ";
    
78.     for (int i = 1; i <= R; ++i)
    
79.         cout << T[i].sum << " ";
    
80.     cout << endl;
    
81. }
    
82. int main()
    
83. {
    
84.     cin >> n;
    
85.     L = 1;
    
86.     while (L < n)
    
87.         L <<= 1;
    
88.     R = L * 2 - 1;
    
89.     cout << L << endl;
    
90.     for (int i = 0; i != n; ++i)
    
91.         cin >> T[L + i].sum;
    
92.     build(1, 1, L);
    
93.     cin >> m;
    
94.     for (int i = 0, p, l, r, x; i != m; ++i) {
    
95.         cin >> p;
    
96.         if (p == 1) {
    
97.             cin >> l >> r >> x;
    
98.             add(1, l, r, x);
    
99.         }
    
100.         if (p == 2) {
     
101.             cin >> l >> r;
     
102.             cout << query(1, l, r) << endl;
     
103.         }
     
104.         print();
     
105.     }
     
106.     return 0;
     
107. }
     
108. /*
     
109. 6
     
110. 1 1 4 5 2 3
     
111. 4
     
112. 1 1 3 4
     
113. 1 2 4 3
     
114. 2 2 3
     
115. 2 1 4
     
116. */
     

复制代码

smileandyxu

1. #include <iostream>
   
2. #include <set>
   
3. #define INF 0x6fffffff
   
4. using namespace std;
   
5. set<int> S;
   
6. int n, ans;
   
7. int main()
   
8. {
   
9.     cin >> n;
   
10.     cin >> ans;
    
11.     S.insert(ans);
    
12.     for (int i = 0, x; i != n - 1; ++i) {
    
13.         cin >> x;
    
14.         set<int>::iterator iter = S.find(x);
    
15.         int minx = INF;
    
16.         ++iter;
    
17.         if (iter != S.end())
    
18.             minx = min(minx, *iter - x);
    
19. 
    
20.     }
    
21.     return 0;
    
22. }
    

复制代码

smileandyxu

1. #include <iostream>
   
2. #include <vector>
   
3. #include <queue>
   
4. #define INF 0x3fffffff
   
5. #define eps 1e-8
   
6. using namespace std;
   
7. struct edge {
   
8.     int end;
   
9.     int len;
   
10.     int vel;
    
11. };
    
12. vector<edge> V[201];
    
13. double D[201][501];
    
14. int F[201][501];
    
15. int G[201][501];
    
16. int m, n, d;
    
17. void add(int a, int b, int v, int l)
    
18. {
    
19.     edge tmp;
    
20.     tmp.end = b;
    
21.     tmp.vel = v;
    
22.     tmp.len = l;
    
23.     V[a].push_back(tmp);
    
24. }
    
25. void spfa()
    
26. {
    
27.     queue<int> Q;
    
28.     queue<int> P;
    
29.     bool B[201][501];
    
30.     Q.push(0);
    
31.     P.push(70);
    
32.     B[0][70] = true;
    
33.     D[0][70] = 0;
    
34.     while (!Q.empty()) {
    
35.         int k = Q.front();
    
36.         int t = P.front();
    
37.         B[k][t] = false;
    
38.         Q.pop();
    
39.         P.pop();
    
40.         for (int i = 0; i != V[k].size(); ++i) {
    
41.             if (V[k][i].vel == 0) {
    
42.                 if (D[V[k][i].end][t] - D[k][t] + double(V[k][i].len) / double(t) > eps) {
    
43.                     D[V[k][i].end][t] = D[k][t] + double(V[k][i].len) / double(t);
    
44.                     F[V[k][i].end][t] = k;
    
45.                     G[V[k][i].end][t] = t;
    
46.                     cout << "change: " << V[k][i].end << "#" << t << " ====> " << k << "#" << t << endl;
    
47.                     if (!B[V[k][i].end][t]) {
    
48.                         Q.push(V[k][i].end);
    
49.                         P.push(t);
    
50.                         B[V[k][i].end][t] = true;
    
51.                     }
    
52.                 }
    
53.             }
    
54.             else {
    
55.                 if (D[V[k][i].end][V[k][i].vel] - D[k][t] + double(V[k][i].len) / double(V[k][i].vel) > eps) {
    
56.                     D[V[k][i].end][V[k][i].vel] = D[k][t] + double(V[k][i].len) / double(V[k][i].vel);
    
57.                     F[V[k][i].end][V[k][i].vel] = k;
    
58.                     G[V[k][i].end][V[k][i].vel] = t;
    
59.                     cout << "change: " << V[k][i].end << "#" << V[k][i].vel << " ====> " << k << "#" << t << endl;
    
60.                     if (!B[V[k][i].end][V[k][i].vel]) {
    
61.                         Q.push(V[k][i].end);
    
62.                         P.push(V[k][i].vel);
    
63.                         B[V[k][i].end][V[k][i].vel] = true;
    
64.                     }
    
65.                 }
    
66.             }
    
67.         }
    
68.     }
    
69. }
    
70. int cnt;
    
71. void output(int x, int y)
    
72. {
    
73.     if (cnt <= 30)
    
74.     cout << x << "#" << y << endl;
    
75.     ++cnt;
    
76.     if (F[x][y] != x && x != 0)
    
77.         output(F[x][y], G[x][y]);
    
78.     cout << x << " ";
    
79. }
    
80. int main()
    
81. {
    
82.     cin >> n >> m >> d;
    
83.     for (int i = 0, a, b, v, l; i != m; ++i) {
    
84.         cin >> a >> b >> v >> l;
    
85.         add(a, b, v, l);
    
86.     }
    
87.     for (int i = 0; i != n; ++i) {
    
88.         for (int j = 0; j <= 500; ++j) {
    
89.             D[i][j] = INF;
    
90.             F[i][j] = i;
    
91.         }
    
92.     }
    
93.     spfa();
    
94.     double tmp = INF;
    
95.     int k = 0;
    
96.     for (int i = 0; i <= 500; ++i) {
    
97.         if (tmp - D[d][i] > eps) {
    
98.             tmp = D[d][i];
    
99.             k = i;
    
100.         }
     
101.     }
     
102.     cout << "==================================" << endl;
     
103.     output(d, k);
     
104.     return 0;
     
105. }
     

复制代码

smileandyxu

1. #include <iostream>
   
2. #include <vector>
   
3. #include <queue>
   
4. #define esp 1e-7
   
5. using namespace std;
   
6. struct edge {
   
7.     int beg;
   
8.     int end;
   
9.     int len;
   
10.     int vel;
    
11. };
    
12. vector<edge> V;
    
13. double D[201][501];
    
14. int P[201];
    
15. int m, n, d;
    
16. void add(int a, int b, int v, int l)
    
17. {
    
18.     edge tmp;
    
19.     tmp.beg = a;
    
20.     tmp.end = b;
    
21.     tmp.vel = v;
    
22.     tmp.len = l;
    
23.     V.push_back(tmp);
    
24. }
    
25. void spfa()
    
26. {
    
27.    
    
28. }
    
29. int main()
    
30. {
    
31.     cin >> n >> m >> d;
    
32.     for (int i = 0, a, b, v, l; i != n; ++i) {
    
33.         cin >> a >> b >> v >> l;
    
34.         add(a, b, v, l);
    
35.     }
    
36.     spfa();
    
37.    
    
38.     return 0;
    
39. }
    

复制代码

smileandyxu

1. #include <iostream>
   
2. #include <algorithm>
   
3. #include <set>
   
4. using namespace std;
   
5. set<int> G[501][501];
   
6. int F[501][501];
   
7. int B[501];
   
8. int C[501];
   
9. int W[501];
   
10. int P[501];
    
11. int L[501];
    
12. int n;
    
13. void mysearch(int i, int p)
    
14. {
    
15.     if (F[i][p] != 0 || i == 0)
    
16.         return;
    
17.     else if (W[i] > p) {
    
18.         mysearch(B[i], p);
    
19.         F[i][p] = F[B[i]][p];
    
20.         G[i][p] = G[B[i]][p];
    
21.     }
    
22.     else if (W[i] == p) {
    
23.         F[i][p] = L[i];
    
24.         G[i][p].insert(i);
    
25.     }
    
26.     else {
    
27.         mysearch(B[i], p);
    
28.         mysearch(B[i], p - W[i]);
    
29.         mysearch(C[i], p - W[i]);
    
30.         F[i][p] = F[B[i]][p];
    
31.         G[i][p] = G[B[i]][p];
    
32.         for (int k = 0; k <= p - W[i]; ++k) {
    
33.             if (k <= P[i] && p - W[i] - k <= P[i] && p - W[i] - k >= 0) {
    
34.                 mysearch(B[i], k);
    
35.                 mysearch(C[i], p - W[i] - k);
    
36.                 if (F[B[i]][k] + F[C[i]][p - W[i] - k] > F[i][p]) {
    
37.                     F[i][p] = F[B[i]][k] + F[C[i]][p - W[i] - k];
    
38.                     for (set<int>::iterator iter = G[B[i]][k].begin(); iter != G[B[i]][k].end(); ++iter)
    
39.                         G[i][p].insert(*iter);
    
40.                     for (set<int>::iterator iter = G[C[i]][p - W[i] - k].begin(); iter != G[C[i]][p - W[i] - k].end(); ++iter)
    
41.                         G[i][p].insert(*iter);
    
42.                 }
    
43.             }
    
44.         }
    
45.     }
    
46. }
    
47. int main()
    
48. {
    
49.     cin >> n;
    
50.     for (int i = 1, t; i <= n; ++i) {
    
51.         cin >> t >> W[i] >> P[i] >> L[i];
    
52.         int k = C[t];
    
53.         C[t] = i;
    
54.         B[i] = k;
    
55.     }
    
56.     for (int i = W[1]; i <= P[1] + W[1]; ++i)
    
57.         mysearch(1, P[1] + W[1]);
    
58.     cout << F[1][P[1] + W[1]];
    
59.     cout << endl;
    
60.     for (set<int>::iterator iter = G[1][P[1] + W[1]].begin(); iter != G[1][P[1] + W[1]].end(); ++iter)
    
61.         cout << *iter << " ";
    
62.     return 0;
    
63. }
    

复制代码

smileandyxu

1. #include <iostream>
   
2. using namespace std;
   
3. struct node {
   
4.     node* ch[2];
   
5.     int v;
   
6.     int s;
   
7.     int cmp(int x) const
   
8.     {
   
9.         if (x == v)
   
10.             return -1;
    
11.         return x < v ? 0 : 1;
    
12.     }
    
13. };
    
14. node* null = new node();
    
15. node* newnode(int x)
    
16. {
    
17.     node* tmp = new node();
    
18.     tmp->ch[0] = null;
    
19.     tmp->ch[1] = null;
    
20.     tmp->v = x;
    
21.     tmp->s = 1;
    
22.     return tmp;
    
23. }
    
24. int rank(node* o, int x)
    
25. {
    
26.     if (o == null)
    
27.         return -1;
    
28.     if (o->cmp(x) == -1)
    
29.         return 1;
    
30.     else if (o->cmp(x) == 0)
    
31.         return rank(o->ch[0], x);
    
32.     else
    
33.         return o->ch[0]->s + rank(o->ch[1], x);
    
34. }
    
35. node* find_kth(node* o, int k)
    
36. {
    
37.     if (k == 1) {
    
38.         while (o->ch[0] != null)
    
39.             o = o->ch[0];
    
40.         return o;
    
41.     }
    
42.     else {
    
43.         if (o->ch[0]->s >= k)
    
44.             return find_kth(o->ch[0], k);
    
45.         else
    
46.             return find_kth(o->ch[1], k - o->ch[0]->s);
    
47.     }
    
48. }
    
49. node* precursor(node* o, int x)
    
50. {
    
51.     return find_kth(o, rank(o, x) - 1);
    
52. }
    
53. node* successor(node* o, int x)
    
54. {
    
55. 
    
56.     return find_kth(o, rank(o, x) + 1);
    
57. }
    
58. void rotate(node* &o, int d)
    
59. {
    
60.     node* k = o->ch[d ^ 1];
    
61.     o->ch[d ^ 1] = k->ch[d];
    
62.     k->ch[d] = o;
    
63.     k->s = o->s;
    
64.     o->s = o->ch[0]->s + o->ch[1]->s;
    
65.     o = k;
    
66. }
    
67. void maintain(node* o, bool d)
    
68. {
    
69.     if (!d) {
    
70.         if (o->ch[0]->ch[0]->s > o->ch[1]->s)
    
71.             rotate(o, 1);
    
72.         else if (o->ch[0]->ch[1]->s > o->ch[1]->s) {
    
73.             rotate(o->ch[0], 0);
    
74.             rotate(o, 1);
    
75.         }
    
76.         else
    
77.             return;
    
78.     }
    
79.     else {
    
80.         if (o->ch[1]->ch[1]->s > o->ch[0]->s)
    
81.             rotate(o, 0);
    
82.         else if (o->ch[1]->ch[0]->s > o->ch[0]->s) {
    
83.             rotate(o->ch[1], 1);
    
84.             rotate(o, 0);
    
85.         }
    
86.         else
    
87.             return;
    
88.     }
    
89.     cout << "#";
    
90.     maintain(o->ch[0], false);
    
91.     maintain(o->ch[1], true);
    
92.     maintain(o, false);
    
93.     maintain(o, true);
    
94. }
    
95. void insert(node* &o, int x)
    
96. {
    
97.     if (o == null)
    
98.         o = newnode(x);
    
99.     else {
    
100.         if (o->cmp(x) == 0)
     
101.             insert(o->ch[0], x);
     
102.         else
     
103.             insert(o->ch[1], x);
     
104.         ++o->s;
     
105.         maintain(o, false);
     
106.         maintain(o, true);
     
107.     }
     
108. }
     
109. void erase(node* &o, int x)
     
110. {
     
111.     if (o->cmp(x) == -1) {
     
112.         if (o->ch[0] == null && o->ch[1] == null)
     
113.             o = null;
     
114.         else if (o->ch[0] == null)
     
115.             o = o->ch[1];
     
116.         else if (o->ch[1] == null)
     
117.             o = o->ch[0];
     
118.         else {
     
119.             node* tmp = find_kth(o->ch[1], 1);
     
120.             o->v = tmp->v;
     
121.             erase(o->ch[1], tmp->v);
     
122.             --o->s;
     
123.         }
     
124.     }
     
125.     else {
     
126.         if (o->cmp(x) == 0)
     
127.             erase(o->ch[0], x);
     
128.         else {
     
129.             erase(o->ch[1], x);
     
130.         }
     
131.         --o->s;
     
132.     }
     
133. }
     
134. node* T = null;
     
135. int n;
     
136. int main()
     
137. {
     
138.     cin >> n;
     
139.     null->ch[0] = null;
     
140.     null->ch[1] = null;
     
141.     for (int i = 0, p; i != n; ++i) {
     
142.         int x;
     
143.         cin >> p >> x;
     
144.         if (p == 1)
     
145.             insert(T, x);
     
146.         if (p == 2)
     
147.             erase(T, x);
     
148.         if (p == 3)
     
149.             cout << rank(T, x) << endl;
     
150.         if (p == 4)
     
151.             cout << find_kth(T, x)->v << endl;
     
152.         if (p == 5)
     
153.             cout << precursor(T, x)->v << endl;
     
154.         if (p == 6)
     
155.             cout << successor(T, x)->v << endl;
     
156.     }
     
157.     return 0;
     
158. }
     

复制代码