1887C - Minimum Array - CodeForces Solution

#include<bits/stdc++.h>
#define endl '\n'
using namespace std;
using ll=long long;
void solve();
int main(){
    cin.tie(nullptr)->sync_with_stdio(false);
	int t=1;
	cin>>t;
	while(t--)solve();
}

const int N=5e5+3;
ll a[N];
struct seg{
	bool sm;
	ll s;
}T[N<<2];
void pls(int p,int l,int r,int x,int y,int d){
	if(l>=x&&r<=y){
		T[p].s+=d;
		return;
	}
	int mid=l+r>>1;
	if(T[p].sm){
		T[p<<1].sm=1;T[p<<1].s=T[p].s;
		T[p<<1|1].sm=1;T[p<<1|1].s=T[p].s;
		T[p].s=T[p].sm=0;
	}
	else{
		T[p<<1].s+=T[p].s;
		T[p<<1|1].s+=T[p].s;
		T[p].s=0;
	}
	if(mid>=x)pls(p<<1,l,mid,x,y,d);
	if(mid+1<=y)pls(p<<1|1,mid+1,r,x,y,d);
	if(T[p<<1].sm&&T[p<<1|1].sm&&T[p<<1].s==T[p<<1|1].s)T[p]=T[p<<1];
}
bool bin(int p,int l,int r){
	if(T[p].sm)return T[p].s<0;
	T[p<<1].s+=T[p].s;
	T[p<<1|1].s+=T[p].s;
	T[p].s=0;
	int mid=l+r>>1;
	if(T[p<<1].sm&&!T[p<<1].s)return bin(p<<1|1,mid+1,r);
	return bin(p<<1,l,mid);
}
void clear(){
	T[1]={1,0};
}
struct node{int l,r,x;};
void solve(){
	int n;cin>>n;
	for(int i=1;i<=n;i++)cin>>a[i];
	int q;cin>>q;
	vector<node>Q;
	clear();
	int m=0;
	for(int i=1;i<=q;i++){
		node t;
		auto &[l,r,x]=t;
		cin>>l>>r>>x;
		Q.push_back(t);
		pls(1,1,n,l,r,x);
		if(bin(1,1,n)){
			m=i;
			clear();
		}
	}
	// cout<<"! "<<m<<endl;
	for(int i=n;i;i--)a[i]-=a[i-1];
	for(int i=0;i<m;i++){
		a[Q[i].l]+=Q[i].x;
		a[Q[i].r+1]-=Q[i].x;
	}
	for(int i=1;i<=n;i++){
		a[i]+=a[i-1];
		cout<<a[i]<<" ";
	}
	cout<<endl;
}