题目
长为n(n<=5e5)的数组a，第i个数ai(-1e9<=ai<=1e9)
q(q<=5e5)次操作，每次选择一个区间[l,r]，对这个区间加x(-1e9<=x<=1e9)
求序列操作前及第[1,q]次操作后，这q+1次对应的序列中，
历史最小字典序是哪个序列，输出序列
实际为t(t<=5e5)组样例，sumn和sumq均不超过5e5
思路来源
夏老师代码
HHU_zZhu代码
题解1（在线）
在线就是直接考虑保留第几次操作后是最优答案
考虑已经有一个最优答案，怎么替换成一个更优的答案，
肯定是最优答案，从某个前缀位置开始，有一个单点减，使这个点变得更小了
那区间减也可以维护成若干个差分，
如果若干次操作后，差分的第一个位置是一个单点减，说明是可以替换成更优的答案
所以map维护区间差分的位置，把map上差分为0的项实时抹掉，
去判断第一个差分非0的最左项是正还是负的，是负的说明可以保留，更新答案
题解2（离线）
扫描线思想， 把[0,q]这q+1个时间戳拍到线段树上，让这q+1个位置同时从第一个位置开始比
n个位置，q个时刻，扫描线，增序扫n个位置，l加，r+1减
在扫描线区间内的位置，即被若干次修改覆盖，
在某个时间区间对应+x，另一个时间区间对应-y，...，
保留区间加对应的最小的那个时间区间
每个修改是有时间后效性的，也就是第i时刻的修改，会改[i,q]时间的值
只关注最小值即可，删掉不可能成为最小值的时刻，这些时刻一定是在前缀某个位置处变大了
维护区间最小值，删掉的置成INF，保证经过后面的操作这些也不可能成为最小即可
代码1（在线）
//#include <bits/stdc++.h>
#include<iostream>
#include<cstdio>
#include<vector>
#include<map>
using namespace std;
#define rep(i,a,b) for(int i=(a);i<=(b);++i)
#define per(i,a,b) for(int i=(a);i>=(b);--i)
typedef long long ll;
typedef double db;
typedef pair<int,int> P;
#define fi first
#define se second
#define pb push_back
#define dbg(x) cerr<<(#x)<<":"<<x<<" ";
#define dbg2(x) cerr<<(#x)<<":"<<x<<endl;
#define SZ(a) (int)(a.size())
#define sci(a) scanf("%d",&(a))
#define pt(a) printf("%d",a);
#define pte(a) printf("%d\n",a)
#define ptlle(a) printf("%lld\n",a)
#define debug(...) fprintf(stderr, __VA_ARGS__)
using namespace std;
const int N=5e5+10;
map<int,ll>mp;
array<int,3>op[N];
int t,n,q,pos,a[N],l,r,w;
ll add[N];
int main(){
sci(t);
while(t--){
sci(n);
mp.clear();
pos=0;
rep(i,1,n){
sci(a[i]);
add[i]=0;
}
sci(q);
rep(i,1,q){
sci(l),sci(r),sci(w);
op[i]={l,r,w};
mp[l]+=w;
mp[r+1]-=w;
if(!mp[l])mp.erase(mp.find(l));
if(!mp[r+1])mp.erase(mp.find(r+1));
if(mp.size() && mp.begin()->se<0){
pos=i;
mp.clear();
}
}
rep(i,1,pos){
auto [l,r,w]=op[i];
add[l]+=w;
add[r+1]-=w;
}
rep(i,1,n){
add[i]+=add[i-1];
}
rep(i,1,n){
printf("%lld%c",a[i]+add[i]," \n"[i==n]);
}
}
return 0;
}代码2（离线）
//#include <bits/stdc++.h>
#include<iostream>
#include<cstdio>
#include<vector>
using namespace std;
#define rep(i,a,b) for(int i=(a);i<=(b);++i)
#define per(i,a,b) for(int i=(a);i>=(b);--i)
typedef long long ll;
typedef double db;
typedef pair<int,int> P;
#define fi first
#define se second
#define pb push_back
#define dbg(x) cerr<<(#x)<<":"<<x<<" ";
#define dbg2(x) cerr<<(#x)<<":"<<x<<endl;
#define SZ(a) (int)(a.size())
#define sci(a) scanf("%d",&(a))
#define pt(a) printf("%d",a);
#define pte(a) printf("%d\n",a)
#define ptlle(a) printf("%lld\n",a)
#define debug(...) fprintf(stderr, __VA_ARGS__)
using namespace std;
const int N=5e5+10;
const ll INF=1e18,INF2=1e17;
typedef pair<int,int> P;
struct segtree{
int n;
struct node{int l,r;ll c,mn,mx;}e[N<<2];
#define l(p) e[p].l
#define r(p) e[p].r
#define mn(p) e[p].mn
#define mx(p) e[p].mx
#define c(p) e[p].c
void up(int p){
mn(p)=min(mn(p<<1),mn(p<<1|1));
mx(p)=max(mx(p<<1),mx(p<<1|1));
}
void bld(int p,int l,int r){
l(p)=l;r(p)=r;
mn(p)=mx(p)=c(p)=0;
if(l==r){return;}
int mid=l+r>>1;
bld(p<<1,l,mid);bld(p<<1|1,mid+1,r);
up(p);
}
void psd(int p){
if(c(p)){
mn(p<<1)+=c(p);
mx(p<<1)+=c(p);
c(p<<1)+=c(p);
mn(p<<1|1)+=c(p);
mx(p<<1|1)+=c(p);
c(p<<1|1)+=c(p);
c(p)=0;
}
}
void init(int _n){n=_n;bld(1,0,n);}
void add(int p,int ql,int qr,int v){
if(mn(p)>=INF2)return;
if(ql<=l(p)&&r(p)<=qr){
mn(p)+=v;
mx(p)+=v;
c(p)+=v;
return;
}
psd(p);
int mid=l(p)+r(p)>>1;
if(ql<=mid)add(p<<1,ql,qr,v);
if(qr>mid)add(p<<1|1,ql,qr,v);
up(p);
}
void del(int p,int ql,int qr,ll v){// 每一个要删的递归到底，均摊O(nlogn)
if(mn(p)>=INF2)return;
if(l(p)==r(p) && mx(p)>v){
mn(p)=INF;
mx(p)=-INF;
return;
}
psd(p);
int mid=l(p)+r(p)>>1;
if(ql<=mid && mx(p<<1)>v)del(p<<1,ql,qr,v);// 左区间有要删的
if(qr>mid && mx(p<<1|1)>v)del(p<<1|1,ql,qr,v);// 右区间又要删的
up(p);
}
ll ask(int p,int ql,int qr){
if(mn(p)>=INF2)return INF2;
if(ql<=l(p)&&r(p)<=qr)return mn(p);
int mid=l(p)+r(p)>>1;
ll res=INF2;
psd(p);
if(ql<=mid)res=min(res,ask(p<<1,ql,qr));
if(qr>mid)res=min(res,ask(p<<1|1,ql,qr));
return res;
}
}seg;
int t,n,a[N],q,l,r,w;
vector<P>add[N],del[N];
ll ans[N];
int main(){
sci(t);
while(t--){
sci(n);
rep(i,1,n){
sci(a[i]);
add[i].clear();
del[i].clear();
}
sci(q);
seg.init(q);
rep(i,1,q){
sci(l),sci(r),sci(w);
add[l].pb(P(i,w));
del[r].pb(P(i,w));
}
rep(i,1,n){
for(auto &x:add[i]){
//printf("i:%d x.fi:%d x.se:%d\n",i,x.fi,x.se);
seg.add(1,x.fi,q,x.se);
}
ll mn=seg.ask(1,0,q);
ans[i]=mn+a[i];
seg.del(1,0,q,mn);
for(auto &x:del[i]){
seg.add(1,x.fi,q,-x.se);
}
}
rep(i,1,n){
printf("%lld%c",ans[i]," \n"[i==n]);
}
}
return 0;
}
