题目链接:http://www.lightoj.com/volume_showproblem.php?problem=1087 大意就是给一个动态的序列,每次询问序列中第k个元素是啥,询问完以后,就删除这个元素,同时可以在结尾添加元素,如果当前位置没有元素,就输出“none”。 这道题可以说唯一一个捉急的地方就是带删除序列的,所以树上维护的东西就应该是当前区间内还有多少个元素没被删除,这样当询问到某一棵子树的时候,如果左子树的元素个数大于k,那么元素必定在左子树当中,否则就在右子树当中,在左子树当中固然好,就是左子树区间内第k个,在右子树的话就应该是第k减去左子树元素个数个,同时在叶子结点维护元素值,当即搞定。
![](/Images/OutliningIndicators/ContractedBlock.gif) 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
|