問題一覧 > 通常問題

No.1091 Range Xor Query

レベル : / 実行時間制限 : 1ケース 2.000秒 / メモリ制限 : 512 MB / 通常問題
タグ : / 解いたユーザー数 51
作問者 : nullnull / テスター : butsurizukibutsurizuki
1 ProblemId : 4570 / 出題時の順位表
問題文最終更新日: 2020-06-24 01:32:16

問題文

長さ $N$ の数列 $a_1, a_2, \dots, a_N$ があります。
$\displaystyle \bigoplus_{i = l}^{r} a_i = a_l\ xor\ a_{l+1}\ xor\ \dots\ xor\ a_r$ とします。
$j(1 \le j \le Q)$ 番目のクエリでは、$\displaystyle \bigoplus_{i = l_j}^{r_j} a_i$ を求めてください。
$a\ xor\ b$ とは、$a, b$ を二進数であらわしたとき、各桁について $a, b$ どちらもビットが立っているまたは立っていないときその桁が $0$、それ以外の時に $1$ となるような演算です。詳しくは「排他的論理和」で検索してください。

入力

$N\ Q$
$a_1\ a_2\ \dots\ a_N$
$l_1\ r_1$
$l_2\ r_2$
$\dots$
$l_Q\ r_Q$

$1 \le N, Q \le 2 \times 10^5$
$1 \le a_i \le 10^5$
$1 \le l_j \le r_j \le N$

出力

改行区切りで $Q$ 行にわたって答えを出力せよ。最後に改行せよ。

サンプル

サンプル1
入力
10 10
1 1 4 5 1 4 1 9 1 9
1 10
10 10
1 1
4 5
1 4
8 10
1 9
1 9
9 9
5 10
出力
4
9
1
4
1
1
13
13
1
5

出典

YSF Beginner Contest: D - Range Xor Query
writer: null
tester: butsuri_0523
HackerRank の規約に基づいて移植されました。一部サイトの都合などで改変したところがあります。

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