Блог пользователя adyyy

help_segment_tree_problem!!
Автор adyyy, история, 4 года назад, По-английски

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

  • Проголосовать: нравится
  • -13
  • Проголосовать: не нравится

»
4 года назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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.

→ Ответить
  • »
    »
    4 года назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    I think you have not read the problem clearly.

    → Ответить
    • »
      »
      »
      4 года назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится

      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?

      → Ответить
»
4 года назад, # |
  Проголосовать: нравится +1 Проголосовать: не нравится

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.

→ Ответить
»
4 года назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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

→ Ответить