EternalFire's blog

A Query Problem
By EternalFire, history, 6 years ago, In English

Given an array A consist of N integers. (N <= 10^5). There are Q (Q <= 10^5) queries of two types:

  • 1 x y: Increase x smallest elements, each by 1 which satisfy the following condition: all elements greater than or equal to y. (1 <= x <= N, 0 <= y <= 10^9).

  • 2 l r: Count the number of elements in array A have value in range [l..r]. (1 <= l <= r <= 10^9).

I haven't found an approach to process queries type 1 yet. Could someone help me? Thanks.

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

»
6 years ago, # |
← Rev. 2   Vote: I like it +13 Vote: I do not like it

Sort the initial array and use segment tree with lazy propagation.

Lets say your array is now 2 3 4 4 4 4 4 5 6 7 and you have to increase the first 5 elements

You can binary search for the last element that has the same value as the xth element and update like this.

(2+1) (3+1) 4 4 (4+1) (4+1) (4+1) 5 6 7

It can be done with 2 range updates.

The array maintains monotone.

For queries of type 2 just do binary search

Im not sure what you mean about that y thing but i think you can deal with it with binary search.

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

    If the array is 2 3 4 4 4 4 4 5 6 7 then if x = 3 and y = 5 you have to increase the last three elements.

    But I understood your idea, I think it's correct. Thanks for your help.

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

    Got accepted. Many thanks, I learnt new technique today.

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

      can u post the link to the original problem .

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

        how to find the list of elements which we have to increase

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

          You can use segment tree with binary search.

          Assume that you want to find the position of the last element <= val. Then you look at right node, if minimum value of right node <= val then jump to right node, else jump to left node

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

        https://oj.uz/problem/view/BOI11_grow

        Baltic Olympiad In Informatics 2011 Task Grow

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

For query 1 , after sorting the array , we will find the lower bound of y in the array and we will also get the index of that element (say lb) , now we update the the range lb to lb+x-1 (0-based indexing) using lazy prop.! correct me if I'm wrong and also how to answer the type 2 query ?

→ Reply