为什么这么写能对

// Problem: P2801 教主的魔法
// Contest: Luogu
// URL: https://www.luogu.com.cn/problem/P2801
// Memory Limit: 128 MB
// Time Limit: 1000 ms
// 
// Powered by CP Editor (https://cpeditor.org)

#include <algorithm>
#include <cmath>
#include <cstdio>

constexpr int N = 1e6 + 5, B = 1e3 + 5;

int query(int l, int r, int c);
void update(int l, int r, int w);

int n, q, l, r, w, c, len, a[N], s[N], id[N], st[B], ed[B], tag[B];
char op;

int main(void)
{
	scanf("%d %d", &n, &q);
	len = sqrt(n);
	
	for (int i = 1; i <= n; i++)
	{
		scanf("%d", &a[i]);
		s[i] = a[i];
		id[i] = (i - 1) / len + 1;
	}
	
	for (int i = 1; (i - 1) * len < n; i++)
	{
		st[i] = std::min((i - 1) * len + 1, n);
		ed[i] = std::min(n, i * len);
		// printf("%d Sort [%d, %d) [%p, %p) SIZE %d\n", i, st[i], ed[i] + 1, s + st[i], st + ed[i] + 1, s + st[i] < s + ed[i] + 1);
		std::sort(st + ed[i] + 1, s + st[i]); // 注意这里
	}
	
	for (int i = 1; i <= q; i++)
	{
		scanf(" %c", &op);
		
		if (op == 'A')
		{
			scanf("%d %d %d", &l, &r, &c);
			printf("%d\n", query(l, r, c));
		}
		else if (op == 'M')
		{
			scanf("%d %d %d", &l, &r, &w);
			update(l, r, w);
		}
	}
	
	#define _ 0
	return ~~(0^_^0);
	#undef _
}

int query(int l, int r, int c)
{
	int res = 0;
	
	if (id[l] == id[r])
	{	
		for (int i = l; i <= r; i++) res += a[i] >= c;
		return res;
	}
	
	for (int i = l; id[i] == id[l]; i++) res += a[i] >= c;
	for (int i = id[l] + 1; i < id[r]; i++) res += s + i * len - std::lower_bound(s + (i - 1) * len + 1, s + i * len, c - tag[i]);
	for (int i = r; id[i] == id[r]; i--) res += a[i] >= c;
	
	return res;
}

void update(int l, int r, int w)
{
	if (id[l] == id[r])
	{
		for (int i = l; i <= r; i++) a[i] += w;
		for (int i = st[id[l]]; i <= ed[id[r]]; i++) s[i] = a[i];
		std::sort(s + st[id[l]], s + ed[id[r]] + 1);
		return;
	}
	
	for (int i = l; id[i] == id[l]; i++) a[i] += w;
	for (int i = st[id[l]]; i <= ed[id[l]]; i++) s[i] = a[i];
	std::sort(s + st[id[l]], s + ed[id[l]] + 1);
	
	for (int i = id[l] + 1; i < id[r]; i++) tag[i] += w;
	
	for (int i = r; id[i] == id[r]; i--) a[i] += w;
	for (int i = st[id[r]]; i < ed[id[r]]; i++) s[i] = a[i];
	std::sort(s + st[id[r]], s + ed[id[r]] + 1);
}