CF1648D Serious Business

(Updated: )
oi

题目链接：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

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
#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<<11,mid+1,r
        #define PT CI x=1,CI l=1,CI r=n
        #define PU(x) (T[x]=T[x<<1]+T[x<<11])
    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;
}