CF1648D Serious Business
本文最后更新于 65 天前,其中的信息可能已经有所发展或是发生改变。

题目链接:CF1648D

给定一个 $3$ 行 $n$ 列的矩阵,每个位置有权值 $a_i,j$,初始时除第二行任意位置均不允许通过外第一行第三行均允许通过。

接下来有 $q$ 个操作,第 $i$ 个操作可使第二行的 $l_i\sim r_i$ 的位置可以通过,代价为 $k_i$。

你可以任意选择若干操作执行,需要最大化从 $(1,1)$ 走到 $(3,n)$ 的路径上的权值之和减去代价。

$n,q\leq 5\times 10^5$。

Tutorial

记 $s_{i,j}=\sum_{k=1}^j s_{i,k}$,显然答案可以拆分为:
$$
\max_{1\leq i\leq j\leq n} s_{1,i} – s_{2,i-1} + s_{2,j} – s_{3,j-1} + s_{3,n} – \operatorname{cost}(i,j)
$$
考虑用线段树维护 $s_{1,i}-s_{2,i-1} – \operatorname{cost}(i,j)$(第一部分),$s_{2,j}-s_{3,j-1}+s_{3,n}$(第二部分),$Ans$(第一部分与第二部分之和)。

不妨将这 $q$ 个操作按照 $r$ 排序,那么考虑其影响,每次可以扣 $[l_i,r_i]$ 中的答案减去 $k_i$ 即可纳入答案,而该操作对之后的影响即为 $r_{i+1}$ 的第一部分的贡献可以变为 $[l_i,r_i]$ 的答案的第一部分。

时间复杂度:$O(q(\log q+\log n))$。

Solution

#include<bits/stdc++.h>
#define Tp template<typename Ty>
#define Ts template<typename Ty,typename... Ar>
#define W while
#define I inline
#define RI register int
#define int long long
#define Cn const
#define CI Cn int&
#define gc getchar
#define D isdigit(c=gc())
#define pc(c) putchar((c))
using namespace std;
namespace Debug{
    Tp I void _debug(Cn char* f,Ty t){cerr<<f<<'='<<t<<endl;}
    Ts I void _debug(Cn char* f,Ty x,Ar... y){W(*f!=',') cerr<<*f++;cerr<<'='<<x<<",";_debug(f+1,y...);}
    Tp ostream& operator<<(ostream& os,Cn vector<Ty>& V){os<<"[";for(Cn auto& vv:V) os<<vv<<",";os<<"]";return os;}
    #define gdb(...) _debug(#__VA_ARGS__,__VA_ARGS__)
}using namespace Debug;
namespace FastIO{
    Tp I void read(Ty& x){char c;int f=1;x=0;W(!D) f=c^'-'?1:-1;W(x=(x<<3)+(x<<1)+(c&15),D);x*=f;}
    Ts I void read(Ty& x,Ar&... y){read(x),read(y...);}
    Tp I void write(Ty x){x<0&&(pc('-'),x=-x,0),x<10?(pc(x+'0'),0):(write(x/10),pc(x%10+'0'),0);}
    Tp I void writeln(Cn Ty& x){write(x),pc('\n');}
}using namespace FastIO;
Cn int N=5e5+10;
int n,q,a[4][N],Ans;
struct Que{int l,r,k;}g[N];
struct node{int l,r,v;}O;
I node operator+(Cn node& x,Cn node& y){return (node){max(x.l,y.l),max(x.r,y.r),max(max(x.v,y.v),x.l+y.r)};}
class SegmentTree{
    private:
        node T[N<<2];
        #define mid (l+r>>1)
        #define LT x<<1,l,mid
        #define RT x<<1|1,mid+1,r
        #define PT CI x=1,CI l=1,CI r=n
        #define PU(x) (T[x]=T[x<<1]+T[x<<1|1])
    public:
        I void B(PT){
            if(l==r) return void(T[x]=(node){a[1][l]-a[2][l-1],a[2][l]+a[3][n]-a[3][l-1],a[1][l]-a[2][l-1]+a[2][l]+a[3][n]-a[3][l-1]});
            B(LT),B(RT),PU(x);
        }
        I void U(CI p,CI v,PT){
            if(l==r) return T[x].l=max(T[x].l,v),T[x].v=T[x].l+T[x].r,void();
            p<=mid?U(p,v,LT):U(p,v,RT),PU(x);
        }
        I node Q(CI L,CI R,PT){
            if(L<=l&&r<=R) return T[x];
            if(R<=mid) return Q(L,R,LT);if(L>mid) return Q(L,R,RT);
            return Q(L,R,LT)+Q(L,R,RT);
        }
}T;
signed main(){
    RI i,j;for(read(n,q),i=1;i<=3;i++) for(j=1;j<=n;j++) read(a[i][j]),a[i][j]+=a[i][j-1];for(i=1;i<=q;i++) read(g[i].l,g[i].r,g[i].k);
    for(sort(g+1,g+q+1,[&](Cn Que& x,Cn Que& y){return x.r<y.r;}),T.B(),Ans=-2e18,i=1;i<=q;i++)
        O=T.Q(g[i].l,g[i].r),Ans=max(Ans,O.v-g[i].k),g[i].r<n&&(T.U(g[i].r+1,O.l-g[i].k),0);return writeln(Ans),0;
}
暂无评论

发送评论 编辑评论


|´・ω・)ノ
ヾ(≧∇≦*)ゝ
(☆ω☆)
(╯‵□′)╯︵┴─┴
 ̄﹃ ̄
(/ω\)
∠( ᐛ 」∠)_
(๑•̀ㅁ•́ฅ)
→_→
୧(๑•̀⌄•́๑)૭
٩(ˊᗜˋ*)و
(ノ°ο°)ノ
(´இ皿இ`)
⌇●﹏●⌇
(ฅ´ω`ฅ)
(╯°A°)╯︵○○○
φ( ̄∇ ̄o)
ヾ(´・ ・`。)ノ"
( ง ᵒ̌皿ᵒ̌)ง⁼³₌₃
(ó﹏ò。)
Σ(っ °Д °;)っ
( ,,´・ω・)ノ"(´っω・`。)
╮(╯▽╰)╭
o(*////▽////*)q
>﹏<
( ๑´•ω•) "(ㆆᴗㆆ)
😂
😀
😅
😊
🙂
🙃
😌
😍
😘
😜
😝
😏
😒
🙄
😳
😡
😔
😫
😱
😭
💩
👻
🙌
🖕
👍
👫
👬
👭
🌚
🌝
🙈
💊
😶
🙏
🍦
🍉
😣
Source: github.com/k4yt3x/flowerhd
颜文字
Emoji
小恐龙
花!
上一篇