当每次遇到操作二时，不进行操作，而是对两个数进行偏移。 过程： 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(Q*N)$是不允许的，那如何优化，操作一一定不能在优化了，那就看操作二，可以发现，操作二只有在奇数时才会对答案有变化，所以可以记录一下奇数还是偶数，如果是奇数的话，将操作一偏移一下，可以发现如果是奇数的话，操作一在执行的时候在前半部分的位置会到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;
}

神秘石板

问题分析

本题涉及对字符串 $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))