CF1648D Serious Business

· · 题解

记 a,b,c 分别为三行的前缀和，前缀和，后缀和数组。

设 f_i 为到第二行第 i 列最小代价，答案即 \max\{f_i+c_i\}。设区间 [l,r] 包含 i，代价为 k 转移为：

做扫描线，对于后者，在扫到 l 的时候将 f_{l-1}-b_{l-1} 加入 multiset S，r+1 时弹出，f_i\gets\max(S)。

对于前者，考虑维护 n 个 multiset，扫到 l 的时候将 k 加入 S_l,\cdots,S_r，r+1 的时候弹出。f_i\gets\max_{j=1}^i\{a_j-b_{j-1}-\min(S_i)\}+b_i。

线段树+标记永久化优化这个过程，一次修改仅涉及到 O(\log n) 个 multiset，线段树维护区间 \max\{a_j-b_{j-1}\} 就可以算答案（当前节点答案和左右子树答案都要考虑）。复杂度 O(n\log^2n)。

注意可以初始插入所有数，然后扫描线到 r 时删除。只要初始插入就按照 k 的顺序就可以避免 multiset。vector+惰性删除，复杂度 O(n\log n)。

轻微卡常，实现可参考。

#pragma GCC optimize("Ofast,no-stack-protector")
#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")

#include<bits/stdc++.h>
using namespace std;

#ifdef ONLINE_JUDGE
static char buf[1000000],*p1=buf,*p2=buf;
#define getchar() p1==p2&&(p2=(p1=buf)+fread(buf,1,1000000,stdin),p1==p2)?EOF:*p1++
#endif

inline int read(){
    register int x = 0;
    register bool f = 0;
    register char c = getchar();
    for(;c < '0' || c > '9';c = getchar()) f |= c == '-';
    for(;c >= '0' && c <= '9';c = getchar())
        x = x * 10 + (c ^ '0');
    return f ? -x : x;
}

using ll = long long;

const int N = 5e5 + 5,M = N * 4;

int n,m,L[N],R[N],I[N];
ll a[N],b[N],c[N],f[N],K[N],ans = -1e18;
vector<pair<int,int>> O[N];
bool vis[N];

#define lc (i * 2)
#define rc (lc + 1)
#define mid ((L + R) / 2)
#define ls lc,L,mid
#define rs rc,mid + 1,R
#define id int i = 1,int L = 1,int R = n

vector<int> T[M];
int C[M];
ll V[M],S[M];

void psu(id){
    S[i] = T[i].size() ? V[i] - K[T[i].back()] : -1e18;
    if(L < R) S[i] = max({S[i],S[lc],S[rc]});
}

void build(id){
    if(L == R) V[i] = a[L] - b[L - 1];
    else build(ls),build(rs),V[i] = max(V[lc],V[rc]);
    psu(i,L,R);
}

void add(int l,int r,id){
    if(r < L || R < l) return;
    if(l <= L && R <= r) ++C[i];
    else add(l,r,ls),add(l,r,rs);
}

void ins(int l,int r,int x,id){
    if(r < L || R < l) return;
    if(l <= L && R <= r) T[i].push_back(x);
    else ins(l,r,x,ls),ins(l,r,x,rs);
}

void ers(int l,int r,id){
    if(r < L || R < l) return;
    if(l <= L && R <= r)
        for(;T[i].size() && vis[T[i].back()];T[i].pop_back());
    else ers(l,r,ls),ers(l,r,rs);
    psu(i,L,R);
}

ll qry(int l,int r,ll x = 1e18,id,ll s = -1e18){
    if(l > r) return s;
    if(T[i].size()) x = min(x,K[T[i].back()]);
    if(l <= L && R <= r) return max(V[i] - x,S[i]);
    if(l <= mid) s = qry(l,r,x,ls);
    if(r > mid) s = max(s,qry(l,r,x,rs));
    return s;
}

multiset<ll> _;

int main(){
    n = read(),m = read();
    for(int i = 1;i <= n;++i) a[i] = read() + a[i - 1];
    for(int i = 1;i <= n;++i) b[i] = read() + b[i - 1];
    for(int i = 1;i <= n;++i) c[i] = read();
    for(int i = n;i >= 1;--i) c[i] += c[i + 1];
    for(int i = 1;i <= m;++i)
        O[L[i] = read()].emplace_back(i,1),
        O[(R[i] = read()) + 1].emplace_back(i,0),
        I[i] = i,K[i] = read();
    sort(I + 1,I + m + 1,[](int i,int j){ return K[i] < K[j]; });
    for(int i = m;i >= 1;--i) add(L[I[i]],R[I[i]]);
    for(int i = 1;i <= 4 * n;++i) T[i].reserve(C[i]);
    for(int i = m;i >= 1;--i) ins(L[I[i]],R[I[i]],I[i]);
    build(); 
    f[0] = -1e18;
    for(int i = 1;i <= n;++i){
        for(auto[j,k] : O[i]){
            ll x = f[L[j] - 1] - b[L[j] - 1] - K[j];
            if(k) _.insert(x);
            else vis[j] = 1,ers(L[j],R[j]),_.erase(_.find(x));
        }
        f[i] = qry(1,i) + b[i];
        if(_.size()) f[i] = max(f[i],*_.rbegin() + b[i]);
        ans = max(ans,f[i] + c[i]);
    }
    printf("%lld\n",ans);
    return 0;
}