CF1648 [D] Serious Business
sim_sugar
·
·
个人记录
能直接建边跑最长路吗。
然后源点 $S \to \forall i : pre1_i$，$\forall i \to T : suf3_i$，求 $S \to T$ 的最长路。
很优秀啊，唯一的问题是跑不了，因为有负权边。用 $\text{SPFA}$ 肯定炸。
那继续想 $\text{dp}$，那想不出来，于是贺了贺。（？？？？）
***
Key：找到最优方案存在的贪心策略，以此去掉直接 $dp$ 的时候不好处理的部分，然后 $dp$ 解决一般部分，枚举解决特殊部分。
一开始 $\text{dp}$ 想了几个世纪哼哼啊啊啊啊啊，但是没往加强限制上面想（“走到 $i$ 右端点为 $r$” $\to$ “走到 $i$ 且钦定 $i$ 就是右端点”），以后遇到怎么都 $\text{dp}$ 不出来的可以考虑找性质然后 **加强状态的约束**。
最优方案是走满除了最右边一条线段之外的所有线段的覆盖，然后再走最后一条的某一段。
先假设每条线段都走满，然后再枚举最后一条线段拼答案。
那么 $dp$ 的时候我们就不需要在意右端点了，因为当前所在的位置就是右端点。
设 $f_i$ 表示从 $1,1$ 走到 $2,i$ 的最大值，
$$
f_{i} = \max_{r_k=i}(\max_{j=l_k}^{i}\max(pre1_j,f_{j-1})-sum_{j-1}-v_k+sum_i)
$$
然后这个东西就直接线段树做， `vector` 存一下 $r_k = i$ 的线段，每个线段只会被算一次，枚举每条线段，是一个后缀查最大值的操作，这个可以用 $\text{BIT}$ 换了，少写个线段树。
枚举最后一段，那么问题形式是 $-v_i+\max_{l_i-1 \le x \le y \le r_i} f_x-sum_x+sum_y+suf3_y$，放到线段树上，可以考虑维护区间 $f_i-sum_i$ 的最大值，$sum_y+suf3_y$ 的最大值，答案的值，然后合并的时候用个结构体更新就行了。
同时还需要特判一下只有最后一条线段的情况（只选一条），线段树上多维护一个 $\max_{l_i \le x \le y \le r_i} pre1_x-sum_{x-1}+sum_y+suf3_y$ 即可，注意这里查询区间的区别。
然后你就做完了。。。
```cpp
#define ri register int
#define ll long long
#define lowbit(x) (x&-x)
const int N = 500003; const ll oo = 1e17;
int n,m,a[N]; ll pre1[N],suf3[N],sum[N],bit[N],f[N],res=-oo;
struct ope{ int l,r,v; }b[N]; vector<ope> vec[N];
inline void Mdf(int x,ll d){ while(x<=n) bit[x]=max(bit[x],d),x+=lowbit(x); }
inline ll Qry(int x,ll t=-oo){ while(x) t=max(t,bit[x]),x-=lowbit(x); return t; }
struct Data{
ll lef,rig,val; Data(){} Data(ll A,ll B,ll C):lef(A),rig(B),val(C){}
inline Data operator +(const Data &rhs){ return Data(max(lef,rhs.lef),max(rig,rhs.rig),max({val,rhs.val,lef+rhs.rig})); }
}val[2][N<<2];
inline void Bld(int u,int l,int r){
if(l==r){
val[0][u]=Data(f[l]-sum[l],sum[l]+suf3[l],f[l]+suf3[l]),
val[1][u]=Data(pre1[l]-sum[l-1],sum[l]+suf3[l],pre1[l]+a[l]+suf3[l]); return;
} int mid=l+r>>1; Bld(u<<1,l,mid),Bld(u<<1|1,mid+1,r);
val[0][u]=val[0][u<<1]+val[0][u<<1|1],val[1][u]=val[1][u<<1]+val[1][u<<1|1];
//printf("%d[%d , %d] : %lld %lld %lld\n",u,l,r,val[u].lef,val[u].rig,val[u].val);
}
inline Data Que(int u,int l,int r,int L,int R,int i){
Data t(-oo,-oo,-oo); if(L>R) return t; if(l>=L&&r<=R) return val[i][u]; int mid=l+r>>1;
if(L<=mid) t=Que(u<<1,l,mid,L,R,i); if(R>mid) t=t+Que(u<<1|1,mid+1,r,L,R,i); return t;
}
main(){
rd(n),rd(m),bit[0]=f[0]=-oo;
for(ri i=1;i<=n;++i) rd(pre1[i]),pre1[i]+=pre1[i-1],bit[i]=-oo;
for(ri i=1;i<=n;++i) rd(a[i]),sum[i]=sum[i-1]+a[i];
for(ri i=1;i<=n;++i) rd(suf3[i]),f[i]=-oo;
for(ri i=n;i>=1;--i) suf3[i]+=suf3[i+1];
for(ri i=1;i<=m;++i) rd(b[i].l),rd(b[i].r),rd(b[i].v),vec[b[i].r].push_back(b[i]);
for(ri i=1;i<=n;++i){ // 你应该把没有 f[i] 的地方插一个 pre[i] 进去 否则 x 作为第一个线段的情况统计不全
Mdf(n-i+1,max(f[i-1],pre1[i])-sum[i-1]);
ll Maxx=-oo; for(auto t:vec[i])
Maxx=max(Maxx,Qry(n-t.l+1)-t.v+sum[i]);
f[i]=Maxx,res=max(res,f[i]+suf3[i]);
} Bld(1,1,n);
for(ri i=1;i<=m;++i){
const int L = b[i].l, R = b[i].r;
Data t=Que(1,1,n,max(L-1,1),R,0),t2=Que(1,1,n,L,R,1);
res=max(res,max(t.val,t2.val)-b[i].v);
} writeln(res);
}
```