RACETIME  Race Against Time
As another one of their crazy antics, the N (1 ≤ N ≤ 100,000) cows want Farmer John to race against the clock to answer some of their pressing questions.
The cows are lined up in a row from 1 to N, and each one is holding a sign representing a number, A_{i} (1 ≤ A_{i} ≤ 1,000,000,000). The cows need FJ to perform Q (1 ≤ Q ≤ 50,000) operations, which can be either of the following:
 Modify cow i's number to X (1 ≤ X ≤ 1,000,000,000). This will be represented in the input as a line containing the letter M followed by the spaceseparated numbers i and X.
 Count how many cows in the range [P, Q] (1 ≤ P ≤ Q ≤ N) have A_{i} ≤ X (0 ≤ X ≤ 1,000,000,000). This will be represented in the input as a line containing the letter C followed by the spaceseparated numbers P, Q, and X.
Of course, FJ would like your help.
Input
The first line gives the integers N and Q, and the next N lines give the initial values of A_{i}. Finally, the next Q lines each contain a query of the form "M i X" or "C P Q X".
Output
Print the answer to each 'C' query, one per line.
Example
Input: 4 6 3 4 1 7 C 2 4 4 M 4 1 C 2 4 4 C 1 4 5 M 2 10 C 1 3 9 Output: 2 3 4 2
FJ has 4 cows, whose initial numbers are 3, 4, 1, and 7. The cows then give him 6 operations; the first asks him to count the how many of the last three cows have a number at most 4, the second asks him to change the fourth cow's number to 1, etc.
Warning: large input/output data.hide comments
canhnam357:
20221215 15:21:37
coordinate compression + sqrtdecomposition + fenwick2d 

lzwhindsers:
20220912 08:12:05
OH！I got AC just now. 

lzwhindsers:
20220912 08:03:04
It's too hard for me to solve this without my WA data.I can't hack myself. 

lzwhindsers:
20220912 08:02:04
Friends,how can I get my WA data? 

kshitij917050:
20220119 16:47:43
getting WA on TC7 using sqrt decomposition with binary search 

nikhil0010:
20211018 03:34:02
Simple sqrt decomposition with binary search :) 

zerojude:
20210727 09:45:24
my merge sort Tree giving TLE what to do.....


sanchit2812:
20200711 23:59:07
Why my code with N*log2(N) not passing


hchauhan7816:
20200429 15:29:21
AC in one go using sqrt decomposition. No issue faced for TLE ( I think there must be some implementation problem or the Time Constraints might have been updated). 

thanos_tapras:
20200321 17:29:01
Really nice problem.

Added by:  Neal Wu 
Date:  20081025 
Time limit:  1s1.200s 
Source limit:  50000B 
Memory limit:  1536MB 
Cluster:  Cube (Intel G860) 
Languages:  All except: ERL JSRHINO 