| № | Пользователь | Рейтинг |
|---|---|---|
| 1 | tourist | 4009 |
| 2 | jiangly | 3823 |
| 3 | Benq | 3738 |
| 4 | Radewoosh | 3633 |
| 5 | jqdai0815 | 3620 |
| 6 | orzdevinwang | 3529 |
| 7 | ecnerwala | 3446 |
| 8 | Um_nik | 3396 |
| 9 | ksun48 | 3390 |
| 10 | gamegame | 3386 |
| Страны | Города | Организации | Всё → |
| № | Пользователь | Вклад |
|---|---|---|
| 1 | cry | 167 |
| 2 | Um_nik | 163 |
| 3 | maomao90 | 162 |
| 3 | atcoder_official | 162 |
| 5 | adamant | 159 |
| 6 | -is-this-fft- | 158 |
| 7 | awoo | 157 |
| 8 | TheScrasse | 154 |
| 9 | Dominater069 | 153 |
| 9 | nor | 153 |
Given an array of N integers and Q queries. For each query you are given two integers L and R(where L<=R<=N) you have to output the sum of xor over all the triplet i,j and k where L<=i<j<k<=R Constraints 1 <= N <=10^5 1 <= Q <=10^5 1 <= A[i] <=10^12
Can anybody help me out on how to solve this question?
The main observation is that the XOR is independent over all bits. Then lets have a partial sums array over all bits. This way in O(1) we can find the number of k-th bits set in a range.
Well then for each query in
we can find the answer by simply considering each bit (when you have the number of 1's and 0's in the range at the given bit, you can calculate the value for that bit in O(1)).
Can you please explain a little bit more.
Well imagine the rangle [L; R] has three numbers {3, 2, 16}. Then their 0-th bit xor is 1, 1-st bit xor is 0, 2-nd bit xor is 0, 3-rd bit xor is also 0 and 4-th bit xor is 1. Well then we simply can add 20, 21 and 24 to the answer. This is what I meant by "the xor is independent over all bits".
The algorithm will look like that for each query:
Consider i-th bit.
Count the answer if all numbers with 1 on this bits are ones and all over are zeroes. Let the answer be S.
Add S * 2i to the answer.
Let's assume we are calculating the answer for bit B in the range [L, R].
Three numbers (i, j, k) will ⊕ (bitwise XOR) to 1 if (i = 1, j = 0, k = 0) or (i = 1, j = 1, k = 1) (obviously including permutations of (i, j, k)).
Let x be the count of 1s in the range [L, R], and y be the count of 0s in the range [L, R]. We have
ways to pick three 1s out of this range, and 
ways to pick a 1 and two 0s. Therefore, the answer is 
(we divide by 3! because we are only looking for unordered triplets).
First find prefix sum for each bit. This way we can find number of elements in range l to r which have ith bit set( i from 0 to ceil(log10^12)). Now say in range l to r there are k elements which have ith bit set. Then if we take 3 elements from them then they will contribute value of ith bit to xor sum. So add to xor sum kC3*ith value. And if we take 1 such element and 2 elements which don't have that bit set then also their triplet will contribute value to sum. k*((r-l+1)-kC2)*value
Gem
https://www.hackerearth.com/practice/data-structures/advanced-data-structures/segment-trees/practice-problems/algorithm/xor-sum-1-af648068/ editorial would help :p
nice question