恩施网站建设公司,婚纱官网,网站配色 标记色,网站界面设计需要正题
luogu CF1648D 题目大意
有一个 3*n 的矩阵#xff0c;1,3行没有行走限制#xff0c;对于第2行#xff0c;有m个区间#xff0c;覆盖第 i 个区间有 kik_iki 的代价#xff0c;只有覆盖的位置才能走#xff0c;让你从 (1,1) 走到 (3,n)#xff08;只能向下和向右…正题
luogu CF1648D 题目大意
有一个 3*n 的矩阵1,3行没有行走限制对于第2行有m个区间覆盖第 i 个区间有 kik_iki 的代价只有覆盖的位置才能走让你从 (1,1) 走到 (3,n)只能向下和向右走 答案为经过的每个点的权值之和减去代价之和问你答案最大值 解题思路
可以把第2行的权值用前缀和计算令 Ai∑j1is1,j−∑j1i−1s2,j,Bi∑jins3,j∑j1is2,jA_i\sum_{j1}^i s_{1,j}-\sum_{j1}^{i-1} s_{2,j},B_i\sum_{ji}^n s_{3,j}\sum_{j1}^{i} s_{2,j}Ai∑j1is1,j−∑j1i−1s2,j,Bi∑jins3,j∑j1is2,j
答案就转化为了在第二行走一段路答案为 AbgBedA_{bg}B_{ed}AbgBed这个可以先按区间的左端点排序然后再线段树上依次往后贡献即可 code
#includevector
#includecstdio
#includecstring
#includeiostream
#includealgorithm
#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];
vectorlll[N];
const ll inf1e18;
struct Tree
{#define ls x*2#define rs x*21ll s[N2],v[N2],lazy[N2],lazyy[N2];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(lr){v[x]b[l];return;}ll midlr1;build(ls,l,mid);build(rs,mid1,r);push_up(x);return;}ll change(ll x,ll L,ll R,ll l,ll r,ll ad,ll an){if(LlRr){get(x,ad,an);return max(v[x],s[x]);}push_down(x);ll midLR1,g;if(rmid)gchange(ls,L,mid,l,r,ad,an);else if(lmid)gchange(rs,mid1,R,l,r,ad,an);else{gchange(ls,L,mid,l,mid,ad,an);gmax(g,change(rs,mid1,R,mid1,r,ad,max(an,g-ad)));}push_up(x);return g;}ll ask(ll x,ll l,ll r,ll y){if(lr)return s[x];push_down(x);ll midlr1;if(ymid)return ask(ls,l,mid,y);else return ask(rs,mid1,r,y);}
}T;
int main()
{scanf(%lld%lld,n,m);for(ll i1;i3;i)for(ll j1;jn;j)scanf(%lld,a[i][j]);for(ll i1;in;i)b[i]b[i-1]a[1][i]-a[2][i-1];for(ll i1;im;i){scanf(%lld%lld%lld,X[i],Y[i],Z[i]);l[X[i]].push_back(i);}T.build(1,1,n);for(ll i1;in;i)for(ll j0;jl[i].size();j)T.change(1,1,n,i,Y[l[i][j]],Z[l[i][j]],(i1?T.ask(1,1,n,i-1)-Z[l[i][j]]:-inf));for(ll i1;in;i)suma[3][i];ans-inf;for(ll i1;in;i){b[i]b[i-1]a[2][i]-a[3][i-1];ansmax(ans,sumb[i]T.ask(1,1,n,i));}printf(%lld,ans);return 0;
}
