問題一覧 > 通常問題

No.3205 Range Pairwise Xor Query

レベル : / 実行時間制限 : 1ケース 2.000秒 / メモリ制限 : 512 MB / 標準ジャッジ問題
タグ : / 解いたユーザー数 113
作問者 : amesyu / テスター : noshinn lmorinn 遭難者
ProblemId : 12365 / 出題時の順位表 / 自分の提出
問題文最終更新日: 2025-07-20 15:57:35

問題文

長さ $N$ の整数列 $A = (A_1, A_2, \cdots, A_N)$ が与えられます。
以下の形式で与えられる $Q$ 個のクエリに答えてください。
整数 $L$ , $R$ が与えられる。 $\displaystyle \sum_{i=L}^{R-1} \sum_{j=i+1}^{R} A_i \oplus A_j$ を求めよ。
ただし $A \oplus B$ は $A$ と $B$ のビットごとの排他的論理和を表します。

ビットごとの排他的論理和 とは 非負整数 $A$ , $B$ のビットごとの排他的論理和 $A \oplus B$ は、以下のように定義されます。
  • $A \oplus B$ を二進表記した際の $2^k \ (k \geq 0)$ の位の数は $A$ , $B$ を二進表記した際の $2^k$ の位の数のうち一方のみが $1$ であれば $1$ 、そうでなければ $0$ である
    • 例えば、 $3 \oplus 5 = 6$ となります。(二進表記すると: $011 \oplus 101 = 110$ )

    制約

    • $1 \leq N \leq 2 \times 10^5$
    • $1 \leq Q \leq 2 \times 10^5$
    • $0 \leq A_i \lt 2^{26}$
    • $1 \leq L \lt R \leq N$
    • 入力はすべて整数

    入力

    $N$ $Q$
$A_1$ $A_2$ $\cdots$ $A_N$
$\text{query}_1$
$\text{query}_2$
$\vdots$
$\text{query}_Q$
    各クエリは以下の形式で与えられる。 
    $L$ $R$

    出力

    $Q$ 行出力せよ。 $i$ 行目には $i$ 番目のクエリの答えを出力せよ。

    サンプル

    サンプル1
    入力
    5 5
3 1 4 1 5
3 5
1 5
1 2
2 4
4 5
    出力
    10
36
2
10
4

    $1$ つ目のクエリについて、 $4 \oplus 1 = 5$ , $4 \oplus 5 = 1$ , $1 \oplus 5 = 4$ , なので答えは $10$ です。

    提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。