Codeforces Round 905 div2 F题

记答案为\(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;
}