読者です 読者をやめる 読者になる 読者になる

pekempeyのブログ

競技プログラミングに関する話題を書いていきます。

Codeforces Round #365 (Div. 2) D. Mishka and Interesting sum

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

解法

even ではなく odd であれば普通に区間の和を取れば求まる。

(even の和)=(distinct な和)xor (odd の和)なので、distinct な和を求めることができれば解くことができる。

distinct な和を求めるには、クエリを先読みして次のような処理をする。

pos[10^6] = {-1, -1, -1, ... };
for (int i = 0; i < n; i++) {
    if (pos[a[i]] != -1) {
        bit.update(pos[a[i]], a[i]);
    }
    pos[a[i]] = i;
    bit.update(pos[a[i]], a[i]);

    for (int qid : 右端が i であるクエリの集合) {
        ans[qid] = bit.query(r[qid]) ^ bit.query(l[qid] - 1);
    }
}

i 以前に現れた v のうち、最も右にある v だけを BIT に入れておく、という処理をしている。

値をできるだけ右に寄せておけばうまくヒットするので、これでうまくいく。

割とよく使うテクで、実は 2 回解説で書いたことがある。