正題

luogu
CF1648D

---

題目大意

有一個 3*n 的矩陣，1,3行沒有行走限制，對于第2行，有m個區(qū)間，覆蓋第 i 個區(qū)間有 $k_i$ 的代價，只有覆蓋的位置才能走，讓你從 (1,1) 走到 (3,n)（只能向下和向右走） ，答案為經(jīng)過的每個點的權(quán)值之和減去代價之和，問你答案最大值

---

解題思路

可以把第2行的權(quán)值用前綴和計算，令 $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}$

答案就轉(zhuǎn)化為了在第二行走一段路答案為 $A_{bg}+B_{ed}$，這個可以先按區(qū)間的左端點排序，然后再線段樹上依次往后貢獻即可

---

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+1ll 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; }

總結(jié)

以上是生活随笔為你收集整理的【线段树】Serious Business（CF1648D）的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。