题解：AT_abc419_d [ABC419D] Substr Swap

· · 题解

题意简述

有两个长度为 N 的字符串 S 和 T，以及 M 个区间 [L_i, R_i]。
每次操作交换 S 和 T 在区间 [L_i, R_i] 上的子串（1-based 索引）。
求 M 次操作后 S 的内容。

数据范围：

思路分析

直接模拟的复杂度

如果每次真的去交换区间内的字符，最坏情况复杂度 O(NM)，会超时。

高效做法

我们可以利用 rope 数据结构（一个非标准的STL工具）来高效完成区间交换。
rope 支持：

这样每次操作只需提取两段子串并交换，复杂度 O(\log N)，总复杂度 O(M \log N)，可以满足题目要求。

算法步骤

  1. 读入 N, M, S, T 和操作区间。
  2. 将 S 和 T 存入两个 rope<char>。
  3. 对每个操作 [L, R]（转为 0-based）：
    • 从 S 中提取 [L, R] 子串 subS
    • 从 T 中提取 [L, R] 子串 subT
    • 将 S 的 [L, R] 替换为 subT
    • 将 T 的 [L, R] 替换为 subS
  4. 将最终的 S 转换为字符串输出。

代码实现

#include <iostream>
#include <string>
#include <ext/rope>
using namespace std;
using namespace __gnu_cxx;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int N, M;
    cin >> N >> M;
    string s, t;
    cin >> s >> t;

    rope<char> rs(s.c_str()), rt(t.c_str());

    for (int i = 0; i < M; i++) {
        int L, R;
        cin >> L >> R;
        L--; R--;
        auto subS = rs.substr(L, R - L + 1);
        auto subT = rt.substr(L, R - L + 1);
        rs.replace(L, R - L + 1, subT);
        rt.replace(L, R - L + 1, subS);
    }

    string ans;
    for (int i = 0; i < N; i++)
        ans += rs[i];
    cout << ans << '\n';

    return 0;
}