問題一覧 > 通常問題

No.3205 Range Pairwise Xor Query

レベル : / AI推定難易度 : 925 / 実行時間制限 : 1ケース 2.000秒 / メモリ制限 : 512 MB / 標準ジャッジ問題
タグ : （解説公開後に AC するまで非表示） / 解いたユーザー数 120
作問者 : amesyu / テスター : noshinn lmorinn 👑 qand
お気に入りにしたユーザー ProblemId : 12365 / 自分の提出
問題文最終更新日: 2025-07-20 15:57:35
This statement was translated by AI (claude-opus-5-5, effort medium) and may contain errors or differ in nuance from the original. The original statement takes precedence. Back to the original
yukicoder contest 474 (順位表) の他の問題:

Problem Statement

You are given an integer sequence $A = (A_1, A_2, \cdots, A_N)$ of length $N$.
Answer $Q$ queries given in the following format.
Integers $L$ , $R$ are given. Find $\displaystyle \sum_{i=L}^{R-1} \sum_{j=i+1}^{R} A_i \oplus A_j$.
Here, $A \oplus B$ denotes the bitwise exclusive OR of $A$ and $B$.

What is bitwise exclusive OR? The bitwise exclusive OR $A \oplus B$ of non-negative integers $A$ , $B$ is defined as follows.
  • The digit in the $2^k \ (k \geq 0)$ place of $A \oplus B$ in binary is $1$ if exactly one of the digits in the $2^k$ place of $A$ , $B$ in binary is $1$, and $0$ otherwise.
    • For example, $3 \oplus 5 = 6$. (In binary: $011 \oplus 101 = 110$ )

    Constraints

    • $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$
    • All inputs are integers.

    Input

    $N$ $Q$
$A_1$ $A_2$ $\cdots$ $A_N$
$\text{query}_1$
$\text{query}_2$
$\vdots$
$\text{query}_Q$
    Each query is given in the following format. 
    $L$ $R$

    Output

    Output $Q$ lines. The $i$-th line should contain the answer to the $i$-th query.

    Sample

    Sample 1
    Input
    5 5
3 1 4 1 5
3 5
1 5
1 2
2 4
4 5
    Output
    10
36
2
10
4

    For the $1$ st query, $4 \oplus 1 = 5$ , $4 \oplus 5 = 1$ , $1 \oplus 5 = 4$ , so the answer is $10$.

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