记答案为\(ans_i\)，表示从1到i次修改出现的字典序最小的数组a, \(c\)数组表示\(ans_i\)出现之后，所有修改的累加和。用一个vector存一下\(ans_i\)之后的所有修改。从1到q遍历每一次修改时，对\(c\)数组进行区间赋值操作，如果\(c\)数组中第一个不为0的数<0,那么\(ans_i\)加上\(c\)中的所有数，字典序会变得更小，所以将vector存的所有的区间赋值操作都加到\(ans_i\)上，并清空\(c\)数组。
使用两个维护区间最小值和最大值，可以区间赋值的线段树，其中一个维护\(ans_i\)，另一个维护的是\(c\)数组,要找到\(c\)数组中第一个不为0的数，可以用线段树上二分实现
注意找第一个不为0的数需要同时维护最小值和最大值
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int,int> pii;
typedef pair<int,ll> pil;
const int N=5e5+10,INF=0x3f3f3f3f,mod=998244353;
int a[N],b[N];
struct info{
ll minv,maxn;
info(ll x=0):minv(x),maxn(x){}
info operator+(info b){
info c;
c.minv=min(minv,b.minv);
c.maxn=max(maxn,b.maxn);
return c;
}
};
struct node{
int l,r;
ll t;
info val;
};
void settag(node&u,ll t){
u.val.minv+=t;
u.val.maxn+=t;
u.t+=t;
}
struct SegmentTree{
vector<node>tr;
SegmentTree(int n,int num[]):tr(n<<2){
function<void(int,int,int)>build=[&](int u,int l,int r){
if(l==r) {
tr[u]={l,r,0,{num[l]}};
}
else {
tr[u]={l,r,0};
int mid=l+r>>1;
build(u<<1,l,mid),build(u<<1|1,mid+1,r);
pushup(u);
}
};
build(1,1,n);
}
void pushdown(int u){
if(tr[u].t){
settag(tr[u<<1],tr[u].t);
settag(tr[u<<1|1],tr[u].t);
tr[u].t=0;
}
}
void pushup(int u){
tr[u].val=tr[u<<1].val+tr[u<<1|1].val;
}
void modify(int u,int l,int r,int t){
if(tr[u].l>=l&&tr[u].r<=r){
settag(tr[u],t);
}
else {
pushdown(u);
int mid=tr[u].l+tr[u].r>>1;
if(l<=mid) modify(u<<1,l,r,t);
if(r>mid) modify(u<<1|1,l,r,t);
pushup(u);
}
}
info query(int u,int l,int r){
if(tr[u].l>=l&&tr[u].r<=r) return tr[u].val;
else {
pushdown(u);
int mid=tr[u].l+tr[u].r>>1;
if(r<=mid) return query(u<<1,l,r);
else if(l>mid) return query(u<<1|1,l,r);
else return query(u<<1,l,r)+query(u<<1|1,l,r);
}
}
int find1(int u,ll x){
if(tr[u].l==tr[u].r) return tr[u].val.maxn>x?tr[u].l:INF;
else {
pushdown(u);
if(tr[u<<1].val.maxn>x) return find1(u<<1,x);
else return find1(u<<1|1,x);
}
}
int find2(int u,ll x){
if(tr[u].l==tr[u].r) return tr[u].val.minv<x?tr[u].l:INF;
else {
pushdown(u);
if(tr[u<<1].val.minv<x) return find2(u<<1,x);
else return find2(u<<1|1,x);
}
}
};
void solve(){
int n;
cin>>n;
for(int i=1;i<=n;i++) cin>>a[i],b[i]=0;
SegmentTree ans(n,a);
SegmentTree c(n,b);
// for(int i=1;i<=n;i++) cout<<ans.query(1,i,i).minv<<" ";
// cout<<"\n";
vector<array<int,3>>op;
int q;
cin>>q;
while(q--){
int l,r,x;
cin>>l>>r>>x;
op.push_back({l,r,x});
c.modify(1,l,r,x);
if(c.find1(1,0)>c.find2(1,0)){
for(auto [u,v,m]:op) ans.modify(1,u,v,m),c.modify(1,u,v,-m);
op.clear();
}
// for(int i=1;i<=n;i++) cout<<ans.query(1,i,i).minv<<" ";
// cout<<"\n";
}
for(int i=1;i<=n;i++) cout<<ans.query(1,i,i).minv<<" ";
cout<<"\n";
}
int main()
{
ios::sync_with_stdio(false);
cin.tie(0),cout.tie(0);
int T=1;
cin>>T;
while(T--) solve();
return 0;
}