A Query Problem

Revision en2, by EternalFire, 2018-09-24 17:03:54

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 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.

History

 
 
 
 
Revisions
 
 
  Rev. Lang. By When Δ Comment
en3 English EternalFire 2018-09-24 17:18:53 5 Tiny change: 's greater or equal ' -> 's greater than or equal '
en2 English EternalFire 2018-09-24 17:03:54 11 Tiny change: 't elements which sat' -> 't elements, each by 1 which sat'
en1 English EternalFire 2018-09-24 17:03:07 456 Initial revision (published)