#P3343. 教主的魔法

教主的魔法

题目描述

教主最近学会了一种神奇的魔法,能够使人长高。于是他准备演示给 XMYZ 信息组每个英雄看。于是 NN 个英雄们又一次聚集在了一起,这次他们排成了一列,被编号为 1,2,⋯ ,N1,2,\cdots,N。
每个人的身高一开始都是不超过 10001000 的正整数。教主的魔法每次可以把闭区间 [L,R],(1≤L≤R≤N)[L, R],(1\le L\le R\le N) 内的英雄的身高全部加上一个整数 WW。(虽然 L=RL=R 时并不符合区间的书写规范,但我们可以认为是单独增加第 LL(RR)个英雄的身高)。
CYZ、光哥和 ZJQ 等人不信教主的邪,于是他们有时候会问 WD 闭区间 [L,R][L, R] 内有多少英雄身高大于等于 CC,以验证教主的魔法是否真的有效。
WD 巨懒,于是他把这个回答的任务交给了你。

输入格式

第 11 行为两个整数 N,QN,Q。QQ 为问题数与教主的施法数总和。
第 22 行有 NN 个正整数,第 ii 个数代表第 ii 个英雄的身高。
第 33 到第 Q+2Q+2 行每行有一个操作:
11: 若第一个字母为 M,则紧接着有三个数字 L,R,WL,R,W。表示对闭区间 [L,R][L, R] 内所有英雄的身高加上 WW。
22: 若第一个字母为 A,则紧接着有三个数字 L,R,CL,R,C。询问闭区间 [L,R][L, R] 内有多少英雄的身高大于等于 CC。

输出格式

对每个 A 询问输出一行,仅含一个整数,表示闭区间 [L,R][L, R] 内身高大于等于 CC 的英雄数。

5 3
1 2 3 4 5
A 1 5 4
M 3 5 1
A 1 5 4

2
3

样例解释

原先5个英雄身高为 1,2,3,4,51,2,3,4,5,此时 [1,5][1, 5] 间有 22 个英雄的身高大于等于 44。教主施法后变为 1,2,4,5,61,2,4,5,6,此时 [1,5][1, 5] 间有 33 个英雄的身高大于等于 44。

数据范围

对 30%30 \% 的数据,N≤1000,Q≤1000N\le 1000,Q\le 1000。 对 100%100 \% 的数据,$N\le 1000000,Q\le 3000,1\le W\le 1000,1\le C\le 10^9$。