神秘石板

问题分析

本题涉及对字符串 $S$ 进行 两类操作，我们需要按照给定的查询顺序对 $S$ 进行变换，并输出最终结果。 由于字符串长度可达 $2N \leq 4 \times 10^5$，查询数量可达 $Q \leq 3 \times 10^5$，暴力模拟会导致 $O(QN)$ 级别的时间复杂度，可能会超时。因此，我们需要 优化操作 以降低复杂度。

操作类型

1. 交换字符 ($T_i = 1$)：
   • 交换索引 $A_i$ 和 $B_i$ 处的字符。
2. 翻转前后两部分 ($T_i = 2$)：
   • 直接交换字符串的前半部分和后半部分。
   • 但是 由于多次翻转会抵消效果，因此不必真的执行字符串翻转，而是维护一个 标记变量 来反映字符串的当前状态。

算法解析

1. 如何高效处理翻转操作？

如果我们每次遇到 $T_i = 2$ 就直接翻转前后部分，会导致 $O(N)$ 的开销。 但观察发现：

• 偶数次翻转：相当于没有变化。
• 奇数次翻转：前后部分交换。

因此，我们可以使用一个布尔变量 f 来跟踪翻转状态：

• 若 f = false，索引保持不变。
• 若 f = true，说明字符串前后已交换，我们需要调整索引： $\text{新索引} = \left\{ \begin{array}{ll} x + N, & \text{如果 } x < N \\ x - N, & \text{如果 } x \geq N \end{array} \right.$

2. 如何高效执行交换操作？

• 由于 f 可能会影响索引，我们要在每次交换前检查 f 并调整索引。

3. 最终输出的处理

• 若 f = true，表示前后部分需要交换，我们可以直接构造新字符串： $S = S_{\text{后半部分}} + S_{\text{前半部分}}$ 这样可以在 $O(N)$ 的时间内完成所有变换。

#include <bits/stdc++.h>
using namespace std;

void solve() {
    int n, q;
    string s;
    cin >> n >> s >> q;

    auto rev = [&](int x) {
        return (x < n) ? x + n : x - n;
    };

    vector<int> t(q), a(q), b(q);
    for (int i = 0; i < q; i++) {
        cin >> t[i] >> a[i] >> b[i];
    }

    bool f = false;
    for (int i = 0; i < q; i++) {
        a[i]--;
        b[i]--;
        if (t[i] == 1) {
            if (f) {
                a[i] = rev(a[i]);
                b[i] = rev(b[i]);
            }
            swap(s[a[i]], s[b[i]]);
        } else {
            f = !f;
        }
    }

    if (f) {
        s = s.substr(n) + s.substr(0, n);
    }

    cout << s << "\n";
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    solve();
    return 0;
}

import java.io.*;
import java.util.*;

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        PrintWriter out = new PrintWriter(System.out);

        int n = Integer.parseInt(br.readLine());
        char[] s = br.readLine().toCharArray();
        int q = Integer.parseInt(br.readLine());

        int[] t = new int[q];
        int[] a = new int[q];
        int[] b = new int[q];

        for (int i = 0; i < q; i++) {
            String[] input = br.readLine().split(" ");
            t[i] = Integer.parseInt(input[0]);
            a[i] = Integer.parseInt(input[1]) - 1;
            b[i] = Integer.parseInt(input[2]) - 1;
        }

        boolean f = false;
        for (int i = 0; i < q; i++) {
            if (t[i] == 1) {
                if (f) {
                    a[i] = (a[i] < n) ? a[i] + n : a[i] - n;
                    b[i] = (b[i] < n) ? b[i] + n : b[i] - n;
                }
                char temp = s[a[i]];
                s[a[i]] = s[b[i]];
                s[b[i]] = temp;
            } else {
                f = !f;
            }
        }

        if (f) {
            char[] temp = new char[2 * n];
            System.arraycopy(s, n, temp, 0, n);
            System.arraycopy(s, 0, temp, n, n);
            s = temp;
        }

        out.println(new String(s));
        out.flush();
    }
}

n = int(input())
s = list(input())
q = int(input())

queries = [tuple(map(int, input().split())) for _ in range(q)]
f = False

for t, a, b in queries:
    a -= 1
    b -= 1
    if t == 1:
        if f:
            a = a + n if a < n else a - n
            b = b + n if b < n else b - n
        s[a], s[b] = s[b], s[a]
    else:
        f = not f

if f:
    s = s[n:] + s[:n]

print("".join(s))