P10638 BZOJ4355 Play with sequence Solution-CSDN博客

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

Description

给定 $a=(a_1,a_2,\cdots,a_n)$ ，有 $m$ 个操作，分以下三种：

$\operatorname{assign}(l,r,k)$ ：对每个 $\in[l,r]$ 执行 $a_i \leftarrow k$ .
$\operatorname{modify}(l,r,k)$ ：对每个 $\in[l,r]$ 执行 $a_i \leftarrow max(a_i+c,0)$ .
$\operatorname{query}(l,r)$ ：求 $\sum\limits_{i=l}^r [a_i=0]$ .

Limitations

$\le n,m \le 3\times 10^5$
$\le a_i \le 10^9$
$\le k \le 10^9$ （ $\operatorname{assign}$ ）
$\le 10^9$ （ $\operatorname{modify}$ ）
$1.5\text{s},512\text{MB}$

Solution

看到区间最值，想到吉司机线段树.
考虑转化每个操作：

$\operatorname{assign}$ ：来一次 $\operatorname{chmax}$ ，再来一次 $\operatorname{chmin}$ .
$\operatorname{modify}$ ：来一次 $\operatorname{add}$ ，再来一次 $\operatorname{chmax}$ .
$\operatorname{query}$ ：由于 $a_i$ 非负，只需看最小值是否为 $0$ ，再看出现次数.

接下来只需把 P10639 代码拉过来改一下即可。

Code

$6.32\text{KB},1.66\text{s},48.61\text{MB}\;\texttt{(in total, C++ 20 with O2)}$

// Problem: P10639 BZOJ4695 最佳女选手
// Contest: Luogu
// URL: https://www.luogu.com.cn/problem/P10639
// Memory Limit: 512 MB
// Time Limit: 2000 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;
}

constexpr i64 inf = 3e18;

namespace seg_tree {
	struct Node {
	    int l, r, cmax, cmin;
	    i64 max, max2, min, min2;
	    i64 tag, tmin, tmax, sum;
	};
	
	inline int ls(int u) { return 2 * u + 1; }
	inline int rs(int u) { return 2 * u + 2; }
	
	struct SegTree {
		vector<Node> tr;
		inline SegTree() {}
		inline SegTree(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) {
		    tr[u].sum = tr[ls(mid)].sum + tr[rs(mid)].sum;
		    if (tr[ls(mid)].max == tr[rs(mid)].max) {
		        tr[u].max = tr[ls(mid)].max;
		        tr[u].cmax = tr[ls(mid)].cmax + tr[rs(mid)].cmax;
		        tr[u].max2 = max(tr[ls(mid)].max2, tr[rs(mid)].max2);
		    }
		    else if (tr[ls(mid)].max > tr[rs(mid)].max) {
		        tr[u].max = tr[ls(mid)].max;
		        tr[u].cmax = tr[ls(mid)].cmax;
				tr[u].max2 = max(tr[ls(mid)].max2, tr[rs(mid)].max);
		    }
		    else {
		        tr[u].max = tr[rs(mid)].max;
		        tr[u].cmax = tr[rs(mid)].cmax;
		        tr[u].max2 = max(tr[ls(mid)].max, tr[rs(mid)].max2);
		    }
		    
		    if (tr[ls(mid)].min == tr[rs(mid)].min) {
		        tr[u].min = tr[ls(mid)].min;
		        tr[u].cmin = tr[ls(mid)].cmin + tr[rs(mid)].cmin;
		        tr[u].min2 = min(tr[ls(mid)].min2, tr[rs(mid)].min2);
		    }
		    else if (tr[ls(mid)].min < tr[rs(mid)].min) {
		        tr[u].min = tr[ls(mid)].min;
		        tr[u].cmin = tr[ls(mid)].cmin;
		    	tr[u].min2 = min(tr[ls(mid)].min2, tr[rs(mid)].min);
		    }
		    else {
		        tr[u].min = tr[rs(mid)].min;
		        tr[u].cmin = tr[rs(mid)].cmin;
		        tr[u].min2 = min(tr[ls(mid)].min, tr[rs(mid)].min2);
		    }
		}
		
		inline void build(int u, int l, int r, const vector<i64>& A) {
		    tr[u].l = l;
		    tr[u].r = r;
		    tr[u].tmin = inf;
		    tr[u].tmax = -inf;
		    
			if (l == r) {
				tr[u].sum = tr[u].max = tr[u].min = A[l];
				tr[u].max2 = -inf;
				tr[u].min2 = inf;
				tr[u].cmax = tr[u].cmin = 1;
				return;
			}
			
			const int mid = (l + r) >> 1;
			build(ls(mid), l, mid, A);
			build(rs(mid), mid + 1, r, A);
			pushup(u, mid);
		}
		
		inline void upd_add(int u, i64 val) {
		    tr[u].sum += val * (tr[u].r - tr[u].l + 1);
			tr[u].max += val;
			tr[u].min += val;
			if (tr[u].max2 != -inf) tr[u].max2 += val;
			if (tr[u].min2 != inf) tr[u].min2 += val;
			if (tr[u].tmax != -inf) tr[u].tmax += val;
			if (tr[u].tmin != inf) tr[u].tmin += val;
			tr[u].tag += val;
		}
		
		inline void upd_min(int u, i64 val) {
		    if (tr[u].max <= val) return;
			tr[u].sum += (val - tr[u].max) * tr[u].cmax;
			if (tr[u].min2 == tr[u].max) tr[u].min2 = val;
			if (tr[u].min == tr[u].max) tr[u].min = val;
			tr[u].tmax = min(tr[u].tmax, val);
			tr[u].max = val;
			tr[u].tmin = val;
		}
		
		inline void upd_max(int u, i64 val) {
		    if (tr[u].min > val) return;
			tr[u].sum += (val - tr[u].min) * tr[u].cmin;
			if (tr[u].max2 == tr[u].min) tr[u].max2 = val; 
			if (tr[u].max == tr[u].min) tr[u].max = val;
			tr[u].tmin = max(tr[u].tmin, val);
			tr[u].min = val;
			tr[u].tmax = val;
		}
		
		inline void pushdown(int u, int mid) {
		    if (tr[u].tag) {
		        upd_add(ls(mid), tr[u].tag);
		        upd_add(rs(mid), tr[u].tag);
		    }
		    if (tr[u].tmax != -inf) {
				upd_max(ls(mid), tr[u].tmax);
				upd_max(rs(mid), tr[u].tmax);
			}
			if (tr[u].tmin != inf) {
				upd_min(ls(mid), tr[u].tmin);
				upd_min(rs(mid), tr[u].tmin);
			}
			tr[u].tag = 0;
			tr[u].tmax = -inf;
			tr[u].tmin = inf;
		}
		
		inline void add(int u, int l, int r, i64 val) {
		    if (l <= tr[u].l && tr[u].r <= r) return upd_add(u, val);
		    const int mid = (tr[u].l + tr[u].r) >> 1;
		    pushdown(u, mid);
		    if (l <= mid) add(ls(mid), l, r, val);
		    if (r > mid) add(rs(mid), l, r, val);
		    pushup(u, mid);
		}
		
		inline void chmin(int u, int l, int r, i64 val) {
		    if (tr[u].max <= val) return;
		    if (l <= tr[u].l && tr[u].r <= r && tr[u].max2 < val) return upd_min(u, val);
		    const int mid = (tr[u].l + tr[u].r) >> 1;
		    pushdown(u, mid);
		    if (l <= mid) chmin(ls(mid), l, r, val);
		    if (r > mid) chmin(rs(mid), l, r, val);
		    pushup(u, mid);
		}
		
		inline void chmax(int u, int l, int r, i64 val) {
		    if (tr[u].min >= val) return;
		    if (l <= tr[u].l && tr[u].r <= r && tr[u].min2 > val) return upd_max(u, val);
		    const int mid = (tr[u].l + tr[u].r) >> 1;
		    pushdown(u, mid);
		    if (l <= mid) chmax(ls(mid), l, r, val);
		    if (r > mid) chmax(rs(mid), l, r, val);
		    pushup(u, mid);
		}
		
		inline int query(int u, int l, int r) {
		    if (tr[u].min > 0) return 0;
			if (l <= tr[u].l && tr[u].r <= r) return tr[u].cmin;
			const int mid = (tr[u].l + tr[u].r) >> 1;
			pushdown(u, mid);
			if (r <= mid) return query(ls(mid), l, r);
			else if (l > mid) return query(rs(mid), l, r);
			else return query(ls(mid), l, r) + query(rs(mid), l, r);
		}
		
		inline void range_add(int l, int r, i64 x) { add(0, l, r, x); }
		inline void range_chmin(int l, int r, i64 x) { chmin(0, l, r, x); }
		inline void range_chmax(int l, int r, i64 x) { chmax(0, l, r, x); }
		inline int range_zeros(int l, int r) { return query(0, l, r); }
	};
}
using seg_tree::SegTree;

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]);
	SegTree sgt(a);
	for (int i = 0, op, l, r, v; i < m; i++) {
	    scanf("%d %d %d", &op, &l, &r);
	    l--, r--;
	    if (op == 1) {
	        scanf("%d", &v);
	        sgt.range_chmax(l, r, v);
	        sgt.range_chmin(l, r, v);
	    }
	    if (op == 2) {
	        scanf("%d", &v);
	        sgt.range_add(l, r, v);
	        sgt.range_chmax(l, r, 0);
	    }
	    if (op == 3) {
	        printf("%d\n", sgt.range_zeros(l, r));
	    }
	}

	return 0;
}