IPFL [AtCoder Beginner Contest 199（Sponsored by Panasonic） C]

https://atcoder.jp/contests/abc199/tasks/abc199_c

解説

https://atcoder.jp/contests/abc199/submissions/22039696

この問題のミソはT=2の処理である。
T=1の場合はswapがO(1)で行えるので問題ない。
T=2の場合は、普通にやるとO(N)かかるのでこれを何とかしたい。

どうする？

T=2だけを考えたときにどのようにやれば高速化できるだろうか。
これは文字列を前後半に分割して保持しておく方法がある。
前半をpre, 後半をpostとしておくと、preとpostのswapのみでT=2を完結させることができる。
O(N)のコピーをしているのでは？と考えられるかもしれない。

== ここからちょっと自信なし ==
C++においてstringは参照型であるので、参照先についてswapされるだけであり、O(1)で行える
== ここまでちょっと自信なし ==

T=1は？

これでT=2が達成できたのはいいが、T=1をうまく扱う方法を考える。
だが実装を考えると、これはちょっとの場合分けを行うことで達成できる。

• B＜Nならどちらも前半のswapなので、swap(pre[A], pre[B])
• N≦Aならどちらも後半のswapなので、swap(post[A - N], post[B - N])
• そうでないなら、前半と後半のswapなので、swap(pre[A], post[B - N])

int N; string S; int Q;
//---------------------------------------------------------------------------------------------------
void _main() {
    cin >> N >> S >> Q;

    string pre = S.substr(0, N);
    string post = S.substr(N);

    rep(_, 0, Q) {
        int T, A, B; cin >> T >> A >> B;
        if (T == 1) {
            A--; B--;

            if (B < N) swap(pre[A], pre[B]);
            else if (N <= A) swap(post[A - N], post[B - N]);
            else swap(pre[A], post[B - N]);
        }
        else {
            swap(pre, post);
        }
    }

    cout << pre << post << endl;
}