https://www.luogu.com.cn/problem/P2801

提交：

https://www.luogu.com.cn/record/136864478

代码：

#include<iostream>
#include<algorithm>
#include<vector>
#include<cstdio>
#include<cmath>
#define ll long long 
using namespace std;
const int N=1e6+10;
const int MXN=1e4+10;
ll n,q,bl,cnt;
ll bel[N],val[N],mar[N];
vector<ll> blocks[MXN];
void init()
{
	ll i;
	for(i=1;i<=cnt;++i)
		sort(blocks[i].begin(),blocks[i].end());
}
void upd(ll pos)
{
	ll i;
	blocks[pos].clear();
	for(i=pos*bl+1-bl;i<=pos*bl;++i)
		blocks[pos].push_back(val[i]);
	sort(blocks[pos].begin(),blocks[pos].end());
}
void add_blocks(ll l,ll r,ll x)
{
	ll i,sz=min(r,bel[l]*bl);
	for(i=l;i<=sz;++i)
		val[i]+=x;
	upd(bel[l]);
	if(bel[l]!=bel[r])
	{
		for(i=bel[l]+1;i<bel[r];++i)
			mar[i]+=x;//mid - all - blocks
		for(i=(bel[r]-1)*bl+1;i<=r;++i)
			val[i]+=x;//nblocks - right
		upd(bel[r]);
	}
}
ll calc_blocks(ll l,ll r,ll x)
{
	ll i,sum=0,sz=min(r,bel[l]*bl);
	for(i=l;i<=sz;++i)
		if(val[i]+mar[bel[i]]>=x)//nblocks - left
			++sum;
	if(bel[l]!=bel[r])
	{
		for(i=bel[l]+1;i<bel[r];++i)
		{
			ll lef,rig,mid;
			lef=0,rig=bl-1;
			while(lef<=rig)
			{
				mid=(rig-lef)>>1;
				if(blocks[i][mid+lef]+mar[i]<x)
					lef=mid+1;
				else
					rig=mid-1;
			}
			sum+=bl-lef;
		}
		for(i=bel[r]*bl+1-bl;i<=r;++i)
		{
			if(val[i]+mar[bel[i]]>=x)//nblocks - right 
				++sum;
		}
	}
	return sum;
}
int main()
{
	ll i;
	scanf("%lld%lld",&n,&q);
	bl=sqrt(n);
	for(i=1;i<=n;++i)
	{
		cin>>val[i];
		if(i%bl==1)
			++cnt;
		bel[i]=cnt;
		blocks[cnt].push_back(val[i]);
	}
	init();
	while(q--)
	{
		char opt;
		ll x,y,z;
		cin>>opt;
		scanf("%lld%lld%lld",&x,&y,&z);
		if(opt=='M')
			add_blocks(x,y,z);
		else if(opt=='A')
			printf("%lld\n",calc_blocks(x,y,z));
	}
	return 0;
}

40tps 帮我找错，球球了。。。