50求调

#include<bits/stdc++.h>
using namespace std;
const int N = 1e6 + 100;
int n, q, blo, bl[N], a[N], tag[N];
void update(int l, int r, int k) {
	if (bl[l] == bl[r]) {
		for (int i = l; i <= r; i ++) {
			a[i] += k;
		}
		return ;
	}
	for (int i = l; i <= bl[l] * blo; i ++) {
		a[i] += k;
	}
	for (int i = bl[l] + 1; i <= bl[r] - 1; i ++) {
		tag[i] += k;
	}
	for (int i = (bl[r] - 1) * blo + 1; i <= r; i ++) {
		a[i] += k;
	}
	return ;
}
int ef(int s, int c) {
	int ans = 0;
	int l = (s - 1) * blo + 1;
	int r = s * blo;
//	cout << l << " " << r << "\n";
	sort (a + l, a + r + 1);
	while (l + 1 < r) {
		int mid = (l + r) / 2;
		if (a[mid] >= c) {
			r = mid;
		}
		else {
			l = mid;
		}
	}
	if (a[l] >= c) {
		ans = s * blo - l + 1;
	}
	else {
		ans = s * blo - r + 1; 
	}
	return ans;
}
void anser(int l, int r, int c) {
	int ans = 0;
	if (bl[l] == bl[r]) {
		for (int i = l; i <= r; i ++) {
			if (a[i] >= c) {
				ans ++;
			}
		}
		cout << ans << "\n";
		return ;
	}
	for (int i = l; i <= bl[l] * blo; i ++) {
		if (a[i] >= c) {
//			cout << a[i] << "\n";
			ans ++;
		}
	}
	for (int i = (bl[r] - 1) * blo + 1; i <= r; i ++) {
		if (a[i] >= c) {
			ans ++;
//			cout << a[i] << "\n";
		}
	}
//	cout << ans << "\n";
	for (int i = bl[l] + 1; i <= bl[r] - 1; i ++) {
		ans += ef(i, c - tag[i]);
//		cout << ef(i, c - tag[i]) << "\n\n";
	}
	cout << ans << "\n";
	return ;
}
signed main() {
	ios::sync_with_stdio(0);
	cin.tie(0), cout.tie(0);
	cin >> n >> q;
	blo = sqrt(n);
	for (int i = 1; i <= n; i ++) {
		cin >> a[i];
		bl[i] = (i - 1) / blo + 1;
	}
	while (q --) {
		char op;
		cin >> op;
		if (op == 'M') {
			int l, r, w;
			cin >> l >> r >> w;
			update(l, r, w);
		}
		else {
			int l, r, c;
			cin >> l >> r >> c;
			anser(l, r, c);
		}
	}
	return 0;
}