题目大意：一条数轴，每两点有一条边，带流量限制。从左往右扫描，你有一个变量 \(x\)（每次经过边时会对边取 \(\min\) 进行限制），每个点上会进行一定的权值改变，且改变后为负则失败。动态维护这个权值改变的量 \(a\)，问你初始权值一定时要多少流量限制的增加才能让任务不失败。
人的本质是复读机，下文参考了官方题解。
我们考虑怎么刻画这个最小代价，那么设 \(r_i\) 为通过 \(i\) 至少需要保留的权值。显然，此时 \(r_n=0,r_{i-1}=\max(0,r_{i}-a_i)\)，也就是保持每次都至少有 \(0\) 能走，且之前的代价不加。注意到 \(a\) 有负数，那么 \(r\) 也不一定全部都是 \(0\)。此时，若 \(k 那么就是所有边开到 \(+\infty\) 都无能为力，则答案恒定为 \(-1\)。反之，我们考虑最小化总代价。
注意到，我们每次只需要保留当前权值 \(\ge r_i\) 即可，那么我们要改的东西就是所有会让 \(r_i\) 低于预期的位置，也就是 \(cost=\sum_{i=1}^n \max(0,r_i-b_i)\)。如果一条边不会使得权值低于极限值，那么不修改一定是不劣的，即答案与 \(k\) 无关，这是一个比较重要的性质。
那么我们就需要找到一个办法动态维护这个 \(r\)，因为 \(a\) 是动态修改的。注意到 \(a\) 只可能动态加，且 \([x,n]\) 处的值与 \(a_x\) 无关，那么我们只需要考虑 \([0,x)\) 处的 \(r\) 会因此而减小。考虑维护这个减少量，设为 \(d_x\)。源发点 \(x-1\) 显然有 \(d_{x-1}=\min(y,r_{x-1})\)，代表着至多减到 \(0\) 的性质。然后传递就是按照 \(r\) 的定义去传递，\(d_i=\min(d_{i+1},r_i)\) 代表减少是固定的，但是每次不会减到 \(<0\)。
但是这样写会有一个问题就是 \(d\) 在每一个位置都不一样。那么我们就直接按照前缀全部减少 \(d_{x-1}\) 的方法来实现，每次如果区间 \(r\) 最小值 \(\ge d\) 就说明整段可减，否则分段处理。注意到右边减完之后 \(d\) 就会被削弱，那么此时再对这个削弱传入左子树做计算，即可。这个东西复杂度应该没有多一个 \(\log\)，因为操作只有正数，此时每个点 \(r\) 都是在变成 \(0\) 的过程，每次我们都只会让每个数变成 \(0\) 至多一次，那么复杂度均摊看下来这部分是 \(\mathcal O(n\log n)\) 的。
然后我们除了维护 \(r\) 还要动态维护 \(w_i=\max(0,r_i-b_i)\) 的和，那么此时整段 \(r\to \max(r-d,0)\iff w\to \max(w-d,0)\)。此时这个东西类似 \(r\) 去维护就可以了。怎么感觉越写越大份。具体的：
- 维护区间的正数个数，最小（最大）正数及和。
- \(d<\) 最小正数时等价于区间减。
- \(d\ge\) 最大正数时等价于区间清 \(0\)。
- 反之类似 \(r\) 的维护一样递归去做，复杂度分析和 \(r\) 是一样的，均摊 \(\mathcal O(n\log n)\)。
这样分析下来本题的总时间复杂度就是 \(\mathcal O((n+q)\log n)\) qwq。注意 \(w\) 和用 __int128 来存。
对于这种区间加一个带左区间贡献的东西我们就可以用这样的方式来维护，学到了 qwq（上次见到这种东西还是在楼房重建）。
细节比较多，注意 tag 的实际意义以及对应的维护量。
::::success[Code]
#define FileIO
#include
using namespace std;
#define ll long long
#define _l __int128
#define fi first
#define se second
#define il inline
bool stMem; double stT=clock();
const int N=3e5+10;
const ll P=998244353;
il ll qp(ll a,ll b=P-2){ll res=1;for(;b;b>>=1,a=(a*a)%P) if(b&1) res=(res*a)%P;return res;
}
// ---------------------------------------------------- //
int test_id;
ll n,q,a[N],b[N];
ll R[N], W[N]; // 原始需要处理的 r 和 w
namespace tree_w{ll cn[N<<2], mn[N<<2], mx[N<<2], dt[N<<2]; _l su[N<<2];bool ct[N<<2];il void pushup(int p){cn[p]=cn[p<<1]+cn[p<<1|1];mn[p]=min(mn[p<<1],mn[p<<1|1]);mx[p]=max(mx[p<<1],mx[p<<1|1]);su[p]=su[p<<1]+su[p<<1|1];}void build(int p,int l,int r){dt[p]=ct[p]=0;if(l==r){if(W[l]) mn[p]=mx[p]=W[l];else mn[p]=+1e10, mx[p]=-1e10;su[p]=W[l]; cn[p]=(W[l]>0);return;}int mid=(l+r)>>1;build(p<<1,l,mid);build(p<<1|1,mid+1,r);pushup(p); }il void pushdown(int p){if(dt[p]){ // 注意使用这个的时候 dt 一定小于最小正数，所以不对 cn 进行修改if(cn[p<<1]){dt[p<<1]+=dt[p]; mn[p<<1]-=dt[p]; mx[p<<1]-=dt[p];su[p<<1]-=(_l)dt[p]*cn[p<<1];}if(cn[p<<1|1]){dt[p<<1|1]+=dt[p]; mn[p<<1|1]-=dt[p]; mx[p<<1|1]-=dt[p];su[p<<1|1]-=(_l)dt[p]*cn[p<<1|1]; }dt[p]=0;}if(ct[p]){dt[p<<1]=0; mn[p<<1]=1e10; mx[p<<1]=-1e10; su[p<<1]=0; ct[p<<1]=1; cn[p<<1]=0;dt[p<<1|1]=0; mn[p<<1|1]=1e10; mx[p<<1|1]=-1e10; su[p<<1|1]=0; ct[p<<1|1]=1; cn[p<<1|1]=0;ct[p]=0;}}void update(int p,int l,int r,int ql,int qr,ll uv){if(ql>qr) return;if(ql<=l&&r<=qr){if(uv=mx[p]){ su[p]=0; mn[p]=1e10; mx[p]=-1e10; dt[p]=0; ct[p]=1; cn[p]=0; return; }}pushdown(p);int mid=(l+r)>>1;if(ql<=mid) update(p<<1,l,mid,ql,qr,uv);if(qr>mid) update(p<<1|1,mid+1,r,ql,qr,uv);pushup(p);}
}
namespace tree_r{ll mn[N<<2], dt[N<<2];il void pushup(int p){ mn[p]=min(mn[p<<1],mn[p<<1|1]); }void build(int p,int l,int r){dt[p]=0;if(l==r){ mn[p]=R[l]; return; }int mid=(l+r)>>1;build(p<<1,l,mid);build(p<<1|1,mid+1,r);pushup(p);} il void pushdown(int p){if(!dt[p]) return;dt[p<<1]+=dt[p]; mn[p<<1]-=dt[p];dt[p<<1|1]+=dt[p]; mn[p<<1|1]-=dt[p];dt[p]=0;}il void sync_w(ll l,ll r,ll uv){ l=max(l,1ll), r=min(r,n-1); if(l<=r) tree_w::update(1,1,n-1,l,r,uv); }ll update(int p,int l,int r,int ql,int qr,ll uv){if(l==r&&mn[p]=uv){ sync_w(l,r,uv); dt[p]+=uv; mn[p]-=uv; return uv; }pushdown(p);int mid=(l+r)>>1; ll weaken=uv;if(qr>mid) weaken=update(p<<1|1,mid+1,r,ql,qr,uv);if(ql<=mid&&weaken) weaken=update(p<<1,l,mid,ql,qr,weaken);pushup(p);return weaken;}ll query_one(int p,int l,int r,int ps){if(l==r){ return mn[p]; }pushdown(p);int mid=(l+r)>>1;if(ps<=mid) return query_one(p<<1,l,mid,ps);return query_one(p<<1|1,mid+1,r,ps);}
}
il void write(_l x){string res="";if(x==0){ cout<<"0\n"; return; }while(x){ res+=char(x%10+'0'); x/=10; }reverse(res.begin(),res.end());cout<>n>>q;for(int i=1;i<=n;++i) cin>>a[i];for(int i=1;i>b[i];R[n]=0;for(int i=n;i;--i) R[i-1]=max(0ll,R[i]-a[i]);for(int i=1;i>op>>x;if(op==1){cin>>y;ll ori_d=min(y,tree_r::query_one(1,0,n,x-1));tree_r::update(1,0,n,0,x-1,ori_d);}else{if(x>test_id>>T;while(T--) solve();cerr<<"\n";cerr<<"[Info] End Of Running. \n";cerr<<" Time Used : "<<(clock()-stT)/CLOCKS_PER_SEC*1000.00<<" ms\n";cerr<<" Memory Used : "<<(&stMem-&edMem)/1048576.00<<" Mib\n";return 0;
}::::
https://www.luogu.com.cn/article/wwytygg0