首页 > 代码库 > 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) - 可持久化线段树
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。