### PROBLEM LINK:

**Author:** Chhekur

**Tester:** Pankaj Devesh

**Editorialist:** Pawan Kushwah

### DIFFICULTY:

Easy

### PREREQUISITES:

Segment Tree, SQRT Decomposition, DP

### PROBLEM:

You have to print number of elements in given range (L,R), which are strictly greater than K.

### QUICK EXPLANATION:

You are given an array of elements and you have to perform Q queries on it.

In update query you have to replace the X^{th} element of array with value Y.

In range query you have to iterate all the element in range from L to R and count elements, which are strictly greater than K.

### EXPLANATION:

For an efficient solution of this problem, you must approach this problem via SQRT Decomposition or Segement Tree.

First of all you have to decompose the given array as follows:

- If the length of given array is n, then size of one decomposed block would be √
_{n}. - And number of such decomposed blocks would be ceil(n/size_of_one_decomposed_block).
- For update query, you have to update a particular element of given array as well as the equivalent block of decomposed array.
- For range query, you have to iterate decomposed array according to given range (L,R).

Author’s solution can be found here.