adyyy's blog

help_segment_tree_problem!!
By adyyy, history, 5 years ago, In English

https://mirror.codeforces.com/gym/100739/problem/A Can anyone please help me out with this problem. It has no editoial.

  • Vote: I like it
  • -13
  • Vote: I do not like it

Comments Comments (5)
| Write comment?
»
5 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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.

→ Reply
  • »
    »
    5 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    I think you have not read the problem clearly.

    → Reply
    • »
      »
      »
      5 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      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?

      → Reply
»
5 years ago, # |
  Vote: I like it +1 Vote: I do not like it

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.

→ Reply
»
5 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Seconded....waiting for a solution , stuck in merging and combining approach ...

→ Reply