WA #9 #10

#include<iostream>
#include<stack>
#include<cstdio>
#include<cstring>
#include<vector>
#include <algorithm>
#include<queue>
#include<cmath>
#include<map>
#include<unordered_map>
#include<set>
#include<unordered_set>
#include<iomanip>
#include<iterator>

using namespace std;
#define IOS ios::sync_with_stdio(false);cin.tie(0);cout.tie(0)
#define ri register int 
typedef long long ll;
typedef long double ld;
const int N = 1e6 + 5, M = 2e5 + 5;
const int INF = 1e9;
const ll MOD = 1e9 + 7;

int n, m;
int root[N], cnt, siz;
int a[N], b[N];
struct Node {
	int L, R, sum;
}tree[N * 10];

int tag[N << 2];
bool vis[N << 2];

int ls(int p) { return p << 1; }
int rs(int p) { return p << 1 | 1; }
void push_down(int p) {
	if (tag[p]) {
		tag[ls(p)] += tag[p];
		tag[rs(p)] += tag[p];
		vis[ls(p)] = vis[rs(p)] = 1;
		tag[p] = 0;
	}
}
void addtag(int L, int R, int p, int pl, int pr, int x) {
	vis[p] = 1;
	if (L <= pl && pr <= R) {
		tag[p] += x;
		return;
	}
	push_down(p);
	int mid = (pl + pr) >> 1;
	if (L <= mid) addtag(L, R, ls(p), pl, mid, x);
	if (R > mid) addtag(L, R, rs(p), mid + 1, pr, x);
}
int update(int pre, int pl, int pr, int x) {
	int rt = ++cnt;
	tree[rt].L = tree[pre].L;
	tree[rt].R = tree[pre].R;
	tree[rt].sum = tree[pre].sum + 1;
	int mid = (pl + pr) >> 1;
	if (pl < pr) {
		if (x <= mid) tree[rt].L = update(tree[pre].L, pl, mid, x);
		else tree[rt].R = update(tree[pre].R, mid + 1, pr, x);
	}
	return rt;
}
int ask(int u, int v, int pl, int pr, int k) {
	int x = tree[tree[v].L].sum - tree[tree[u].L].sum;
	int mid = (pl + pr) >> 1;
	int ans = 0;
	if (pl < pr) {
		if (k <= mid) ans += ask(tree[u].L, tree[v].L, pl, mid, k);
		else ans += ask(tree[u].R, tree[v].R, mid + 1, pr, k) + x;
	}
	return ans;
}
int query(int L, int R, int p, int pl, int pr, int x) {
	int ans = 0;
	if (L <= pl && pr <= R) {
		if (tag[p]) {
			int k = lower_bound(b + 1, b + 1 + siz, x - tag[p]) - b;
			ans += (tree[root[pr]].sum - tree[root[pl - 1]].sum) - ask(root[pl - 1], root[pr], 1, siz, k);
			return ans;
		}
		else if (!vis[p]) {
			int k = lower_bound(b + 1, b + 1 + siz, x) - b;
			ans += (tree[root[pr]].sum - tree[root[pl - 1]].sum) - ask(root[pl - 1], root[pr], 1, siz, k);
			return ans;
		}
	}
	push_down(p);
	int mid = (pl + pr) >> 1;
	if (L <= mid) ans += query(L, R, ls(p), pl, mid, x);
	if (R > mid) ans += query(L, R, rs(p), mid + 1, pr, x);
	return ans;
}
int main() {
	IOS;
	cin >> n >> m;
	for (int i = 1; i <= n; i++) {
		cin >> a[i];
		b[i] = a[i];
	}
	sort(b + 1, b + 1 + n);
	siz = unique(b + 1, b + 1 + n) - b - 1;
	for (int i = 1; i <= n; i++) {
		int x = lower_bound(b + 1, b + 1 + siz, a[i]) - b;
		root[i] = update(root[i - 1], 1, siz, x);
	}
	for (int i = 1; i <= m; i++) {
		char op;
		cin >> op;
		if (op == 'M') {
			int L, R, x;
			cin >> L >> R >> x;
			addtag(L, R, 1, 1, n, x);
		}
		else {
			int L, R, v;
			cin >> L >> R >> v;
			cout << query(L, R, 1, 1, n, v) << endl;
		}
	}

	return 0;
}