CF1648D 简单清楚的做法
我自己做这题没做出来，看网上题解都有点难看懂，自己搞一个
前置知识
线段树维护： 对于两个序列 \(a,b\)，给定 \(l,r\)，询问：\(\max (a_i+b_j),l\le i\le j\le r\)。
区间维护： \(a\) 的最大值，\(b\) 的最大值，区间答案。
考虑 \(i,j\)，如果都在两边，调用左右两边的ans，否则就是左边 \(a\) 最大值 \(+\) 右边 \(b\) 最大值。
正片
显然我们只需要关心什么时候进第二行和什么时候出第二行即可。
设 \(f(i)\) 表示走到第二行的 \(i\) 位置，算上解锁区间的代价，最大的收益。答案为 \(\max(f(i)+sum3(i…n))\)。
（注：后面用 \(sum(l…r)\) 表示区间和，\(s(i)\) 表示前缀和，\(s_1,s_2,s_3\) 表示1/2/3行）（均为前缀和，没有后缀和）
考虑 \(f(i)\) 的转移。注意到 \(i\) 这个位置一定有一个区间覆盖到它。考虑覆盖 \(i\) 的区间 \([l,r],cost=w\)。
- 转移case1 它不是第一个解锁区间
如果它不是第一个解锁的区间，那我们可以直接从 \(f(l-1)\) 转移过来，而不需要枚举 \(j\ge l-1\) 转移。
原因是不管 \(j\) 取在哪，最后的总和一定都是：第二行选择的区间和 \(-\) 解锁区间的代价和。因此没必要枚举 \(j\) ，直接取 \(l-1\) 就行了。
这个情况的转移为 \(f(i) \leftarrow f(l-1)+sum2(l…i)-w\)。
- 转移case2 它是第一个区间
这回没法直接继承了，枚举 \(j\) 是必要的。枚举 \(l\le j\le i\) 表示从 \(j\) 位置进入第二行。
这个情况的转移为 \(f(i)\leftarrow s_1(j)+sum2(j…i)-w\)。
- 边界
注意到我们不需要给转移2设置边界，它本身就相当于边界（与其说是转移，它更像是在求一个式子的值，因为它并不依赖于 \(f\)）。而转移 \(1\) 则强制要求当前的 \([l,r]\) 不是第一个区间，从而 \(l=1\) 从 \(0\) 转移过来是不合法的。因此我们要令 \(f(0)=-\infin\)。
注： \(a\leftarrow b\) 表示用 \(b\) 更新 \(a\)，这里是取 \(\max\)。
它的复杂度显然不对，考虑优化。
首先我们显然可以用扫描线相关技巧动态维护当前包含 \(i\) 的区间 \([l,r],cost=w\) 的集合。就是枚举到 \(i\) 时，加入 \(l=i\) 的区间，删除 \(r+1=i\) 的区间。
- 优化转移1
变成 \(f(l-1)+s_2(i)-s_2(l-1)-w\)。要么只和 \(i\) 有关，要么只和 \(l\) 有关。
我们要求 \(\max\) 并且支持加入和删除，用 multiset 维护所有包含 \(i\) 的区间中， \(f(l-1)-s_2(l-1)-w\) 的集合即可。
- 优化转移2
变成 \(s_1(j)+s_2(i)-s_2(j-1)-w\)。其中 \(1\le l\le j\le i\)。
对于同一个 \(l\)，我们只关注 \(w\) 的最小值（即 \(-w\) 最大值）。把项提取一下，设 \(A(l)=\max(-w),r\ge i\)，\(B(j)=s_1(j)-s_2(j-1)\)。它相当于 \(\max(A(l)+B(j)),1\le l\le j\le i\)。
对于每个 \(l\) 维护一个 multiset 表示所有 \(\ge i\) 的 \(r\) 中， \(-w\) 的集合。当我们加入/删除区间时，先更新这个multiset，然后这里的最大值就是新的 \(A(l)\)，在线段树上单点修改 \(A(l)\) 更新即可。注意 \(B\) 不需要更新。
然后 \(f(i)\) 就是 \(s_2(i)\) 加上线段树上 \([1,i]\) 的答案。
这样的话操作之后改multiset和线段树，都是一个 \(\log\)。
复杂度 \(O((n+q)\log n)\)。
代码
// 注：NNF 表示 -INF （Negative INF）
#include<bits/stdc++.h>
using namespace std;
#define N 1000006
#define int long long
#define F(i,l,r) for(int i=(l);i<=(r);++i)
#define D(i,r,l) for(int i=(r);i>=(l);--i)
#define MEM(x,a) memset(x,a,sizeof(x))
int I(){int x=0,f=0;char c=getchar(); while(!isdigit(c))f=(c=='-'),c=getchar(); while(isdigit(c))x=x*10+c-'0',c=getchar(); return f?-x:x;}
#define vi vector<int>
#define eb emplace_back
#define sz(x) ((int)x.size())
#define al(x) x.begin(),x.end()
#define pii pair<int,int>
#define fi first
#define se second
#define lwrb lower_bound
#define uprb upper_bound
#define mset multiset<int>
#define t3 tuple<int,int,int>
const int INF=1e18,NNF=-1e18;
void del1(mset&s,int x){auto it=s.find(x);if(it!=s.end())s.erase(it);}
int gmx(mset&s) {return *prev(s.end());}
int n,m; int a[4][N],s[4][N];
vector<t3> rg;
struct nd{int l,r,k;}r[N];
vi ad[N],dc[N];
mset rec1,rec2[N];
int A[N],B[N];
struct info{int ma,mb,mx;};
info operator+(info a,info b){return (info){max(a.ma,b.ma),max(a.mb,b.mb),max({a.mx,b.mx,a.ma+b.mb})};}
struct SegT
{
#define ls u<<1
#define rs u<<1|1
#define ll ls,L,o
#define rr rs,o+1,R
info a[N];
void up(int u) {a[u]=a[ls]+a[rs];}
void build(int u=1,int L=1,int R=n)
{
if(L==R) {a[u]=(info){A[L],B[L],A[L]+B[L]}; return;}
int o=(L+R)>>1; build(ll);build(rr);up(u);
}
void ca(int p,int x,int u=1,int L=1,int R=n)
{
if(L==R) {a[u].ma=x; a[u].mx=a[u].ma+a[u].mb; return;}
int o=(L+R)>>1;
if(p<=o)ca(p,x,ll); else ca(p,x,rr); up(u);
}
info qr(int l,int r,int u=1,int L=1,int R=n)
{
if(l<=L && R<=r)
{
return a[u];
}
int o=(L+R)>>1;
if(r<=o)return qr(l,r,ll); if(o<l) return qr(l,r,rr);
return qr(l,r,ll)+qr(l,r,rr);
}
}T;
int f[N];
void flandre()
{
n=I(),m=I();
F(i,1,3)
{
F(j,1,n) a[i][j]=I();
F(j,1,n) s[i][j]=s[i][j-1]+a[i][j];
}
F(i,1,m) {int l=I(),r=I(),w=I(); rg.eb(l,r,w);}
F(i,0,sz(rg)-1) {auto [l,r,w]=rg[i]; ad[l].eb(i); dc[r+1].eb(i);}
rec1.insert(NNF); F(i,1,n) rec2[i].insert(NNF);
F(i,1,n) A[i]=gmx(rec2[i]),B[i]=s[1][i]-s[2][i-1];
T.build(); f[0]=NNF;
F(i,1,n)
{
for(auto x:ad[i])
{
auto [l,r,w]=rg[x];
rec1.insert(f[l-1]-s[2][l-1]-w);
rec2[l].insert(-w);
A[l]=gmx(rec2[l]); T.ca(l,A[l]);
}
for(auto x:dc[i])
{
auto [l,r,w]=rg[x];
del1(rec1,f[l-1]-s[2][l-1]-w);
del1(rec2[l],-w);
A[l]=gmx(rec2[l]); T.ca(l,A[l]);
}
f[i]=gmx(rec1)+s[2][i];
f[i]=max(f[i],T.qr(1,i).mx+s[2][i]);
}
int ans=NNF;
F(i,1,n) ans=max(ans,f[i]+s[3][n]-s[3][i-1]);
printf("%lld\n",ans);
}
#undef int
int main()
{
int t=1;
while(t--)flandre();
return 0;
}
原文地址：http://www.cnblogs.com/LightningUZ/p/16900913.html
