题目大意
维护一种数据结构,资磁三种操作。
1.在p位置插入一个字符串s
2.从p位置开始删除长度为c的字符串
3.输出第v个历史版本中从p位置开始的长度为c的字符串1≤n≤50000,所有字符串总长度小于等于10^6,输出字符串总长度小于等于20000
强制在线,每次输入中的数字都要减去你的所有输出中字母c的个数
思路 #1:可持久化FHQ Treap
(如果你懒得打一大长串的代码,就去看思路#2)
不难看出,这是一道可持久化FHQ Treap的模板题,就是在插入时要O(n)建树,要不会TLE
我们可以直接用一个递归函数build来解决
// s : 用来存储插入的字符串 // struct z[] : 可持久化Treap的本体 QwQ // int newnode(char) : 建立一个新的节点 void build(int l, int r, int &rt) { if(l > r) return; // 边界 int m = (l + r) >> 1; rt = newnode(s[m]); build(l, m - 1, z[rt].ch[0]); build(m + 1, r, z[rt].ch[1]); update(rt); // 更新信息 }
然后我们将根节点直接并到总树中去即可
一定要记住,我们要统计已经输出 'c' 的个数,然后把输入的数字减去这个已经输出的 'c' 的个数(强制在线嘛QwQ)
剩下的细节在代码的注释中写到:
code:
#include <iostream> #include <cstdio> #include <cstdlib> #include <cstring> #include <cmath> #include <algorithm> using namespace std; #define go(i, j, n, k) for(int i = j; i <= n; i += k) #define mn 50010 inline int read(){ int x = 0, f = 1; char ch = getchar(); while(ch > '9' || ch < '0') { if(ch == '-') f = -f; ch = getchar(); } while(ch >= '0' && ch <= '9') { x = x * 10 + ch - '0'; ch = getchar(); } return x * f; } char s[mn * 10]; struct tree { int ch[2], pri, sze; char w; } z[mn * 100]; // 可持久化的数据结构嘛,数组要开大几十倍 int n, m, cnt, rot[mn], xx, yy, zz, d, now; // xx / yy / zz :辅助变量,记录分裂后子树的根节点 // d :记录已经输出的 'c' 的个数 // now :目前版本 inline void update(int rt) { z[rt].sze = 1; if(z[rt].ch[0]) z[rt].sze += z[z[rt].ch[0]].sze; if(z[rt].ch[1]) z[rt].sze += z[z[rt].ch[1]].sze; } // 更新sze(按解决的问题看还可以类似线段树的更新一样可以更新其他信息) inline int newnode(char w = 0) { z[++cnt].w = w; z[cnt].pri = rand(); z[cnt].sze = 1; return cnt; } // 建立新节点的函数 int merge(int x, int y) { if(!x || !y) return x + y; int rt = newnode(); if(z[x].pri < z[y].pri) { z[rt] = z[x]; z[rt].ch[1] = merge(z[rt].ch[1], y); } else { z[rt] = z[y]; z[rt].ch[0] = merge(x, z[rt].ch[0]); } update(rt); return rt; } // 合并操作(模板 void split(int rt, int k, int &x, int &y) { if(!rt) x = y = 0; else { if(k <= z[z[rt].ch[0]].sze) { z[y = newnode()] = z[rt]; split(z[y].ch[0], k, x, z[y].ch[0]); update(y); } else { z[x = newnode()] = z[rt]; split(z[x].ch[1], k - z[z[rt].ch[0]].sze - 1, z[x].ch[1], y); update(x); } } } // 分裂操作(模板 inline int findkth(int rt, int k) { while(1119) { if(k <= z[z[rt].ch[0]].sze) rt = z[rt].ch[0]; else { if(z[rt].ch[0]) k -= z[z[rt].ch[0]].sze; if(!--k) return rt; rt = z[rt].ch[1]; } } } // 查询第 k 值(模板,这里好像没有用 void build(int l, int r, int &rt) { if(l > r) return; int m = (l + r) >> 1; rt = newnode(s[m]); build(l, m - 1, z[rt].ch[0]); build(m + 1, r, z[rt].ch[1]); update(rt); } // 建树操作 inline void ins(int &rt, int last, int pos) { // rt : 更新的版本根节点 // last : 旧版本的根节点 // pos : 要插入的位置 xx = yy = zz = 0; scanf("%s", s + 1); // 字符串的输入让我放在这个地方了哦QwQ int len = strlen(s + 1); split(last, pos, xx, zz); // 注意这个地方要用旧版本的根节点进行 split 操作 build(1, len, yy); // 建树操作 rt = merge(merge(xx, yy), zz); // 重新合并 } // 插入操作 inline void del(int &rt, int last, int pos, int len) { // rt : 更新的版本根节点 // last : 旧版本的根节点 // pos : 要删除的位置 // len : 要删除的长度 xx = yy = zz = 0; // 记得清零,要不影响下次调用 split(last, pos - 1, xx, yy); split(yy, len, yy, zz); // 分成三组,然后把前后两组合并(中间的是被删除的 rt = merge(xx, zz); } // 删除操作 void print(int rt) { // rt : 当前节点 if(!rt) return; print(z[rt].ch[0]); putchar(z[rt].w); if(z[rt].w == 'c') ++d; // 记得统计 'c' 啊 print(z[rt].ch[1]); } // 遍历二叉树输出答案 void print(int rt, int pos, int len) { // rt : 更新的版本根节点 // pos : 要输出的起始位置 // len : 要输出的长度 xx = yy = zz = 0; // 记得清零,要不影响下次调用 split(rt, pos - 1, xx, yy); split(yy, len, yy, zz); // 分离出我们要输出的子树 print(yy); putchar('\n'); } inline void solve() { n = read(); go(i, 1, n, 1) { xx = yy = zz = 0; int s = read(); if(s == 1) { int p = read() - d; // 注意要 - d!(看题目要求啊QAQ ins(rot[now + 1], rot[now], p); ++now; // 毕竟更新过一次,所以版本数 + 1 } else if(s == 2) { int p = read() - d, l = read() - d; // 注意要 - d!!(看题目要求啊QAQ del(rot[now + 1], rot[now], p, l); ++now; // 毕竟更新过一次,所以版本数 + 1 } else { int ver = read() - d, p = read() - d, l = read() - d; // 注意要 - d!!!(看题目要求啊QAQ print(rot[ver], p, l); } } } int main(){ // init(); solve(); return 0; }
思路 #2:STL —— rope
直接使用STL中的rope,这个代码太易懂了,我就不细讲了,免的写平衡树了(就是稍微慢点)
code
#include <iostream> #include <cstdio> #include <ext/rope> #include <algorithm> using namespace std; #define go(i, j, n, k) for(int i = j; i <= n; i += k) inline int read(){ int x = 0, f = 1; char ch = getchar(); while(ch > '9' || ch < '0') { if(ch == '-') f = -f; ch = getchar(); } while(ch >= '0' && ch <= '9') { x = x * 10 + ch - '0'; ch = getchar(); } return x * f; } using namespace __gnu_cxx; crope z[50010], r, str; char a[222]; int n, p, d, c, v, now; inline void solve() { n = read(); go(x, 1, n, 1) { int s = read(); if(s == 1) { p = read() - d; scanf("%s", a); r.insert(p, a); z[++now] = r; } else if(s == 2) { p = read() - d, c = read() - d; r.erase(p - 1, c); z[++now] = r; } else if(s == 3) { v = read() - d, p = read() - d, c = read() - d; str = z[v].substr(p - 1, c); d += count(str.begin(), str.end(), 'c'); cout << str << "\n"; } } } int main(){ // init(); solve(); return 0; }