UVA12538 Version Controlled IDE 题解 crope

Version Controlled IDE

传送门

题面翻译

维护一种数据结构，资磁三种操作。

1.在p位置插入一个字符串s

2.从p位置开始删除长度为c的字符串

3.输出第v个历史版本中从p位置开始的长度为c的字符串

$1\le n\le 50000$，所有字符串总长度小于等于$10^6$，输出字符串总长度小于等于$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

注明

$以上来自UVa，翻译来源：洛谷。$

不如在洛谷看 UVa 的题，在 vjudge 上交。

易懂版题面来自大佬 @shiyihang。

解题思路

前置知识

• crope ${}^{[1]}$。

正文

需要简化一下题意：

初始有一个空字符串，下标从 $1$ 开始，进行 $N$ 次操作：

1. 在第 $p$ 个字符后插入一个字符串 $s$ 。
2. 删除从第 $p$ 个字符（包括第 $p$ 个）开始的长度为 $c$ 的字符串。
3. 输出第 $v$ 个历史版本中从 $p$ 个字符（包括第 $p$ 个）开始的长度为 $c$ 的字符串。

每次 $1,2$ 操作形成一个新的版本，初始版本为 $0$，编号依次递增。强制在线，每一个输入中的数字减去目前所有输出中字母 c 的个数才是题目描述中的值。

对于所有的数据，满足以下条件：

• $2\le N\le 5\times 10^4$ ；
• $0\le p\le 10^6$；
• $0<|s|,c\le 10^6$。

保证输入数据中的 $v$ 在 $1$ 到 先前输入中 操作一或二 的总数 之间。
对于 $2,3$ 操作，保证子串不超过原串末尾 $p+c\le |s|$。

很好的 crope 模版题，直接用 crope 按照题意模拟即可。

AC Code

#include<bits/stdc++.h>
#include<ext/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 学习笔记。