11392: SPOJ GIVEAWAY - Give Away
[Creator : ]
Description
You are given a 1-indexed array $X$, consisting of $N$ integers, and a set of $Q$ queries. There are two kinds of queries:
-
0 a b c
Here you are required to return the number of elements with indices in $[a,b]$ greater than or equal to $c$ -
1 a b
Here you are required to change the $a$-th element of array to $b$.
Input
First line contains $N$, the number of elements in the array $X$.
The next line contains $N$ space separated integers representing the elements of $X$.
The third line of input contains a single integer, $Q$, the number of queries.
The next $Q$ lines of input each contain queries of two kinds as described above.
Output
$Q$ lines with the $i$-th line contains the answer for the $i$-th query
Constraints
$1 ≤ N ≤ 5*10^5$
$1 ≤ Q ≤ 10^5$
$1 ≤ X[i] ≤ 10^9$
$1 ≤ a ≤ b ≤ N$ for query
$1 ≤ a ≤ 10^5, 1 < b ≤ 10^9$ for query
$1 ≤ c ≤ 10^9$
$1 ≤ Q ≤ 10^5$
$1 ≤ X[i] ≤ 10^9$
$1 ≤ a ≤ b ≤ N$ for query
type 0$1 ≤ a ≤ 10^5, 1 < b ≤ 10^9$ for query
type 1$1 ≤ c ≤ 10^9$
Sample 1 Input
5
1 2 3 4 5
3
0 1 5 10
1 2 20
0 1 3 10
Sample 1 Output
0
1