15年做那个网站致富,知网回应被罚: 诚恳接受,专业见长,wordpress安装后查看站点失败Version Controlled IDE
传送门
题面翻译
维护一种数据结构#xff0c;资磁三种操作。
1.在p位置插入一个字符串s
2.从p位置开始删除长度为c的字符串
3.输出第v个历史版本中从p位置开始的长度为c的字符串 1 ≤ n ≤ 50000 1 \leq n \leq 50000 1≤n≤50000#xff0c;所…Version Controlled IDE
传送门
题面翻译
维护一种数据结构资磁三种操作。
1.在p位置插入一个字符串s
2.从p位置开始删除长度为c的字符串
3.输出第v个历史版本中从p位置开始的长度为c的字符串 1 ≤ n ≤ 50000 1 \leq n \leq 50000 1≤n≤50000所有字符串总长度小于等于 1 0 6 10^6 106输出字符串总长度小于等于 20000 20000 20000
强制在线每次输入中的数字都要减去你的所有输出中字母c的个数
Translated by litble
题目描述
PDF 输入格式 输出格式 样例 #1
样例输入 #1
6
1 0 abcdefgh
2 4 3
3 1 2 5
3 3 3 4
1 4 xy
3 5 4 6样例输出 #1
bcdef
bcg
bxyc注明 以上来自 U V a 翻译来源洛谷。 以上来自 UVa翻译来源洛谷。 以上来自UVa翻译来源洛谷。
不如在洛谷看 UVa 的题在 vjudge 上交。
易懂版题面来自大佬 shiyihang。
解题思路
前置知识 crope [ 1 ] ^{[1]} [1]。 正文
需要简化一下题意 初始有一个空字符串下标从 1 1 1 开始进行 N N N 次操作 在第 p p p 个字符后插入一个字符串 s s s 。删除从第 p p p 个字符包括第 p p p 个开始的长度为 c c c 的字符串。输出第 v v v 个历史版本中从 p p p 个字符包括第 p p p 个开始的长度为 c c c 的字符串。 每次 1 , 2 1,2 1,2 操作形成一个新的版本初始版本为 0 0 0编号依次递增。强制在线每一个输入中的数字减去目前所有输出中字母 c 的个数才是题目描述中的值。 对于所有的数据满足以下条件 2 ≤ N ≤ 5 × 1 0 4 2 \le N \le 5 \times 10^4 2≤N≤5×104 0 ≤ p ≤ 1 0 6 0 \le p \le 10^6 0≤p≤106 0 ∣ s ∣ , c ≤ 1 0 6 0 \lt |s|, c \le 10^6 0∣s∣,c≤106。 保证输入数据中的 v v v 在 1 1 1 到 先前输入中 操作一或二 的总数 之间。 对于 2 , 3 2,3 2,3 操作保证子串不超过原串末尾 p c ≤ ∣ s ∣ p c \le |s| pc≤∣s∣。 很好的 crope 模版题直接用 crope 按照题意模拟即可。
AC Code
#includebits/stdc.h
#includeext/rope
using namespace std;
using namespace __gnu_cxx;
int n;
char s[1000005];
crope Rope, His[50005];
int Length;
signed main() {ios::sync_with_stdio(false), cin.tie(0), cout.tie(0), cin n;int opt, v, p, c, sum 0;crope temp;while (n--) {cin opt;if (opt 1) cin p s, p - sum, Rope.insert(p, s), His[Length] Rope;else if (opt 2) cin p c, p - sum, c - sum, Rope.erase(p - 1, c), His[Length] Rope;else cin v p c, v - sum, p - sum, c - sum, temp His[v].substr(p - 1, c), sum count(temp.begin(), temp.end(), c), cout temp endl;}return 0;
}资料来源 [1]博客园 mekdull 实用 STL —— rope 学习笔记。
