北京自助建站系统_夜里十大禁用b站app网页版_企业管理培训课程视频_windows系统优化软件排行榜

Description

定义由 $42$ 为初始数，朝后依次拼接 $4,2$ 的数为 好数.
给定序列 $a=(a_1,a_2,\cdots ,a_n)$，有 $m$ 个操作分四种：

• $\mathrm{add}(l,r,k)$：对每个 $i\in [l,r]$ 执行 $a_i\leftarrow a_i+k$.
• $\mathrm{mul}(l,r,k)$：对每个 $i\in [l,r]$ 执行 $a_i\leftarrow a_i\times k$.
• $\mathrm{assign}(l,r,k)$：对每个 $i\in [l,r]$ 执行 $a_i\leftarrow k$.
• $\mathrm{query}(l,r)$：求 $a_l\sim a_r$ 中好数个数.

Limitations

$1\le n,m,k\le 5\times 10^5$
$1\le l\le r\le n$
保证任意时刻 $1\le a_i\le 5\times 10^5$.
$0.7\text{s},64\text{MB}$

Solution

设 $f(x)$ 表示第一个不小于 $x$ 的好数与 $x$ 的差.
但 $f(x)$ 的图像不连续，不好维护，但 $V=5\times 10^5$ 时，好数只有 $5$ 个.
由于要区间操作，考虑用 势能线段树，每个节点维护区间内 $f(a_i)$ 的最小值 $\text{mix}$，以及满足 $f(a_i)=\text{mix}$ 的 $a_i$ 个数 $\text{cnt}$.

对于 $\mathrm{add}$ 操作，结合函数图像，若当前节点的 $\text{mix}\le k$，则直接打加标记，否则递归子树继续修改.
对于 $\mathrm{mul}$ 操作，直接暴力做，每个数至多被乘 $\log V$ 次.
对于 $\mathrm{assign}$ 操作，直接打标记，但它会让前两个操作的复杂度假掉，不过很好解决，维护区间最大最小值，当两者相等时，直接打标记覆盖成 $\text{max}+(\text{或}\times )k$ 即可.
对于 $\mathrm{query}$，若 $\text{mix}=0$，则答案为 $\text{cnt}$，否则为 $0$.

时间复杂度 $O(m\log n\log V)$，注意忽略掉 $k=1$ 的 $\mathrm{mul}$ 操作，以及卡常.

Code

$4.69\text{KB},201\text{ms},34.85\text{MB}\text{(in total, C++20 with O2)}$

#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;
}// #define LOCAL
#ifdef LOCAL
#define getchar_unlocked getchar
#define putchar_unlocked putchar
#endiftemplate<class T>
inline T read() {T x = 0, f = 1;char ch = getchar_unlocked();while (ch < '0' || ch > '9') {if (ch == '-') f = -1;ch = getchar_unlocked();}while (ch >= '0' && ch <= '9') {x = (x << 3) + (x << 1) + (ch ^ 48);ch = getchar_unlocked();}return x * f;
}template<class T>
inline void write(T x) {if (x < 0) {putchar_unlocked('-');x = -x;}if (x > 9) write(x / 10);putchar_unlocked(x % 10 + '0');return;
}constexpr int V = 5e5;
namespace seg_tree {inline int ls(int u) { return 2 * u + 1; }inline int rs(int u) { return 2 * u + 2; }struct Node {int l, r;int max, min, mix, cnt, add = 0, cov = 0;};array<int, V + 1> nxt;void init() {int cur = V + 1;nxt.fill(-1);nxt[42] = nxt[424] = nxt[4242] = nxt[42424] = nxt[424242] = 0;for (int i = V; i >= 0; i--) {if (nxt[i] == 0) cur = i;else nxt[i] = cur - i;}}struct SegTree {vector<Node> tr;inline SegTree() {}inline SegTree(const vector<int>& 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].max = max(tr[ls(mid)].max, tr[rs(mid)].max);tr[u].min = min(tr[ls(mid)].min, tr[rs(mid)].min);tr[u].mix = min(tr[ls(mid)].mix, tr[rs(mid)].mix);tr[u].cnt = ((tr[u].mix == tr[ls(mid)].mix) * tr[ls(mid)].cnt + (tr[u].mix == tr[rs(mid)].mix) * tr[rs(mid)].cnt);}inline void applyC(int u, int x) {tr[u].max = tr[u].min = x;tr[u].mix = nxt[x];tr[u].cnt = tr[u].r - tr[u].l + 1;tr[u].cov = x;tr[u].add = 0;}inline void applyA(int u, int x) {tr[u].mix -= x;tr[u].add += x;tr[u].min += x;tr[u].max += x;}inline void pushdown(int u, int mid) {if (tr[u].cov) {applyC(ls(mid), tr[u].cov);applyC(rs(mid), tr[u].cov);tr[u].cov = 0;}if (tr[u].add) {applyA(ls(mid), tr[u].add);applyA(rs(mid), tr[u].add);tr[u].add = 0;}}void build(int u, int l, int r, const vector<int>& a) {tr[u].l = l, tr[u].r = r;if (l == r) {tr[u].max = tr[u].min = a[l];tr[u].mix = nxt[a[l]];tr[u].cnt = 1;return;}const int mid = (l + r) >> 1;build(ls(mid), l, mid, a);build(rs(mid), mid + 1, r, a);pushup(u, mid);}void add(int u, int l, int r, int x) {if (l <= tr[u].l && tr[u].r <= r) {if (tr[u].mix > x) return applyA(u, x);if (tr[u].min == tr[u].max) return applyC(u, tr[u].min + x);}const int mid = (tr[u].l + tr[u].r) >> 1;pushdown(u, mid);if (l <= mid) add(ls(mid), l, r, x);if (r > mid) add(rs(mid), l, r, x);pushup(u, mid);}void mul(int u, int l, int r, int x) {if (x == 1) return;if (l <= tr[u].l && tr[u].r <= r && tr[u].max == tr[u].min) return applyC(u, tr[u].min * x);const int mid = (tr[u].l + tr[u].r) >> 1;pushdown(u, mid);if (l <= mid) mul(ls(mid), l, r, x);if (r > mid) mul(rs(mid), l, r, x);pushup(u, mid);}void assign(int u, int l, int r, int x) {if (l <= tr[u].l && tr[u].r <= r) return applyC(u, x);const int mid = (tr[u].l + tr[u].r) >> 1;pushdown(u, mid);if (l <= mid) assign(ls(mid), l, r, x);if (r > mid) assign(rs(mid), l, r, x);pushup(u, mid);}int query(int u, int l, int r) {if (l <= tr[u].l && tr[u].r <= r) return (tr[u].mix == 0) * tr[u].cnt;const int mid = (tr[u].l + tr[u].r) >> 1;int res = 0;pushdown(u, mid);if (l <= mid) res += query(ls(mid), l, r);if (r > mid) res += query(rs(mid), l, r);return res;}};
}
using seg_tree::init;
using seg_tree::SegTree;signed main() {ios::sync_with_stdio(0);cin.tie(0), cout.tie(0);const int n = read<int>(), m = read<int>();vector<int> a(n);for (int i = 0; i < n; i++) a[i] = read<int>();init();SegTree sgt(a);for (int i = 0, op, l, r, v; i < m; i++) {op = read<int>(), l = read<int>(), r = read<int>(), l--, r--;if (op == 4) {write(sgt.query(0, l, r));putchar_unlocked('\n');}else {v = read<int>();if (op == 1) sgt.add(0, l, r, v);if (op == 2) sgt.mul(0, l, r, v);if (op == 3) sgt.assign(0, l, r, v);}}return 0;
}