[数据结构与算法]【线段树】Serious Business（CF1648D）

正题

luogu
CF1648D

题目大意

有一个 3*n 的矩阵，1,3行没有行走限制，对于第2行，有m个区间，覆盖第 i 个区间有 $k_i$ 的代价，只有覆盖的位置才能走，让你从 (1,1) 走到 (3,n)（只能向下和向右走） ，答案为经过的每个点的权值之和减去代价之和，问你答案最大值

解题思路

可以把第2行的权值用前缀和计算，令 $A_i={\sum }_{j=1}^i{s}_{1,j}?{\sum }_{j=1}^{i?1}{s}_{2,j},B_i={\sum }_{j=i}^n{s}_{3,j}+{\sum }_{j=1}^i{s}_{2,j}$

答案就转化为了在第二行走一段路答案为 $A_{bg}+B_{ed}$，这个可以先按区间的左端点排序，然后再线段树上依次往后贡献即可

code

#include<vector>
#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
#define ll long long
#define N 500500
using namespace std;
ll n,m,sum,ans,X[N],Y[N],Z[N],a[4][N],b[N];
vector<ll>l[N];
const ll inf=1e18;
struct Tree
{
	#define ls x*2
	#define rs x*2+1
	ll s[N<<2],v[N<<2],lazy[N<<2],lazyy[N<<2];
	void push_up(ll x)
	{
		s[x]=max(s[ls],s[rs]);
		v[x]=max(v[ls],v[rs]);
		return;
	}
	void get(ll x,ll ad,ll an)
	{
		s[x]=max(s[x],max(v[x]-ad,an));
		lazy[x]=min(lazy[x],ad);
		lazyy[x]=max(lazyy[x],an);
		return;
	}
	void push_down(ll x)
	{
		get(ls,lazy[x],lazyy[x]);
		get(rs,lazy[x],max(lazyy[x],max(v[ls],s[ls])-lazy[x]));
		lazy[x]=inf;
		lazyy[x]=-inf;
		return;
	}
	void build(ll x,ll l,ll r)
	{
		s[x]=lazyy[x]=-inf;
		lazy[x]=inf;
		if(l==r){
			v[x]=b[l];
			return;
		}
		ll mid=l+r>>1;
		build(ls,l,mid);
		build(rs,mid+1,r);
		push_up(x);
		return;
	}
	ll change(ll x,ll L,ll R,ll l,ll r,ll ad,ll an)
	{
		if(L==l&&R==r){
			get(x,ad,an);
			return max(v[x],s[x]);
		}
		push_down(x);
		ll mid=L+R>>1,g;
		if(r<=mid)g=change(ls,L,mid,l,r,ad,an);
		else if(l>mid)g=change(rs,mid+1,R,l,r,ad,an);
		else{
			g=change(ls,L,mid,l,mid,ad,an);
			g=max(g,change(rs,mid+1,R,mid+1,r,ad,max(an,g-ad)));
		}
		push_up(x);
		return g;
	}
	ll ask(ll x,ll l,ll r,ll y)
	{
		if(l==r)return s[x];
		push_down(x);
		ll mid=l+r>>1;
		if(y<=mid)return ask(ls,l,mid,y);
		else return ask(rs,mid+1,r,y);
	}
}T;
int main()
{
	scanf("%lld%lld",&n,&m);
	for(ll i=1;i<=3;++i)
		for(ll j=1;j<=n;++j)
			scanf("%lld",&a[i][j]);
	for(ll i=1;i<=n;++i)
		b[i]=b[i-1]+a[1][i]-a[2][i-1];
	for(ll i=1;i<=m;++i){
		scanf("%lld%lld%lld",&X[i],&Y[i],&Z[i]);
		l[X[i]].push_back(i);
	}
	T.build(1,1,n);
	for(ll i=1;i<=n;++i)
		for(ll j=0;j<l[i].size();++j)
			T.change(1,1,n,i,Y[l[i][j]],Z[l[i][j]],(i>1?T.ask(1,1,n,i-1)-Z[l[i][j]]:-inf));
	for(ll i=1;i<=n;++i)
		sum+=a[3][i];
	ans=-inf;
	for(ll i=1;i<=n;++i){
		b[i]=b[i-1]+a[2][i]-a[3][i-1];
		ans=max(ans,sum+b[i]+T.ask(1,1,n,i));
	}
	printf("%lld",ans);
	return 0;
}