## CBOJ Exec Selection Contest 2 Problem 5 - Obligatory Data Structure Problem

Points: 12
Time limit: 0.7s
Java 1.0s
Memory limit: 256M

Author:
Problem type

You are given an array $$A$$ consisting of $$N$$ positive integers. You are required to support $$Q$$ queries of the following two forms:

• 1 x y: Change the element at the one-indexed position $$x$$ to $$y$$.
• 2 x y: Output the number of integers in the array that are greater than or equal to $$x$$ and less than or equal to $$y$$.

Can you solve it?

#### Input

The first line will contain two space separated integers, $$N$$ and $$Q$$, indicating the number of elements in the array and the number of queries, respectively.

The second line will contain $$N$$ space separated integers, representing the elements of $$A$$.

The next $$Q$$ lines will contain three space separated integers, representing the queries you are to perform.

#### Output

For each query of the second type, output the answer on its own line.

$$1 \le A_{i} \le 10^{9}$$

At any point in time, the maximum element in the array will not surpass $$10^{9}$$.

It is guaranteed that for all queries of the second type, $$x \le y$$ will be true.

##### Subtask 1 [30%]

$$1 \le N, Q \le 10^{3}$$

##### Subtask 2 [70%]

$$1 \le N, Q \le 3\times10^{4}$$

5 3
1 7 6 9 20
1 1 5
1 2 4
2 6 15

2

#### Explanation for Sample Output 1

After the first $$2$$ queries, the array becomes $$\{5,4,6,9,20\}$$. There are $$2$$ elements greater than or equal to $$6$$ and less than or equal to $$15$$, which are $$6$$ and $$9$$. So, we output $$2$$.