Ehsan_sShuvo's blog

Need Help!
By Ehsan_sShuvo, history, 7 years ago, In English

How to solve this problem ? Thanks!

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

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

Let . It's said, that arri are always non negative, that implies: Prefi ≤ Prefi + 1.

Let's first solve the answer query:

You want to find minimal Y, such that X < Y and PrefY - PrefX > C <  =  > PrefY > C - PrefX. If you found such Y than the answer is Y - X, if no such Y exists than answer is N - X + 1. To find such Y you can use binary-search + prefix-sum-query, that can be done with BIT.

Now let's solve update query:

If you change Ai to Y, than it's equal to add Y - Ai to all Prefk, i ≤ k ≤ N.

This works in O((N + Q) × logN2.

You can also solve this problem in O((N + Q) × logN) with segment tree.

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

    Thanks for your help :) . I have solved that problem ;

    But , here is another one [click here] . Could you please help me ?

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

      Think in terms of the way you merge 2 nodes to create an aggregate node. In each node keep the number of blocks (of 1) in that range. When merging two nodes with blocks a,b respectively, the number of blocks in the aggregate node will be a + b — 1 if last element in 1st subarray and first element in 2nd subarray are both 1 otherwise you will have a + b blocks in aggregate node. While updation just update the corresponding node and merge using the above technique. While retreiving answers again use the similar merge idea to aggregate two nodes data about number of blocks

      → Reply