ABC426F分块求调

#include <iostream>
#include <cmath>
using namespace std;
typedef long long ll;
const ll N=300005, sqN=555, INF=0x3f3f3f3f3f3f3f3f;
ll n, a[N], q, blk, t, pos[N], pl[sqN], pr[sqN], mina[sqN], cnt[sqN], tag[sqN];
int main(){
	scanf("%lld",&n);
	for(ll i=1;i<=n;i++) scanf("%lld",&a[i]);
	blk=sqrtl(n), t=n/blk+(n%blk>0);
	for(ll i=1;i<=t;i++){
		pl[i]=(i-1)*blk+1, pr[i]=min(i*blk,n), tag[i]=cnt[i]=0;
		for(ll j=pl[i];j<=pr[i];j++) pos[j]=i, mina[i]=min(mina[i],a[j]);
	}
	scanf("%lld",&q);
	while(q--){
		ll l, r, x, ans=0;
		scanf("%lld%lld%lld",&l,&r,&x);
		for(ll i=pos[l];i<=pos[r];i++){
			if(l<=pl[i]&&pr[i]<=r){
				if(mina[i]==INF) continue;
				if(mina[i]>x) ans+=(pr[i]-pl[i]+1-cnt[i])*x, mina[i]-=x, tag[i]-=x;
				else{
					mina[i]=INF, cnt[i]=0;
					for(ll j=pl[i];j<=pr[i];j++){
						a[j]+=tag[i];
						if(a[j]>x) ans+=x, a[j]-=x, mina[i]=min(mina[i],a[j]);
						else ans+=a[j], a[j]=0, cnt[i]++;
					}
					tag[i]=0;
				}
			}else{
				mina[i]=INF, cnt[i]=0;
				for(ll j=pl[i];j<=pr[i];j++){
					a[j]+=tag[i];
					if(j>r||j<l){
						if(a[j]>0) mina[i]=min(mina[i],a[j]);
						else cnt[i]++;
						continue;
					}
					if(a[j]>x) ans+=x, a[j]-=x, mina[i]=min(mina[i],a[j]);
					else ans+=a[j], a[j]=0, cnt[i]++;
				}
				tag[i]=0;
			}
		}
		printf("%lld\n",ans);
	}
	return 0;
}