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, Ai (1 ≤ Ai ≤ 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 space-separated numbers i and X.
  • Count how many cows in the range [P, Q] (1 ≤ P ≤ Q ≤ N) have Ai ≤ X (0 ≤ X ≤ 1,000,000,000). This will be represented in the input as a line containing the letter C followed by the space-separated 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 Ai. 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
zerojude: 2021-07-27 09:45:24

my merge sort Tree giving TLE what to do.....
time complexity- O( N*LogN^2 + Q*LogN^2)

sanchit2812: 2020-07-11 23:59:07

Why my code with N*log2(N) not passing
?

hchauhan7816: 2020-04-29 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: 2020-03-21 17:29:01

Really nice problem.
Take note of queries that lie in the same block (when using sqrt decomp)

laithhelwany_: 2020-03-13 12:31:01

solved using Microsoft Powerpoint

scolar_fuad: 2020-02-25 19:08:14

bruteforce solution will pass the time limit
try to solve it sqrt segmentation or segment tree
happy coding

sarwar__05: 2019-07-15 09:35:48

similar to GIVEAWAY

a_ranjan: 2019-06-21 10:14:34

Holy F*** ! My sqrt decomposition code got TLE and N*Q brute forciiiiiie got AC . Hahhahaha!!!!

kshubham02: 2019-04-21 21:20:56

N*log^2(N) times out.
Brute force in N*Q passes.
????????????????

aimbot: 2018-01-10 19:23:33

very good problem

Last edit: 2018-01-10 19:23:58

Added by:Neal Wu
Date:2008-10-25
Time limit:1s-1.200s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All except: ERL JS-RHINO