Codeforces Round #803 (Div. 2)
2 өдрийн дараа |
Codeforces Round #804 (Div. 2)
8 өдрийн дараа |
E. XOR үйлдэл ба дуртай тоо
хугацааны хязгаарлалт 4 секунд
санах ойн хязгаарлалт 256 мегабайт
оролт стандарт оролт
гаралт стандарт гаралт
Боб-д дуртай тоо нь болох $k$ болон $n$ урт бүхий $a_{i}$-үүдийн цуваа байжээ.Одоо тэрээр таныг $m$ ширхэг асуултад хариулахыг хүсэв.Асуулт бүр хос $l_{i}$ болон $r_{i}$-аар өгөгдөх ба таныг $l ≤ i ≤ j ≤ r$ болон $a_{i}, a_{i + 1}, ..., a_{j}$ тоонуудын XOR нь $k$-тай тэнцүү байх гэсэн 2 нөхцөлийг хангах хэчнээн ширхэг бүхэл тоон $i$ болон $j$ хосууд байгааг тоолохыг хүсжээ.
Оролт
Эхний мөрөнд харгалзан цувааны урт,асуултын тоо,Боб-ын дуртай тоог илэрхийлэх бүхэл тоонууд $n$, $m$ болон $k$ ($1 ≤ n, m ≤ 100 000$, $0 ≤ k ≤ 1 000 000$) өгөгдөнө.
2-дахь мөрөнд Боб-ын цуваа болох $n$ ширхэг бүхэл тоо $a_{i}$ ($0 ≤ a_{i} ≤ 1 000 000$) өгөгдөнө.
Үүний дараах $m$ ширхэг мөрний $i$-дахь мөрөнд $i$-дахь асуултын параметрүүд болох $l_{i}$ болон $r_{i}$ ($1 ≤ l_{i} ≤ r_{i} ≤ n$) өгөгдөнө.
Гаралт
Оролтод өгөгдсөн дарааллаар асуулт болгоны хариултыг $m$ ширхэг мөрөнд хэвлэнэ.
Орчуулсан: Баатархүү
Жишээ тэстүүд
Оролт
6 2 3 1 2 1 1 0 3 1 6 3 5
Гаралт
7 0
Оролт
5 3 1 1 1 1 1 1 1 5 2 4 1 3
Гаралт
9 4 4
Тэмдэглэл
Эхний жишээний эхний асуултад тохирох хосууд нь ($1$, $2$), ($1$, $4$), ($1$, $5$), ($2$, $3$), ($3$, $6$), ($5$, $6$), ($6$, $6$) байх ба 2-дахь асуултад тохирох хос байхгүй байна
2-дахь жишээнд сондгой урт бүхий бүх дэд цуваануудын XOR нь $1$-тэй тэнцүү байна.