Numbers less than X of a range in an array

Правка en1, от john_hopes, 2016-01-19 16:07:02

You'll be given an Array of N elements and Q queries.

Here N and Q is a non-negative integer and maximum value of N and Q is 100000.

There are two types of query.

One is : 1 P V , this means that you have to change P-th element of the array to V.

Another is : 2 L R X , this means that you have to output the number of elements less than or equal to X in L to R range of the array.

How can I solve this problem? I know the solution if there is no update operation. But this problem contains update operation.

Thanks in Advance. :)

Теги segment tree, sqrt_decomposition, data structures


  Rev. Язык Кто Когда Δ Комментарий
en1 Английский john_hopes 2016-01-19 16:07:02 593 Initial revision (published)