CF_Div2_807_C
原题链接
题目描述
t 次测试：给定长度为 n 的字符串 s，进行 c 次操作，每次操作：将第 l 到第 r 的子字符串复制到 s 尾部，再进行 q 次询问，每次询问当前字符串第 k 个字符是什么
数据范围
- 1 ≤ t ≤ 1000
- 1 ≤ n ≤ 2⋅10^5
- 1 ≤ c ≤ 40，1 ≤ q ≤ 10^4
- 1 ≤ l ≤ r ≤ 10^18
- 1 ≤ k ≤ 10^18
思路剖析
问题分析：
- 暴力模拟会 TLE 或 MLE，需要考虑偏移量
解题思路：
- 记录第 i 次操作的偏移量
diff[i]，和新增长度的左端点和右端点 - 满足：
left[i] = right[i-1]（0-based），right[i] = left[i] + (r - l + 1)，diff[i] = left[i] - l - 对于 q 次查询的 k，一定能通过偏移量映射到初始字符串的某个位置
- 对 k 从 c 开始反向处理，具体实现请看代码
代码实现
#define ll long longvoid solve() {int n, c, q;cin >> n >> c >> q;string s;cin >> s;vector<ll> left(c + 1), right(c + 1), diff(c + 1);// 初始化left[0] = 0, right[0] = n - 1;for (int i = 1; i <= c; ++i) {ll l, r;cin >> l >> r;l--, r--;left[i] = right[i - 1] + 1;right[i] = left[i] + r - l;diff[i] = left[i] - l;}for (int i = 1; i <= q; ++i) {ll k;cin >> k;k--;for (int j = c; j >= 1; --j) {if (k >= left[j] && k <= right[j]) {k -= diff[j];}}cout << s[k] << '\n';}
}