abdo_mohammed's blog

how to solve it with data structure
By abdo_mohammed, history, 7 years ago, In English

how to solve it ?

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

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

Can you mention the source?

→ Reply
»
7 years ago, # |
← Rev. 2   Vote: I like it +10 Vote: I do not like it

I don't know if this is right :

In this problem, the key to be noted is that, the maximum that an element of the array could reach is 2e10.

So, even if we have to update each element by it's floor(sqrt(a[i])), it would need at most 6 — 7 updations, to make it reach 1. Once an element reaches 1, we don't need to update it any longer. How to find if some range has all 1's in it. We can have 2 segment trees, one for sum in range and other for finding max in range. After having done that, we just have to do this — every time a query comes of 2nd type i.e. updation, we will use the segment tree for finding max of the range, if a node already has 1 as max element in it, we don't need to update it, thus saving a lot of iterations, otherwise just update each element by floor(sqrt(a[i])) and accordingly change the node of the segment tree storing the sum.

Because of query of 3rd type, we also need to maintain a lazy tree. You don't have to add every time, just append the add to the lazy node. And when query of 1st and 2nd type comes, you just need to update those elements which falls under the range.

Before doing this, I would suggest you to solve this similar problem( just a bit easier ) : http://codeforces.net/problemset/problem/920/F

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

    your solution is correct if it hasn't the 3rd query and it floor not ceil

    → Reply
    • »
      »
      »
      7 years ago, # ^ |
        Vote: I like it +2 Vote: I do not like it

      I recently learnt segment tree and lazy propagation, and I am sorry if my solution is wrong, can you please help me understand how it won't work for 3rd query. Thanks in advance!

      → Reply
  • »
    »
    7 years ago, # ^ |
      Vote: I like it -9 Vote: I do not like it

    This will become O(N) per update for your max segment tree. What if you add 100000 to all the elements each time? Then you have to update every single one when a sqrt comes.

    → Reply
  • »
    »
    7 years ago, # ^ |
    ← Rev. 8   Vote: I like it +1 Vote: I do not like it

    If you just naively apply the sqrt-floor to all elements in the range, if operations 1 and 3 are repeatedly applied to the entire range, it takes O(n) time per operation of type 1.

    If you apply the sqrt-floor operation to a segment tree node, where not all of the elements below have the same value, it is hard to update the sum.

    However, you can store both the minimum and maximum below, and recurse until the minimum and maximum match, or return if maximum is one, and then apply the tag.

    This is essentially the same thing as the solution given to the "simple problem" in this fantastic blog about "Segment tree beats" ( http://codeforces.net/blog/entry/57319 ).

    This gets you a running time of (n + q) log(n) log(log(x)). However, this is around 1e7, so with 100 test cases, this solution would probably TLE.

    Attempt at a proof:

    Call a interval [a, b] a "Segment" if all of the values in the interval are the same, and the interval cannot be extended while maintaining this property. Call the value of the segment the value that all of the values in the interval are.

    Now, let F be a potential function, where F = log(n) * sum over all adjanced segments, how many sqrt's need to be taken from their values until both segments have the same value.

    Initially we have at most n segments, and for every one of them, the amount of sqrt's is at most log(log(x)). So initially potential function is at most n log(n) log(log(x)).

    Say sqrt-operation covers k segments with values greater than one completely. Then we do log(n) + klog(n) work in that sqrt-operation. The potential function however decreases by at least (k-1) log(n) due to applying sqrt to those segments, and increases at most 2 log(n) due to splitting some segments. Therefore sqrt-operation takes amortized log(n) time.

    Adding to a interval doesn't increase the contribution to the potential function of segments completely inside the interval, expect the one on its left end, and the one on its right end. The contribution of those increases by at most log(n) log(log(x)). Actual time taken is log(n), so adding to a interval takes amortized log(n) log(log(x)) time.

    → Reply