CodeChef Aarambh 2020 - Odd Topic

• 問題
• AC

出現する整数が高々4000種類しかないので、4000個のcompact bit vectorを持ってすべてのクエリに対して累積和で計算する、みたいなムーブを最初にやってしまった。（部分点は取れる。） 結局、バケット法+bitset高速化をした。

簡単のために、数列$a$と$b$の長さは両方$N$とする。$a$と$b$を長さ$B$毎に区切って$k := N/B$個の区間に分解し、さらにそれぞれの区間に対して長さ$4000$のビット配列を保持する。このビット配列を$\alpha_1, ..., \alpha_k, \beta_1, ..., \beta_k$とする。それぞれの区間について、出現する整数の奇遇を数えて

$$\alpha_i[x] := \begin{cases} 1 \qquad (整数xが区間内に奇数個ある場合) \\ 0 \qquad (整数xが区間内に偶数個ある場合) \end{cases}$$

としておく。（$\beta_i$も同様）
各クエリの指定区間に含まれるバケット$\alpha_i, \beta_i$のXORを取って、端の部分は愚直に数えれば、立っているビットの数が答えになる。出現する値の最大値を$A$とすると、計算量は${O}(Q((N/B)\cdot(A/\log A) + B))$。$B= \Theta(\sqrt{NA/\log A})$なら${O}(Q\sqrt{NA/\log A)}$。（$/ \log A$の部分はいわゆるbitset高速化）

コンテスト中は深く考えずに$B=200$としたのだけど、計算量を見ると$\sqrt N$よりは大きいほうがよさそうだったので$B=1000$としてみたら遅くなった。なにか勘違いしてるかも。

---

tmwilliamlinさんの提出を見たら、単純なbitsetの累積和で処理していた。それはそうだった…… ${\mathcal O}((N+Q)A/ \log A)$。

Egorさんは出現する整数のほうを下位5ビットごとに分割して、bitsetなしで通している。