出現する整数が高々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なしで通している。
