样例输出 6;7

笑死

#include <bits/stdc++.h>

using namespace std;

int x;
const int N =1e6 + 5;
int pos[N], st[N], ed[N], b[N], a[N], add[N];
void update(int l, int r, int val)
{
	int p = pos[l], p1 = pos[r];
	if(p == p1)
	{
		for(int i = l;i <= r;i ++ ) a[i] += val;
		for(int i = st[p];i <= ed[p];i ++ ) b[i] = a[i];
		sort(b + st[p], b + 1 + ed[p]);
	}
	else{
		for(int i = p;i < p1;i ++ ) add[i]  += val;
		for(int i = l;i <= ed[p];i ++ ) a[i] += val;
	 	for(int i = st[p];i <= ed[p];i ++ ) b[i] = a[i];
		sort(b + st[p], b + 1 + ed[p]);
		for(int i = st[p1];i <= r;i ++ ) a[i] += val;
		for(int i = st[p1];i <= ed[p1];i ++ ) b[i] = a[i];
		sort(b + st[p1], b + 1 + ed[p1]);
	}
}

int mid_find(int x, int i)
{
	int l = st[i], r = ed[i];
	int ans = -1;
	while(l <= r)
	{
		int mid = (l + r)>>1;
		if(b[mid] >= x) {
			ans = mid;
			r = mid - 1;
		}
		else l = mid + 1;
	}
	return ed[i] - ans + 1;
}

int query(int l, int r, int x)
{
	int p = pos[l], p1 = pos[r];
	int ans = 0;
	if(p == p1)
	{
		for(int i = l;i <= r;i ++ ){
			if(a[i] + add[p] >= x) ans++ ;
		}
	}
	else {
		for(int i = p;i < p1;i ++ ) ans += mid_find(x - add[i], i);
		for(int i = l;i <= ed[p];i ++ ){
			if(a[i] + add[p] >= x) ans ++ ;
		}
		for(int i = st[p1];i <= r;i ++ ){
			if(a[i] + add[p1] >= x) ans ++ ;
		}
	}
	return ans;
}

int main()
{
	int n, q;
	cin >> n >> q;
	for(int i = 1;i <= n;i ++ ) {
		cin >> a[i];
		b[i] = a[i];
	}
	int block = sqrt(n);
	int cnt = n / block;
	if(n % block) cnt ++ ;
	for(int i = 1;i <= n;i ++ ){
		st[i] = (i - 1) * block + 1;
		ed[i] = i * block;
	}
	ed[cnt] = n;
	for(int i = 1;i <= n;i ++ ) pos[i] = (i - 1) / block + 1;
	for(int i = 1;i <= n;i ++ ) cout << st[pos[i]] << ' ' << ed[pos[i]] << endl, sort(b + st[pos[i]], b + ed[pos[i]] + 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;
			cin >>l >> r>>x;
			cout << query(l, r, x)<< endl;
		}
	}
	return 0;
}