題目鏈接：http://www.lightoj.com/volume_showproblem.php?problem=1087 大意就是給一個(gè)動(dòng)態(tài)的序列，每次詢問序列中第k個(gè)元素是啥，詢問完以后，就刪除這個(gè)元素，同時(shí)可以在結(jié)尾添加元素，如果當(dāng)前位置沒有元素，就輸出“none”。 這道題可以說唯一一個(gè)捉急的地方就是帶刪除序列的，所以樹上維護(hù)的東西就應(yīng)該是當(dāng)前區(qū)間內(nèi)還有多少個(gè)元素沒被刪除，這樣當(dāng)詢問到某一棵子樹的時(shí)候，如果左子樹的元素個(gè)數(shù)大于k，那么元素必定在左子樹當(dāng)中，否則就在右子樹當(dāng)中，在左子樹當(dāng)中固然好，就是左子樹區(qū)間內(nèi)第k個(gè)，在右子樹的話就應(yīng)該是第k減去左子樹元素個(gè)數(shù)個(gè)，同時(shí)在葉子結(jié)點(diǎn)維護(hù)元素值，當(dāng)即搞定。
  view code
1 #include <iostream>
2 #include <cstdio>
3 #include <cstdlib>
4 #include <cstring>
5 #include <cmath>
6 #include <algorithm>
7 using namespace std;
8 #define lson l, m, rt << 1
9 #define rson m + 1, r, rt << 1 | 1
10 const int maxn = 200100;
11 int num[maxn << 2], id[maxn << 2], ans;
12 void PushUp(int rt){
13 num[rt] = num[rt << 1] + num[rt << 1 | 1];
14 }
15 void build(int l, int r, int rt){
16 num[rt] = 0; id[rt] = -1;
17 if (l == r) return;
18 int m = (l + r) >> 1;
19 build(lson);
20 build(rson);
21 }
22 void update(int x, int c, int l, int r, int rt){
23 if (l == r){
24 num[rt] = 1;
25 id[rt] = c;
26 return;
27 }
28 int m = (l + r) >> 1;
29 if (x <= m) update(x, c, lson);
30 else update(x, c, rson);
31 PushUp(rt);
32 }
33 void query(int k, int l, int r, int rt){
34 num[rt] -= 1;
35 if (l == r){
36 ans = id[rt]; id[rt] = -1;
37 return;
38 }
39 int m = (l + r) >> 1;
40 if (num[rt << 1] >= k) query(k, lson);
41 else{
42 k -= num[rt << 1];
43 query(k, rson);
44 }
45 }
46 int main(){
47 int t;
48 scanf("%d", &t);
49 for (int p = 1; p <= t; p++){
50 int n, m;
51 scanf("%d%d", &n, &m);
52 int nn = n + m;
53 build(1, nn, 1);
54 printf("Case %d:\n", p);
55 for (int i = 1; i <= n; i++){
56 int x; scanf("%d", &x);
57 update(i, x, 1, nn, 1);
58 }
59 while (m--){
60 char s[2]; int x;
61 scanf("%s%d", s, &x);
62 if (s[0] == 'a'){
63 n += 1;
64 update(n, x, 1, nn, 1);
65 }
66 else{
67 query(x, 1, nn, 1);
68 if (ans == -1) printf("none\n");
69 else printf("%d\n", ans);
70 }
71 }
72 }
73 return 0;
74 }
75
|