P5693 EI 的第六分块 Solution

Description

给定序列 $a=(a_1,a_2,\cdots ,a_n)$，有 $m$ 个操作分两种：

• $\mathrm{add}(l,r,v)$：对每个 $i\in [l,r]$ 执行 $a_i\leftarrow a_i+v$.
• $\mathrm{query}(l,r)$：求 $\max (0,\underset{[u,v]\in [l,r]}{\max }\sum _{i=u}^v{a}_i)$.

Limitations

$1\le n,m\le 4\times 10^5$
$1\le l\le r\le n$
$|a_i|\le 10^9$
$1\le v\le 10^6$
$1.8\text{s},256\text{MB}$

Solution

求最大子段和，显然要维护区间和 $\text{sum}$，最大前缀、后缀、子段和 $\text{lmax},\text{rmax},\text{tmax}$.
考虑区间加 $v$ 对这些值的影响：
如果选择的区间没有变，则答案要加上 $kv$，其中 $k$ 为该区间的长度.
考虑把上述四个值变成一次函数 $y=kx+b$，若选择区间不变则 $x$ 加上 $v$.
但选择的区间不是一成不变的，为了判断，我们需要维护阈值 $L$，表示若 $x\ge L$ 则四个值选择的区间至少会变一个.

pushup 时 $+$ 操作变成一次函数相加，$\max$ 变成函数在 $x=0$ 时的比较.
$L$ 取子节点的 $L$ 的最小，以及 $\text{lmax},\text{rmax}$ 两种方案，$\text{tmax}$ 三种方案的函数交点取最小（若小于 $0$ 或无交则变为 $\infty$）.

每次修改就把 $x$ 减去 $v$，若减后 $x<0$，则暴力遍历子树进行重构，若一棵子树的 $x\ge 0$ 就直接打标记而不进入.

上述即 KTT，时间复杂度约为 $O((n+m){\log }^{3}n)$，具体见 EI’s blog.
需要注意，上述方法建立在区间加正数这一基础上.

Code

$4.22\text{KB},5.10\text{s},138.06\text{MB}\text{(in total, C++20 with O2)}$

// Problem: P5693 EI 的第六分块
// Contest: Luogu
// URL: https://www.luogu.com.cn/problem/P5693
// Memory Limit: 256 MB
// Time Limit: 1800 ms
// 
// Powered by CP Editor (https://cpeditor.org)

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

using i64 = long long;
using ui64 = unsigned long long;
using i128 = __int128;
using ui128 = unsigned __int128;
using f4 = float;
using f8 = double;
using f16 = long double;

template<class T>
bool chmax(T &a, const T &b){
	if(a < b){ a = b; return true; }
	return false;
}

template<class T>
bool chmin(T &a, const T &b){
	if(a > b){ a = b; return true; }
	return false;
}

const i64 inf = 3e18;

struct Line {
    int k;
    i64 b;
    Line(int _k = 0, i64 _b = 0): k(_k), b(_b) {}
    
    void add(i64 v) {
        b += k * v;
    }
};

inline Line operator+(const Line& lhs, const Line& rhs) {
    return Line(lhs.k + rhs.k, lhs.b + rhs.b);
}

inline pair<Line, i64> find(const Line& a, const Line& b) {
    if (a.k < b.k || (a.k == b.k && a.b < b.b)) {
        return find(b, a);
    }
    if (a.b >= b.b) {
        return make_pair(a, inf);
    }
    return make_pair(b, (b.b - a.b) / (a.k - b.k));
}

struct Node {
    int l, r;
    Line lmax, rmax, tmax, sum;
    i64 x, tag;
};
using Tree = vector<Node>;
inline int ls(int u) { return 2 * u + 1; }
inline int rs(int u) { return 2 * u + 2; }

inline void merge(Node& res, const Node& le, const Node& ri) {
	i64 x0 = min(le.x, ri.x);
	Line sum = le.sum + ri.sum;
	auto [lmax, x1] = find(le.lmax, le.sum + ri.lmax);
	auto [rmax, x2] = find(ri.rmax, le.rmax + ri.sum);
	auto [temp, x3] = find(le.tmax, ri.tmax);
	auto [tmax, x4] = find(temp, le.rmax + ri.lmax);
	
	res.lmax = lmax;
	res.rmax = rmax;
	res.tmax = tmax;
	res.sum = sum;
	res.x = min({x0, x1, x2, x3, x4});
}

inline void pushup(Tree& tr, int u) {
    merge(tr[u], tr[ls(u)], tr[rs(u)]);
}

inline void add(Tree& tr, int u, i64 v) {
    tr[u].tag += v;
    tr[u].x -= v;
    tr[u].lmax.add(v);
    tr[u].rmax.add(v);
    tr[u].sum.add(v);
    tr[u].tmax.add(v);
}

inline void pushdown(Tree& tr, int u) {
    if (tr[u].tag) {
        add(tr, ls(u), tr[u].tag);
        add(tr, rs(u), tr[u].tag);
        tr[u].tag = 0;
    }
}

inline void build(Tree& tr, int u, int l, int r, vector<i64>& a) {
    tr[u].l = l;
    tr[u].r = r;
    if (l == r) {
        Line f(1, a[l]);
        tr[u].lmax = tr[u].rmax = tr[u].tmax = tr[u].sum = f;
        tr[u].x = inf;
        return;
    }
    
    int mid = (l + r) >> 1;
    build(tr, ls(u), l, mid, a);
    build(tr, rs(u), mid + 1, r, a);
    pushup(tr, u);
}

inline void defeat(Tree& tr, int u, i64 v) {
    if (v > tr[u].x) {
        defeat(tr, ls(u), tr[u].tag + v);
        defeat(tr, rs(u), tr[u].tag + v);
        tr[u].tag = 0;
        pushup(tr, u);
    }
    else {
        add(tr, u, v);
    }
}

inline void update(Tree& tr, int u, int l, int r, i64 v) {
    if (l <= tr[u].l && tr[u].r <= r) {
        return defeat(tr, u, v);
    }
    
    int mid = (tr[u].l + tr[u].r) >> 1;
    pushdown(tr, u);
    if (l <= mid) {
        update(tr, ls(u), l, r, v);
    }
    if (r > mid) {
        update(tr, rs(u), l, r, v);
    }
    pushup(tr, u);
}

inline Node query(Tree& tr, int u, int l, int r) {
    if (l <= tr[u].l && tr[u].r <= r) {
        return tr[u];
    }
    
    int mid = (tr[u].l + tr[u].r) >> 1;
    pushdown(tr, u);
    if (r <= mid) {
        return query(tr, ls(u), l, r);
    }
    if (l > mid) {
        return query(tr, rs(u), l, r);
    }
    Node le = query(tr, ls(u), l, r), ri = query(tr, rs(u), l, r), res;
    merge(res, le, ri);
    return res;
}

signed main() {
	ios::sync_with_stdio(0);
	cin.tie(0), cout.tie(0);
	
	int n, m;
	scanf("%d %d", &n, &m);
	
	vector<i64> a(n);
	for (int i = 0; i < n; i++) {
	    scanf("%lld", &a[i]);
	}
	
	Tree ktt(n << 2);
	build(ktt, 0, 0, n - 1, a);
	
	for (int i = 0, op, l, r; i < m; i++) {
	    scanf("%d %d %d", &op, &l, &r);
	    l--, r--;
	    
	    if (op == 1) {
	        i64 v;
	        scanf("%lld", &v);
	        update(ktt, 0, l, r, v);
	    }
	    else {
	        printf("%lld\n", max(query(ktt, 0, l, r).tmax.b, 0LL));
	    }
	}
	
	return 0;
}