P10638 BZOJ4355 Play with sequence Solution

Description

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

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

Limitations

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

Solution

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

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

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

Code

$5.85\text{KB},1.66\text{s},94.47\text{MB}\text{(in total, C++ 20 with O2)}$

// Problem: P10638 BZOJ4355 Play with sequence
// Contest: Luogu
// URL: https://www.luogu.com.cn/problem/P10638
// Memory Limit: 512 MB
// Time Limit: 1500 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 Node {int l, r, cmax, cmin;i64 max, max2, min, min2;i64 tag, tmin, tmax, sum;
};
using Tree = vector<Node>;
inline int ls(int u) { return 2 * u + 1; }
inline int rs(int u) { return 2 * u + 2; }inline void pushup(Tree& tr, int u) {tr[u].sum = tr[ls(u)].sum + tr[rs(u)].sum;if (tr[ls(u)].max == tr[rs(u)].max) {tr[u].max = tr[ls(u)].max;tr[u].cmax = tr[ls(u)].cmax + tr[rs(u)].cmax;tr[u].max2 = max(tr[ls(u)].max2, tr[rs(u)].max2);}else if (tr[ls(u)].max > tr[rs(u)].max) {tr[u].max = tr[ls(u)].max;tr[u].cmax = tr[ls(u)].cmax;tr[u].max2 = max(tr[ls(u)].max2, tr[rs(u)].max);}else {tr[u].max = tr[rs(u)].max;tr[u].cmax = tr[rs(u)].cmax;tr[u].max2 = max(tr[ls(u)].max, tr[rs(u)].max2);}if (tr[ls(u)].min == tr[rs(u)].min) {tr[u].min = tr[ls(u)].min;tr[u].cmin = tr[ls(u)].cmin + tr[rs(u)].cmin;tr[u].min2 = min(tr[ls(u)].min2, tr[rs(u)].min2);}else if (tr[ls(u)].min < tr[rs(u)].min) {tr[u].min = tr[ls(u)].min;tr[u].cmin = tr[ls(u)].cmin;tr[u].min2 = min(tr[ls(u)].min2, tr[rs(u)].min);}else {tr[u].min = tr[rs(u)].min;tr[u].cmin = tr[rs(u)].cmin;tr[u].min2 = min(tr[ls(u)].min, tr[rs(u)].min2);}
}inline void build(Tree& tr, 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(tr, ls(u), l, mid, A);build(tr, rs(u), mid + 1, r, A);pushup(tr, u);
}inline void upd_add(Tree& tr, 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(Tree& tr, 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(Tree& tr, 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(Tree& tr, int u) {if (tr[u].tag) {upd_add(tr, ls(u), tr[u].tag);upd_add(tr, rs(u), tr[u].tag);}if (tr[u].tmax != -inf) {upd_max(tr, ls(u), tr[u].tmax);upd_max(tr, rs(u), tr[u].tmax);}if (tr[u].tmin != inf) {upd_min(tr, ls(u), tr[u].tmin);upd_min(tr, rs(u), tr[u].tmin);}tr[u].tag = 0;tr[u].tmax = -inf;tr[u].tmin = inf;
}inline void add(Tree& tr, int u, int l, int r, i64 val) {if (l <= tr[u].l && tr[u].r <= r) return upd_add(tr, u, val);const int mid = (tr[u].l + tr[u].r) >> 1;pushdown(tr, u);if (l <= mid) add(tr, ls(u), l, r, val);if (r > mid) add(tr, rs(u), l, r, val);pushup(tr, u);
}inline void chmin(Tree& tr, 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(tr, u, val);const int mid = (tr[u].l + tr[u].r) >> 1;pushdown(tr, u);if (l <= mid) chmin(tr, ls(u), l, r, val);if (r > mid) chmin(tr, rs(u), l, r, val);pushup(tr, u);
}inline void chmax(Tree& tr, 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(tr, u, val);const int mid = (tr[u].l + tr[u].r) >> 1;pushdown(tr, u);if (l <= mid) chmax(tr, ls(u), l, r, val);if (r > mid) chmax(tr, rs(u), l, r, val);pushup(tr, u);
}inline int query(Tree& tr, 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(tr, u);if (r <= mid) return query(tr, ls(u), l, r);else if (l > mid) return query(tr, rs(u), l, r);else return query(tr, ls(u), l, r) + query(tr, rs(u), l, r);
}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 tr(n << 2);build(tr, 0, 0, n - 1, 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);chmax(tr, 0, l, r, v);chmin(tr, 0, l, r, v);}if (op == 2) {scanf("%d", &v);add(tr, 0, l, r, v);chmax(tr, 0, l, r, 0);}if (op == 3) {printf("%d\n", query(tr, 0, l, r));}}return 0;
}