而不是我会的，没看凸性，感觉不是很可做就没去看了。

首先凸性的本质是严格递增且增量越来越大。那么考虑 \((i,j)\to (i+1,j)\) 的本质是后续所有移动（数值上）获得增量 \(c_{i+1}=a_{i+1}-a_i\)，则贡献就是 \(c_{i+1}(n+m-i-j)\)；同理，考虑 \((i,j)\to (i,j+1)\) 的本质是后续所有移动获得增量 \(d_{j+1}=b_{j+1}-b_j\)。则贡献就是 \(d_{j+1}(n+m-i-j)\)。

使用 \(c,d\) 替换 \(a,b\)。注意到 \(1\) 元素只有开头会取到。你会发现，每次我们都需要选择 \(c_{i}\) 与 \(d_j\) 各一次，故我们考虑最优决策 \(c_{2\dots n}\) 与 \(d_{2\dots m}\)。每走一步，\((n+m-i-j)\) 就变小 \(1\)，所以最优解就是 \(c_i,d_j\) 混合后按顺序取到。

根据这一点考虑 \((n+m-i-j)\iff (n-i+m-j)\)，则对每一个位置的元素拆贡献，那么就是 \(c_i> x\) 的数的个数加上 \(d_j> x\) 的数的个数 \(+1\)。那么直接维护 \(c_1,d_1,\sum_{i=2}^n c_i(n-i)\) 以及 \(\sum_{i=1}^m d_i(m-i)\)。暴力查找 \(c_i\) 会插入 \(d_i\) 的位置，然后直接处理。

时间复杂度 \(\mathcal O(nm\log m)\)。

人类的本质是复读机，这里要说一些不一样的道理，不然这篇题解就是滚木作用的。稍微讲一下具体维护吧。对于这个问题，你会发现 \(c,d\) 之间的关系非常混乱，我们将其分为三类：

  • \(c_1,d_1\)：单独计算，单独贡献。
  • \(c\to c,d\to d\)：也就是所有 \(c,d\) 内部偏序对所产生的贡献。其只会产生 \((n-i+1)c_i\) 以及 \((m-i+1)d_i\) 的贡献。后续直接加产生的贡献就是 \(d\cdot F(n-i+1)\)（\(F(x)=\frac{x(x+1)}{2}\)）。
  • 两者交叉。显然我们 \(c\) 只有 \(100\)，每轮找到第一个 \(\ge c_i\) 的 \(d\)，其左侧 \(d\) 元素显然会有一个贡献（\(d\to c\)）。反之，其右侧的全部元素贡献都是由 \(c\) 来的（\(c\to d\)）。

那么我们写一个区间加、区间最大值、区间 \(\ge x\) 且其左侧和的线段树即可。

::::success[Code]

#define FileIO
#include
using namespace std;
#define ll long long
#define fi first
#define se second
#define il inline
bool stMem; double stT=clock();
const int N=1e5+10, M=1e2+10, S=2e5+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 n,m,q; ll a[N],b[N],c[N],d[N];
ll su[S<<2], mx[S<<2], tg[S<<2];
il void pushup(int p){su[p]=su[p<<1]+su[p<<1|1];mx[p]=max(mx[p<<1],mx[p<<1|1]);
}
void build(int p,int l,int r){if(l==r){su[p]=d[l];mx[p]=d[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,int l,int r){if(!tg[p]) return;int mid=(l+r)>>1;mx[p<<1]+=tg[p];su[p<<1]+=tg[p]*(mid-l+1);tg[p<<1]+=tg[p];mx[p<<1|1]+=tg[p];su[p<<1|1]+=tg[p]*(r-mid);tg[p<<1|1]+=tg[p];tg[p]=0;
}
void update(int p,int l,int r,int ql,int qr,ll uv){if(ql<=l&&r<=qr){mx[p]+=uv;su[p]+=uv*(r-l+1);tg[p]+=uv;return;}pushdown(p,l,r);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);
}
pair binary(int p,int l,int r,int x,ll ls){if(l==r){if(mx[p]>=x) return {l,ls};return {m+1,ls+su[p]};}pushdown(p,l,r);int mid=(l+r)>>1;if(mx[p<<1]>=x) return binary(p<<1,l,mid,x,ls);return binary(p<<1|1,mid+1,r,x,ls+su[p<<1]);
}
il ll F(ll x){ return x*(x+1)/2; }
// ---------------------------------------------------- //
il void solve(){cin>>n>>m>>q;for(int i=1;i<=n;++i) cin>>a[i], c[i]=a[i]-a[i-1];for(int i=1;i<=m;++i) cin>>b[i], d[i]=b[i]-b[i-1];ll self_cost=0;for(int i=2;i<=n;++i) self_cost+=(n-i+1)*c[i];for(int i=2;i<=m;++i) self_cost+=(m-i+1)*d[i];build(1,2,m);while(q--){int op; ll k,dt; cin>>op>>k>>dt;if(op==1){int le=n-k+1;if(le==1) c[1]+=dt, ++le;for(int i=le;i<=n;++i) c[i]+=dt;self_cost+=F(n-le+1)*dt;}else{int le=m-k+1;if(le==1) d[1]+=dt, ++le;update(1,2,m,le,m,dt);self_cost+=F(m-le+1)*dt;			}ll ans=(n+m-1)*(c[1]+d[1])+self_cost;for(int i=2;i<=n;++i){auto res=binary(1,2,m,c[i],0);ans+=res.se+(m-res.fi+1)*c[i];}cout<>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/abvxldiz