Numbers less than X of a range in an array

Revision en1, by 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. :)

Tags segment tree, sqrt_decomposition, data structures

History

 
 
 
 
Revisions
 
 
  Rev. Lang. By When Δ Comment
en1 English john_hopes 2016-01-19 16:07:02 593 Initial revision (published)