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

Need Help!
Автор Ehsan_sShuvo, история, 7 лет назад, По-английски

How to solve this problem ? Thanks!

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

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

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.

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

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

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

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

      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

      → Ответить