提出 #69862122

---

ソースコード 拡げる

/*
*            /$$           /$$
*           |__/          |__/
*  /$$$$$$$$ /$$ /$$$$$$$$ /$$  /$$$$$$
* |____ /$$/| $$|____ /$$/| $$ /$$__  $$
*    /$$$$/ | $$   /$$$$/ | $$| $$  \ $$
*   /$$__/  | $$  /$$__/  | $$| $$  | $$
*  /$$$$$$$$| $$ /$$$$$$$$| $$|  $$$$$$$
* |________/|__/|________/|__/ \____  $$
*                                   | $$
*                                   | $$
*                                   |__/
*/
//hj23308保佑我
//Missile保佑我
/*
* 醒了在梦里挣扎，不觉黯淡了朝霞
*/
/*
* 我很高兴你没有忘了我，但是我现在更希望你已经忘了我了。
* 希望在你的记忆中，我只是尘土一撮，从你的全世界路过，然后四散飞扬不留下一点痕迹，而你要不回头的往前走。
* 我更希望我只是从你的全世界路过，只是路过
*/
/*
* 只是我在十字路口守了太久，守到黄沙如雨掩埋一切痕迹，才发现自己等的人已经离开了。
*/
/*
* 听我的 别回头 回头就可能会泪流满面，会被黄沙掩埋，所以即使痛苦也要向前走
*/
/*
* 我听到了「天行健」的回响，这是一个伟大斗士的不息自强；
* 我听到了「破万法」的回响，这是一个黑道打手的守护欲望；
* 我看见了「生生不息」的激荡，这是一个骗子的伟大乐章！
*/
/*
* 我用虚假的面具照顾着细腻的感情；
* 我以华丽的衣物下藏着腐烂的血肉；
* 当我摘下面具，褪去衣物，即便是我最亲近的人，也无法直视我
*/
#include<bits/stdc++.h>
using namespace std;
mt19937 engine(chrono::steady_clock().now().time_since_epoch().count());
const int MAXN=3e5+5;
const long long inf=1e18;
int n,q;
long long a[MAXN];
struct SGT {
	#define Ls(u) (u<<1)
	#define Rs(u) (u<<1|1)
	long long sum;
	int siz[4*MAXN];
	long long Min[4*MAXN],lazy[4*MAXN];
	void push(int u,long long val)
	{
		Min[u]-=val;
		lazy[u]+=val;
	}
	void pushDown(int u)
	{
		if(lazy[u]) {
			push(Ls(u),lazy[u]);
			push(Rs(u),lazy[u]);
			lazy[u]=0;
		}
	}
	void pushUp(int u)
	{
		siz[u]=siz[Ls(u)]+siz[Rs(u)];
		Min[u]=min(Min[Ls(u)],Min[Rs(u)]);
	}
	void Build(int u,int l,int r)
	{
		if(l==r) {
			siz[u]=1,Min[u]=a[l];
			return;
		}
		int mid=(l+r)>>1;
		Build(Ls(u),l,mid);
		Build(Rs(u),mid+1,r);
		pushUp(u);
	}
	void Modify(int u,int l,int r)
	{
		if(Min[u]>=0) return;
		if(l==r) {
			sum+=Min[u];
			Min[u]=inf,siz[u]=0;
			return;
		}
		pushDown(u);
		int mid=(l+r)>>1;
		Modify(Ls(u),l,mid);
		Modify(Rs(u),mid+1,r);
		pushUp(u);
	}
	void Query(int u,int l,int r,int L,int R,int k)
	{
		if(L<=l&&r<=R) {
//			cout<<siz[u]<<" * "<<k<<" and "<<Min[u]<<"\n";
			sum+=1ll*siz[u]*k;
			push(u,k);
			Modify(u,l,r);
			return ;
		}
		pushDown(u);
		int mid=(l+r)>>1;
		if(L<=mid) Query(Ls(u),l,mid,L,R,k);
		if(mid+1<=R) Query(Rs(u),mid+1,r,L,R,k);
		pushUp(u);
	}
}tree;
int main()
{
//	freopen(".in","r",stdin);
//	freopen(".out","w",stdout);
	std::ios::sync_with_stdio(false);
	cin.tie(0),cout.tie(0);
	cin>>n;
	for(int i=1;i<=n;i++) {
		cin>>a[i];
	}
	tree.Build(1,1,n);
	cin>>q;
	while(q--) {
		int l,r,k;
		cin>>l>>r>>k;
		tree.sum=0;
		tree.Query(1,1,n,l,r,k);
		cout<<tree.sum<<"\n";
	}
	return 0;
}

提出情報

ジャッジ結果