P2801 {{The Leader's Magic}}

{{}}

{{The leader has recently learned a magical spell that can make people taller. He plans to demonstrate it to every hero in the XMYZ Information Group. Thus, $N$ heroes gather once again, lining up in a row and being numbered $1, 2, \ldots, N$. Each person’s height is initially a positive integer not exceeding $1000$. Each time the leader casts the spell, he can add an integer $W$ to the heights of all heroes in the closed interval $[L, R]$ ($1≤L≤R≤N$). (Although $L=R$ is not standard interval notation, we can regard it as increasing only the height of the $L$-th hero.) CYZ, Guang Ge, and ZJQ do not believe in the leader’s magic, so they sometimes ask WD how many heroes in the closed interval $[L, R]$ have height greater than or equal to $C$, to verify whether the magic really works. WD is extremely lazy, so he hands this task over to you.}}

{{The first line contains two integers $N, Q$. $Q$ is the total number of queries and spells. The second line contains $N$ positive integers; the $i$-th number is the height of the $i$-th hero. Lines $3$ through $Q+2$ each contain one operation: 1. If the first letter is `M`, then three numbers $L, R, W$ follow. Add $W$ to the heights of all heroes in the closed interval $[L, R]$. 2. If the first letter is `A`, then three numbers $L, R, C$ follow. Query how many heroes in the closed interval $[L, R]$ have height greater than or equal to $C$.}}

{{For each `A` query, output one line containing a single integer: the number of heroes with height greater than or equal to $C$ in $[L, R]$.}}

{{Sample explanation: Originally, the $5$ heroes’ heights are $1, 2, 3, 4, 5$, so there are $2$ heroes in $[1, 5]$ whose heights are at least $4$. After the leader casts the spell, the heights become $1, 2, 4, 5, 6$, so there are $3$ heroes in $[1, 5]$ whose heights are at least $4$. Constraints: - For $30\%$ of the testdata, $N≤1000$, $Q≤1000$. - For $100\%$ of the testdata, $N≤10^6$, $Q≤3000$, $1≤W≤1000$, $1≤C≤10^9$. --- $\text{upd 2022.8.18}$: A new set of Hack testdata has been added. $\text{upd 2023.8.16}$: A new set of [Hack testdata](https://www.luogu.com.cn/discuss/661585) has been added.}} Translated by ChatGPT 5