RACETIME - Race Against Time
题意翻译
### 题目描述:
现在有$n(1<=n<=1e5)$只奶牛站成一排,每只奶牛手中都拿着一个数字$A_i(0<=A_i<=1e9)$
现在$FJ$要执行$Q(1<=Q<=50000)$个操作,每个操作可能是下面两种操作之一:
$1.$ $M$ $i$ $X$ :将第$i$只奶牛手上的数字$A_i$替换为$X$
$2.$ $C$ $l$ $r$ $K$:询问区间$[l,r]$内有多少只奶牛手上拿的数字$A_i\le K$
作为$FJ$的好朋友,请你对每一个$2$操作输出答案
由于$FJ$非常蕉♂躁,所以他只允许你在$1s$内回答这些问题
### 输入输出格式:
#### 输入格式:
第一行输入两个正整数$n,Q$,含义如上
接下来$n$行,每一行输入一个正整数$A_i$,表示初始时第$i$只奶牛手上拿的数字$A_i$
接下来有$Q$行输入,代表$FJ$接下来要进行的$Q$个操作,格式如上文
#### 输出格式:
对于每一个$2$操作,请你输出满足条件的奶牛个数。每个答案占一行
题目描述
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 space-separated 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 space-separated numbers P, Q, and X.
Of course, FJ would like your help.
输入输出格式
输入格式
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".
输出格式
Print the answer to each 'C' query, one per line.
输入输出样例
输入样例 #1
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
输出样例 #1
2
3
4
2