首页 > 代码库 > OpenJudge cdqz/Data Structure Challenge 2 (Problem 5822) - 可持久化线段树

OpenJudge cdqz/Data Structure Challenge 2 (Problem 5822) - 可持久化线段树

描述

给一个空数列,有M次操作,每次操作是以下三种之一:

(1)在数列后加一个数

(2)求数列中某位置的值

(3)撤销掉最后进行的若干次操作(1和3)

输入

第一行一个正整数M。 接下来M行,每行开头是一个字符,若该字符为‘A‘,则表示一个加数操作,接下来一个整数x,表示在数列后加一个整数x;若该字符为‘Q‘,则表示一个询问操作,接下来一个整数x,表示求x位置的值;若该字符为‘U‘,则表示一个撤销操作,接下来一个整数x,表示撤销掉最后进行的若干次操作。

输出

对每一个询问操作单独输出一行,表示答案。

样例输入

9A 1A 2A 3Q 3U 1A 4Q 3U 2Q 3

样例输出

343

提示

1<=M<=10^5,输入保证合法,且所有整数可用带符号32位整型存储。


  可持久化线段树不解释。

Code

  1 /**  2  * OpenJudge  3  * Problem#5822  4  * Accepted  5  * Time: 846ms  6  * Memory: 144000k  7  */  8 #include <iostream>  9 #include <fstream> 10 #include <sstream> 11 #include <cstdio> 12 #include <cstring> 13 #include <cctype> 14 #include <cstdlib> 15 #include <ctime> 16 #include <algorithm> 17 #include <map> 18 #include <set> 19 #include <stack> 20 #include <vector> 21 #include <queue> 22 using namespace std; 23  24 const int segsize = 300; 25  26 typedef class SegTreeNode { 27     public: 28         int val; 29         SegTreeNode *l, *r; 30          31         SegTreeNode():val(0) {        } 32 }SegTreeNode; 33  34 SegTreeNode pool[6000000]; 35 SegTreeNode *top = pool; 36  37 SegTreeNode* newnode() { 38     return top++; 39 } 40  41 typedef class SegTree { 42     public: 43         SegTreeNode** rts; 44          45         SegTree():rts(NULL) {        } 46         SegTree(int n) { 47             rts = new SegTreeNode*[(n + 1)]; 48             build(rts[0], 1, n); 49         } 50          51         void build(SegTreeNode*& node, int l, int r) { 52             node = newnode(); 53             if(l == r)    return; 54             int mid = (l + r) >> 1; 55             build(node->l, l, mid); 56             build(node->r, mid + 1, r); 57         } 58          59         void update(SegTreeNode*& newv, SegTreeNode*& oldv, int l, int r, int idx, int val) { 60             newv = newnode(); 61             *newv = *oldv; 62             if(l == r) { 63                 newv->val = val; 64                 return; 65             } 66             int mid = (l + r) >> 1; 67             if(idx <= mid)    update(newv->l, oldv->l, l, mid, idx, val); 68             else    update(newv->r, oldv->r, mid + 1, r, idx, val); 69         } 70          71         int query(SegTreeNode*& node, int l, int r, int idx) { 72             if(l == r)    return node->val; 73             int mid = (l + r) >> 1; 74             if(idx <= mid)    return query(node->l, l, mid, idx); 75             return query(node->r, mid + 1, r, idx); 76         } 77          78         SegTreeNode*& operator [] (int pos) { 79             return rts[pos]; 80         } 81 }SegTree; 82  83 int n; 84 int length[100005]; 85 SegTree st; 86 char s[10]; 87  88 inline void solve() { 89     scanf("%d", &n); 90     st = SegTree(n); 91     length[0] = 0; 92     for(int opt = 1, v = 1, x; opt <= n; opt++) { 93         scanf("%s%d", s, &x); 94         switch(s[0]) { 95             case A: 96                 length[v] = length[v - 1] + 1; 97                 st.update(st[v], st[v - 1], 1, n, length[v], x), v++; 98                 break; 99             case Q:100                 printf("%d\n", st.query(st[v - 1], 1, n, x));101                 break;102             case U:103                 length[v] = length[v - x - 1];104                 st[v] = st[v - x - 1], v++;105                 break;106         }107     }108 }109 110 int main() {111     solve();112     return 0;113 }

 

OpenJudge cdqz/Data Structure Challenge 2 (Problem 5822) - 可持久化线段树