Reverse Array [第八回 アルゴリズム実技検定 J]

https://atcoder.jp/contests/past202109-open/tasks/past202109_j

前提知識

• 遅延評価セグメントツリー

解説

https://atcoder.jp/contests/past202109-open/submissions/26703507

遅延評価セグメントツリー以外にも沢山実装方法があるように見える。
今回、自分がやったやり方を説明していこう。

重要性質は何か

今回面倒なのは反転操作であると思うが、何回操作を行っても、回文関係にある部分が
反転するか反転してないかの状態にしかならない。
よって、保持すべき情報、判断すべき情報は、反転しているかどうかだけである。
これをうまくやっていくにはどうすればいいだろうか。

反転操作は区間について行うことになるが、その区間において反転するしないが逆転するような感じになる。
0を反転しない、1を反転するということにすると区間について1でXORをしているような操作になる。
これはそのまま遅延評価セグメントツリーに乗せることもできるが、
自分は区間について+1するような遅延評価セグメントツリーを書いた。
+1するようにしておけば2の倍数であれば反転しないし、2の倍数でないなら反転することに相当する。

まとめ

ちょっとわかりにくかったかもしれないので、実際の実装に落とし込んだ場合としてまとめておく。
区間addを実装した遅延評価セグメントツリーを用意しておく。

t=1のときは、左からk番目の遅延評価セグメントツリーの要素を見て、2の倍数であれば、kを答え、
2の倍数でないなら、2N - k + 1を答える。

t=2のときは、遅延評価セグメントツリーにおいて[N - k + 1, N + k]の要素を+1する

自分の実装では0-indexedになっているので添え字がけっこうややこしいが、以上を実装すればAC.

int N, Q;
LazySegTree<int,1<<19> lst;
//---------------------------------------------------------------------------------------------------
void _main() {
    cin >> N >> Q;
    
    rep(i, 0, Q) {
        int t, k; cin >> t >> k;

        if (t == 1) {
            k--;
            if (lst.get(k, k + 1) % 2 == 0) printf("%d\n", k + 1);
            else printf("%d\n", 2 * N - k);
        }
        else {
            lst.update(N - k, N + k, 1);
        }
    }
}