P6792 & LOJ 3325 [SNOI2020] 区间和 Solution_snoi2020洛谷区间和-CSDN博客

本文链接：https://blog.csdn.net/sblsf/article/details/145655367

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.52\text{KB},5.41\text{s},21.10\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;

namespace ktt {
	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;
	    }
	};
	
	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});
	}
	
	struct KTT {
		vector<Node> tr;
		inline KTT() {}
		inline KTT(const vector<i64>& a) {
			const int n = a.size();
			tr.resize(n << 1);
			build(0, 0, n - 1, a);
		}
		
		inline void pushup(int u, int mid) {
			if (tr[ls(mid)].min == tr[rs(mid)].min) {
			    tr[u].min = tr[ls(mid)].min;
			    tr[u].sec = min(tr[ls(mid)].sec, tr[rs(mid)].sec);
			    merge(tr[u], tr[ls(mid)], tr[rs(mid)]);
			}
			else if (tr[ls(mid)].min < tr[rs(mid)].min) {
			    tr[u].min = tr[ls(mid)].min;
			    tr[u].sec = min(tr[ls(mid)].sec, tr[rs(mid)].min);
			    merge(tr[u], tr[ls(mid)], tr[rs(mid)].reset());
			}
			else {
			    tr[u].min = tr[rs(mid)].min;
			    tr[u].sec = min(tr[ls(mid)].min, tr[rs(mid)].sec);
			    merge(tr[u], tr[ls(mid)].reset(), tr[rs(mid)]);
			}
		}
		
		inline void add(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(int u, int mid) {
		    if (tr[u].tag != -inf) {
		        add(ls(mid), tr[u].tag);
		        add(rs(mid), tr[u].tag);
		        tr[u].tag = -inf;
		    }
		}
		
		inline void build(int u, int l, int r, const 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(ls(mid), l, mid, a);
		    build(rs(mid), mid + 1, r, a);
		    pushup(u, mid);
		}
		
		inline void defeat(int u, i64 v) {
		    tr[u].tag = max(tr[u].tag, v);
		    if (v - tr[u].min > tr[u].x) {
                int mid = (tr[u].l + tr[u].r) >> 1;
		        defeat(ls(mid), v);
		        defeat(rs(mid), v);
		        pushup(u, mid);
		    }
		    else {
		        add(u, v);
		    }
		}
		
		inline void update(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(u, v);
		    }
		    
		    int mid = (tr[u].l + tr[u].r) >> 1;
		    pushdown(u, mid);
		    if (l <= mid) {
		        update(ls(mid), l, r, v);
		    }
		    if (r > mid) {
		        update(rs(mid), l, r, v);
		    }
		    pushup(u, mid);
		}
		
		inline Node query(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(u, mid);
		    if (r <= mid) {
		        return query(ls(mid), l, r);
		    }
		    if (l > mid) {
		        return query(rs(mid), l, r);
		    }
		    Node le = query(ls(mid), l, r), ri = query(rs(mid), l, r), res;
		    merge(res, le, ri);
		    return res;
		}
		
		inline void range_chmax(int l, int r, i64 v) { update(0, l, r, v); }
		inline i64 range_gss(int l, int r) { return max(query(0, l, r).tmax.b, 0LL); }
	};
}
using ktt::KTT;

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]);
	}
	
	KTT ktt(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);
	        ktt.range_chmax(l, r, v);
	    }
	    else {
	        printf("%lld\n", ktt.range_gss(l, r));
	    }
	}
	
	return 0;
}