https://codeforces.com/gym/100739/problem/A Can anyone please help me out with this problem. It has no editoial.
https://codeforces.com/gym/100739/problem/A Can anyone please help me out with this problem. It has no editoial.
| № | Пользователь | Рейтинг |
|---|---|---|
| 1 | tourist | 3690 |
| 2 | jiangly | 3647 |
| 3 | Benq | 3581 |
| 4 | orzdevinwang | 3570 |
| 5 | Geothermal | 3569 |
| 5 | cnnfls_csy | 3569 |
| 7 | Radewoosh | 3509 |
| 8 | ecnerwala | 3486 |
| 9 | jqdai0815 | 3474 |
| 10 | gyh20 | 3447 |
| Страны | Города | Организации | Всё → |
| № | Пользователь | Вклад |
|---|---|---|
| 1 | maomao90 | 173 |
| 2 | awoo | 164 |
| 3 | adamant | 163 |
| 4 | TheScrasse | 160 |
| 5 | nor | 157 |
| 6 | maroonrk | 156 |
| 7 | -is-this-fft- | 152 |
| 8 | Petr | 146 |
| 8 | orz | 146 |
| 10 | pajenegod | 145 |
You use a segment tree, but the cumuluation function should be xor instead of addition. Then you do what is written in statement, do updates and queries.
I think you have not read the problem clearly.
Yes, sorry. But now I think I have understood ;) Suggestion:
Let $$$n=j-i+1$$$ The contribution of $$$A_i$$$ is $$$n$$$ times. The contribution of $$$A_{i+1}$$$ is $$$(n-1)*2$$$ times. $$$A_k$$$ is $$$(n-k)*(k+1)$$$ times.
So for even n all contributions are even, ans=0. For odd n all $$$A_k$$$ at odd $$$k$$$ positions contribute. We can use two segment trees to store the values of even indexes in the one, and odd in the other.
Then on queries, we use dependent on the parity of $$$i$$$ the one or the other tree. Does this work or am I still missing something?
Solve for each bit separately.
The answer for a bit is then the number of subarrays that have odd sum. You can do this with a segment tree by storing some extra information in addition to the number of odd sum subarrays — the number of prefix and suffix subarrays that have odd/even sum and the total xor-sum of the subarray (these are necessary for merging). All that's left is to figure out the formulas for merging/initializing nodes and apply them. I've seen some smarter solutions (which I don't understand yet), but the slowest accepted solutions I saw using this approach ran in 1.6 seconds, which is fine.
Seconded....waiting for a solution , stuck in merging and combining approach ...