当前位置：首页 > article >正文

P6792 [SNOI2020] 区间和 Solution

article 2025/2/24 17:53:40

Description

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

$\operatorname{chmax}(l,r,v)$ ：对每个 $\in [l,r]$ 执行 $a_i \gets \max(a_i,v)$ .
$\operatorname{query}(l,r)$ ：求 $\max(0,\max\limits_{[u,v]\in [l,r]}\sum\limits_{i=u}^v a_i)$ .

Limitations

$\le n \le 10^5$
$\le m \le 2\times 10^5$
$\le l \le r \le n$
$|a_i|,|v| \le 10^9$
$3\text{s},512\text{MB}$

Solution

看到 $\operatorname{chmax}$ 先来一个吉司机.
然后下传标记相当于区间加上 $(v-\textit{minv})$ ，这样就把问题变成区间加正数.
然后可以上 KTT 维护，具体见 P5693.
但是要注意 pushup 时要考虑吉司机的 $\min$ ，所以要将两者间较大值的 $k$ 全部清零.
时间复杂度应该是 $O((n+m)\log^3n)$

Code

$5.19\text{KB},4.93\text{s},40.97\text{MB}\;\texttt{(in total, C++20 with O2)}$

// Problem: P6792 [SNOI2020] 区间和
// Contest: Luogu
// URL: https://www.luogu.com.cn/problem/P6792
// Memory Limit: 512 MB
// Time Limit: 3000 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;
    }
    
    void reset() {
        k = 0;
    }
};

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, min, sec;
    
    inline Node reset() {
        Node res = *this;
        res.lmax.reset();
        res.rmax.reset();
        res.tmax.reset();
        res.sum.reset();
        return res;
    }
};
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) {
	if (tr[ls(u)].min == tr[rs(u)].min) {
	    tr[u].min = tr[ls(u)].min;
	    tr[u].sec = min(tr[ls(u)].sec, tr[rs(u)].sec);
	    merge(tr[u], tr[ls(u)], tr[rs(u)]);
	}
	else if (tr[ls(u)].min < tr[rs(u)].min) {
	    tr[u].min = tr[ls(u)].min;
	    tr[u].sec = min(tr[ls(u)].sec, tr[rs(u)].min);
	    merge(tr[u], tr[ls(u)], tr[rs(u)].reset());
	}
	else {
	    tr[u].min = tr[rs(u)].min;
	    tr[u].sec = min(tr[ls(u)].min, tr[rs(u)].sec);
	    merge(tr[u], tr[ls(u)].reset(), tr[rs(u)]);
	}
}

inline void add(Tree& tr, int u, i64 w) {
    if (w <= tr[u].min) {
        return;
    }
    
    i64 v = w - tr[u].min;
    tr[u].min = w;
    tr[u].tag = max(tr[u].tag, w);
    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 != -inf) {
        add(tr, ls(u), tr[u].tag);
        add(tr, rs(u), tr[u].tag);
        tr[u].tag = -inf;
    }
}

inline void build(Tree& tr, int u, int l, int r, vector<i64>& a) {
    tr[u].l = l;
    tr[u].r = r;
    tr[u].tag = -inf;
    if (l == r) {
        Line f(1, a[l]);
        tr[u].lmax = tr[u].rmax = tr[u].tmax = tr[u].sum = f;
        tr[u].x = tr[u].sec = inf;
        tr[u].min = a[l];
        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) {
    tr[u].tag = max(tr[u].tag, v);
    if (v - tr[u].min > tr[u].x) {
        defeat(tr, ls(u), v);
        defeat(tr, rs(u), v);
        pushup(tr, u);
    }
    else {
        add(tr, u, v);
    }
}

inline void update(Tree& tr, int u, int l, int r, i64 v) {
    if (tr[u].min >= v) {
        return;
    }
    if (l <= tr[u].l && tr[u].r <= r && v < tr[u].sec) {
        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 == 0) {
	        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;
}