神秘石板 问题分析 本题涉及对字符串 $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)$ 的时间内完成所有变换。 ```cpp #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; } ``` ```java 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(); } } ``` ```python 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)) ```

当每次遇到操作二时，不进行操作，而是对两个数进行偏移。 过程： 1.当第一次遇到操作二时，对后续每次的操作一的交换索引进行偏移。如果左索引在前本段，对应于如果进行操作二后位置在后半段，相当于对左索引+n,即还是交换相对应的那个字符；如果在字符右半段，即-n。右索引同理。 2.当遇到第二次操作二时，则原本暴力方法进行第一次的操作二后再执行现在的一次操作二，则变成了现在对索引偏移（不进行真实的操作二）的结果。相当于变回来了，对于后续的操作一，则不需要再进行偏移，因为跟每次都执行操作一的结果统一了。 3.以此类推，遇到奇数次的操作二，后续的操作一跟暴力解法结果，每次都差一个操作二的步骤变换。遇到偶数次的操作二，则后续的操作一结果都一样。 ``` #include <bits/stdc++.h> using namespace std; const int mod = 1e9 + 7; int main() { int len,q; cin>>len; string s; cin>>s; cin>>q; bool flag = false; while(q--) { int a,m,n; cin>>a>>m>>n; m--,n--; if(a == 1) { if(flag) { m = (m < len ? m+len : m-len); n = (n < len ? n+len : n-len); } swap(s[m],s[n]); } if(a == 2) flag = !flag; } if(flag) { reverse(s.begin(),s.end()); reverse(s.begin(),s.begin()+len); reverse(s.begin()+len,s.end()); } cout<<s; } ```

首先，这道题直接模拟的话会超时，因为直接模拟的话时间复杂度时是$O(QN)$是不允许的，那如何优化，操作一一定不能在优化了，那就看操作二，可以发现，操作二只有在奇数时才会对答案有变化，所以可以记录一下奇数还是偶数，如果是奇数的话，将操作一偏移一下，可以发现如果是奇数的话，操作一在执行的时候在前半部分的位置会到x+n，后半部分会到x-n，在执行操作一如果是偶数的话可以先进行偏移，在进行交换即可 ``` #include<cstdio> #include<iostream> #include<vector> #include<map> #include<cstring> #include<array> #include<queue> #include<algorithm> #include<set> #include<cmath> using namespace std; using i64=long long; //using i128=__int128; const i64 INF=1e18; const int mod=998244353; //const int N=1e9+7; void solve(){ int n; cin>>n; string s; cin>>s; int q; cin>>q; bool flag=false; while(q--){ int t,a,b; cin>>t>>a>>b; a--,b--; if(t==1){ if(flag){ a=(a<n ? a+n : a-n); b=(b<n ? b+n : b-n); } swap(s[a],s[b]); } else{ flag=!flag; } } if(flag){ s=s.substr(n)+s.substr(0,n); } cout<<s<<'\n'; } int main(){ int _=1; //cin>>_; while(_--)solve(); return 0; } ```