GIVEAWAY  Give Away
You are given a 1indexed 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 Format:
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 Format:
Q lines with the ith 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 type 0
1 ≤ a ≤ 10^5, 1 < b ≤ 10^9 for query type 1
1 ≤ c ≤ 10^9
Example
Sample Input: 5 1 2 3 4 5 3 0 1 5 10 1 2 20 0 1 3 10 Sample Output: 0 1
Problem Setter: Pulkit Goel and Vidit Gupta
hide comments
hackerbhaiya:
20210623 18:53:01
Time limit is more than 2sec. Square Root Decomposition will pass. No need to use PBDS as I solved without it. Last edit: 20210623 18:53:34 

noobmaster__69:
20210427 09:13:37
Square root decomposition + policy based ds 

adia:
20210117 22:45:32
compilation error in one go <3 

dharan1011:
20200921 15:20:20
AC in one GO. 

prabal08:
20200812 11:38:29
Any test cases guys? 

brandonbreyers:
20200718 12:44:56
I was getting wa for test case 10 again and again, realised that i had to handle the case of the 1st query where a and b could be in the same block 

leetcode07:
20200710 14:46:27
I use sqrt decompose and policybased c++ ds but the code fails on test case #10. Please help 

pratyushmj1:
20200603 15:45:17
A story about Test cases,


harshraj22aug:
20200102 09:41:15
Last edit: 20200102 10:19:23 

scolar_fuad:
20191109 17:34:18
sqrt decompose + binary search ...

Added by:  darkshadows 
Date:  20140128 
Time limit:  1s2s 
Source limit:  50000B 
Memory limit:  1536MB 
Cluster:  Cube (Intel G860) 
Languages:  All except: ASM64 