shreyk's blog

Need help in a range query problem
By shreyk, history, 13 months ago, In English

Problem Link
Here is my approach:
Suppose for the $$$i$$$th operation the value is $$$y_i$$$ for $$$x_i$$$ coordinate then for every $$$x_j$$$ > $$$x_i$$$ their $$$y$$$ coordinate value gets updated to $$$2y_i-y_j$$$. So, the value for $$$y$$$ gets updated in a fashion $$$2y_1-2y_2+2y_3... - y_0$$$ for $$$x_0$$$. I can't think of a way to implement this alternating sign change pattern. Kindly help.

  • Vote: I like it
  • +4
  • Vote: I do not like it

»
13 months ago, hide # |
 
Vote: I like it 0 Vote: I do not like it

$$$O(q^2) $$$ should easily pass.

→ Reply
»
13 months ago, hide # |
← Rev. 5  
Vote: I like it 0 Vote: I do not like it

I got AC in 7234 ms, so I think I can help you with this question.

Main idea: Notice that the difference between two elements will always be either 1 or -1, so we can transform the problem in the following way: given a list A = [1, 1, 1, 1, ..., 1], you have two operations:

  1. Multiply all the values from [x,N] by -1 (the reflection).

  2. Get the cumulative sum from [0,x-1].

You can do that with a lazy segtree. The lazy segtree updates by setting a node as the negative value, if there is an update on top of another we don't update and we merge nodes by summing them. Something like that:

Spoiler

The above code runs in 14296 ms, really close to the time limit. I reimplemented my segtree without some of the abstractions and it ran in 7234 ms, so the ideia should be around this.

→ Reply
  • »
    »
    13 months ago, hide # ^ |
    ← Rev. 2  
    Vote: I like it 0 Vote: I do not like it

    Oh, I forgot to comment: allocating this segtree for every test case is too costly, because it has size MAX_N = 1e5 + 5, so instead we undo the operations. We can do that by saving the operations and undoing in reverse order (technically it could be in any order, as multiplying by -1 is commutative).

    → Reply
    • »
      »
      »
      13 months ago, hide # ^ |
       
      Vote: I like it 0 Vote: I do not like it

      Wrong, no need to undo, creating segtree of 1e5 size on each testcase is fine (6640 ms my time)

      → Reply
  • »
    »
    13 months ago, hide # ^ |
     
    Vote: I like it +11 Vote: I do not like it

    And no need to transform the problem to the difference array, just work with the initial (multiply suffix by -1 and add 2 * f(x) to it).

    → Reply