はまやんはまやんはまやん

hamayanhamayan's blog

Inversion Counting [Educational Codeforces Round 35 D]

http://codeforces.com/contest/911/problem/D

N要素の順列Aがある。
これについてQ個のクエリを処理する。
「範囲[L,R]を反転させて、転置数の偶奇を答えよ」

解法

http://codeforces.com/contest/911/submission/33730265

「転置数の偶奇」という以下にもなワードがある。
ググるこういうのが出て来る。
隣り合う要素をスワップさせると転置数の偶奇が入れ替わるということ。
なので、[L,R]の要素を反転させる操作をswapに置き換えて考えてみると、len=R-L+1とすると、「(len-1)+(len-2)+...+1=(len-1)len/2」回数swapしている。
よってswapの偶奇を見て、転置数の偶奇を変えて答えていく。

最初に転置数を数えて初期状態の偶奇を取り出す。
クエリは実際には反転させずにswap回数のみを見て偶奇を更新して答える。
これでACなのだが、以下のコードは何を間違えたか「len/2」回数swapとして計算している。
pretest数結構あったけど通ってるので、これでも通るかも…?

int N, Q;
//---------------------------------------------------------------------------------------------------
void _main() {
    cin >> N;
    vector<int> A;
    rep(i, 0, N) {
        int x;
        cin >> x;
        x--;
        A.push_back(x);
    }
    ll c = BubbleSortCount(A);

    int ans = c % 2;
    cin >> Q;
    rep(q, 0, Q) {
        int L, R; cin >> L >> R;

        int len = R - L + 1;
        int cnt = len / 2;

        ans = (ans + cnt) % 2;

        if (ans == 1) printf("odd\n");
        else printf("even\n");
    }
}