题目链接
题目解法
先考虑朴素的 \(dp\)
不难发现有两个断点 \(x,y\) 是重要的，即 \([1,x]\) 在第 \(1\) 行，\([x,y]\) 在第 \(2\) 行，\([y,n]\) 在第 \(3\) 行
不妨枚举断点 \(y\)，然后统计最优的 \(x\)
令 \(f_i\) 表示断点在 \(i\) 的最大收益（只计算第 \(1\) 行和第 \(2\) 行）
答案即为 \(\max f_i+sumsuf_{3,i}\)
考虑转移，枚举 \(i\) 被覆盖的区间，假设为 \([l,r,k](l\le i\le r)\)：
- 只用当前区间覆盖
\(f_i=\max\limits_{j=l}^isumpre_{1,j}-sumpre_{1,j-1}+sumpre_{1,i}-k\) - 同时用其他区间覆盖
不难发现，最优的情况一定是 \(f_i=f_{l-1}+sumpre_{1,i}-k\)
发现 \(sumpre_{1,i}\) 是定值，可以移出转移
考虑线段树优化
情况 \(2\) 是好优化的，直接在 \(i=l\) 时枚举区间，然后线段树上区间求 \(\max\) 即可
情况 \(1\) 比较复杂，我们考虑在 \(r\) 处记录结果（因为要满足 \(i\le r\) 的限制），然后从前往后更新后缀即可，有些难懂
需要记录的东西有区间 \(\max\)，区间 \(\min k\)，和下传的 \(tag\)
时间复杂度 \(O(n\log n)\)
#include <bits/stdc++.h>
#define F(i,x,y) for(int i=(x);i<=(y);i++)
#define DF(i,x,y) for(int i=(x);i>=(y);i--)
#define ms(x,y) memset(x,y,sizeof(x))
#define SZ(x) (int)x.size()-1
#define pb push_back
using namespace std;
typedef long long LL;
typedef unsigned long long ull;
typedef pair<int,int> pii;
template<typename T> void chkmax(T &x,T y){ x=max(x,y);}
template<typename T> void chkmin(T &x,T y){ x=min(x,y);}
inline int read(){
int FF=0,RR=1;
char ch=getchar();
for(;!isdigit(ch);ch=getchar()) if(ch=='-') RR=-1;
for(;isdigit(ch);ch=getchar()) FF=(FF<<1)+(FF<<3)+ch-48;
return FF*RR;
}
typedef long long LL;
const int N=500100;
const LL inf=1e15;
int n,m,a[3][N];
LL f[N],s[3][N];
vector<pii> cost[N];
struct Sgt1{
LL seg[N<<2];
void clear(){ F(i,1,n<<2) seg[i]=-inf;}
void modify(int l,int r,int x,int L,int R,LL val){
if(L<=l&&r<=R){ chkmax(seg[x],val);return;}
int mid=(l+r)>>1;
if(mid>=L) modify(l,mid,x<<1,L,R,val);
if(mid<R) modify(mid+1,r,x<<1^1,L,R,val);
}
LL query(int l,int r,int x,int pos){
if(l==r) return seg[x];
int mid=(l+r)>>1;
if(mid>=pos) return max(query(l,mid,x<<1,pos),seg[x]);
else return max(query(mid+1,r,x<<1^1,pos),seg[x]);
}
}sg1;
struct Sgt2{
LL seg[N<<2],rec[N<<2],mink[N<<2];
void clear(){ F(i,1,n<<2) seg[i]=-inf,rec[i]=-inf,mink[i]=inf;}
void pushdown(int x){
if(rec[x]!=-inf){
chkmax(seg[x<<1],rec[x]-mink[x<<1]),chkmax(seg[x<<1^1],rec[x]-mink[x<<1^1]);
chkmax(rec[x<<1],rec[x]),chkmax(rec[x<<1^1],rec[x]);
rec[x]=-inf;
}
}
void modify(int l,int r,int x,int pos,LL v,LL k){
if(l==r){ chkmax(seg[x],v),chkmin(mink[x],k);return;}
pushdown(x);
int mid=(l+r)>>1;
if(mid>=pos) modify(l,mid,x<<1,pos,v,k);
else modify(mid+1,r,x<<1^1,pos,v,k);
seg[x]=max(seg[x<<1],seg[x<<1^1]);
mink[x]=min(mink[x<<1],mink[x<<1^1]);
}
void update(int l,int r,int x,int lb,LL val){
if(r<lb) return;
if(l>=lb){ chkmax(seg[x],val-mink[x]),chkmax(rec[x],val);return;}
pushdown(x);
int mid=(l+r)>>1;
update(l,mid,x<<1,lb,val),update(mid+1,r,x<<1^1,lb,val);
seg[x]=max(seg[x<<1],seg[x<<1^1]);
}
LL query(int l,int r,int x,int lb){
if(r<lb) return -inf;
if(l>=lb) return seg[x];
pushdown(x);
int mid=(l+r)>>1;
return max(query(l,mid,x<<1,lb),query(mid+1,r,x<<1^1,lb));
}
}sg2;
int main(){
n=read(),m=read();
F(i,0,2) F(j,1,n) a[i][j]=read();
F(i,1,m){
int l=read(),r=read(),k=read();
cost[l].pb({r,k});
}
F(i,0,2) F(j,1,n) s[i][j]=s[i][j-1]+a[i][j];
F(i,0,n) f[i]=-inf;
sg1.clear(),sg2.clear();
F(i,1,n){
for(auto [r,k]:cost[i]) sg2.modify(1,n,1,r,s[0][i]-s[1][i-1]-k,k),sg1.modify(1,n,1,i,r,f[i-1]-k);
sg2.update(1,n,1,i,s[0][i]-s[1][i-1]);
f[i]=max(sg1.query(1,n,1,i),sg2.query(1,n,1,i));
}
LL ans=-inf;
F(i,1,n) chkmax(ans,s[2][n]-s[2][i-1]+f[i]+s[1][i]);
printf("%lld\n",ans);
fprintf(stderr,"%d ms\n",int(1e3*clock()/CLOCKS_PER_SEC));
return 0;
}