~/algor $ cat masalalar/bit-oraliq-xor
Bit-03
Oraliq XOR so'rovlari
Muallif:
Iqbolshoh Ilhomjonov
O'rtacha
1000 ms
128 MB
52%
$n$ ta butun son $a_{1}, a_{2}, \ldots, a_{n}$ va $q$ ta so'rov berilgan. Har bir so'rovda $l$ va $r$ beriladi; $a_{l} \oplus a_{l+1} \oplus \ldots \oplus a_{r}$ ni toping. Bu yerda $\oplus$ — bitlar bo'yicha XOR (istisno qiluvchi yoki) amali: ikkilik yozuvda bitlar har xil bo'lgan o'rinda $1$, bir xil bo'lgan o'rinda $0$.
Kiruvchi ma'lumotlar
Birinchi qatorda ikkita natural son: $n$ va $q$. Ikkinchi qatorda bo'sh joy bilan ajratilgan $n$ ta butun son $a_{i}$. Keyingi $q$ ta qatorning har birida ikkita natural son: $l$ va $r$.
Chiquvchi ma'lumotlar
Har bir so'rov uchun alohida qatorda bitta butun son.
Izoh
$1 \le n, q \le 10^{5}$
$0 \le a_{i} \le 10^{9}$
$1 \le l \le r \le n$
Misollar
Kirish #1
5 3 1 2 3 4 5 1 3 2 5 4 4
Chiqish #1
0 0 4
Kirish #2
3 2 7 7 7 1 2 1 3
Chiqish #2
0 7