LG P7447 [Ynoi2007] rgxsxrs Solution

Description

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

• $\mathrm{subtract}(l,r,x)$：对每个 $i\in [l,r]$ 执行 $a_i\leftarrow a_i-x\times [a_i>x]$.
• $\mathrm{query}(l,r)$：求 $\sum _{i=l}^r{a}_i,\underset{i=l}{\overset{r}{\min }}{a}_i,\underset{i=l}{\overset{r}{\max }}{a}_i$.

Limitations

$1\le n,m\le 5\times 10^5$
$1\le a_i,x\le 10^9$
$1\le l\le r\le n$
$6\text{s},64\text{MB}$

Solution

首先考虑一种势能线段树：

每个节点维护所管辖区间的最值，在执行 $\mathrm{subtract}$ 时：

• 若当前 $\max <x$，操作没有用，直接退出.
• 若当前 $\min >x$，所有数都会被改，给当前节点打上一个减去 $x$ 的标记.

但是这玩意的复杂度是错的，只要给一个 $1,10^9$ 交替的序列，每次 $\mathrm{subtract}(1,n,1)$ 就被卡成 $O(nm)$ 了.

序列分块似乎也做不了，只能对值域分块，由于 $V$ 可达 $10^9$，所以要用倍增分块，将 $[b^i,b^{i+1})$ 分为一块，总共有 $\lceil {\log }_{b}V\rceil$ 块，其中 $b$ 为底数.

对每个块维护一棵上面所述的线段树，容易发现每个数最多减 $b$ 次就会掉出该块管辖范围，至于这些掉出的元素，因为一个数最多掉出 $O({\log }_{b}V)$ 次，可以直接暴力找块插入.

这样做的时间复杂度为 $O(nb\log n{\log }_{b}V)$，空间复杂度为 $O(n{\log }_{b}V)$.
然而由于常数比较大，$b$ 取 $2$ 是不够的，需要调大.

空间限制很紧，但是强制在线无法逐块处理，注意到线段树的底下几层很浪费空间，于是若节点的长度小于一个阈值 $L$ 时，就直接暴力处理.

$b$ 和 $L$ 需要根据自己的代码情况调，笔者取的是 $b=32,L=32$.

还有其他细节需要注意：

• 线段树节点不要存 $l,r$，容易被卡.
• 底层暴力时处理插入时，不要给新插入的元素错误地打上标记.
• 区间的元素不再是 $r-l+1$ 个，需要维护 $\text{cnt}$ 表示元素个数.
• 由于所有线段树底层共用一个 $a$，需要先判断是否在本块范围内再操作.

Code

$6.83\text{KB},4.37\text{s},12.50\text{MB}\text{(in total, C++20 with O2)}$
只给主要部分.

namespace block {struct data {i64 sum;int max, min, cnt;inline data() : sum(0), max(0), min(inf), cnt(0) {}inline data(i64 _sum, int _max, int _min, int _cnt): sum(_sum), max(_max), min(_min), cnt(_cnt) {}};inline data operator+(const data& a, const data& b) {return data(a.sum + b.sum,std::max(a.max, b.max),std::min(a.min, b.min),a.cnt + b.cnt);}inline int ls(int u) { return 2 * u + 1; }inline int rs(int u) { return 2 * u + 2; }struct segment_tree {int n, bl, br;vector<data> info;vector<int> tag;vector<int>::iterator a;vector<bool>::iterator fall;inline segment_tree() {}inline void init(int _n, int _bl, int _br) {n = _n, bl = _bl, br = _br;const int cap = std::max(1, n >> 3);info.resize(cap), tag.resize(cap);}inline void leaf_remove(int u, int l, int r, int ql, int qr, int v, vector<int>& trash) {data res;for (int i = l; i <= r; i++)if (bl <= a[i] && a[i] <= br) {a[i] -= tag[u];if (ql <= i && i <= qr && a[i] > v) {a[i] -= v;if (a[i] < bl) {trash.push_back(i);fall[i] = true;continue;}}res = res + data(a[i], a[i], a[i], 1);}info[u] = res;tag[u] = 0;}inline void leaf_insert(int u, int l, int r) {data res;for (int i = l; i <= r; i++)if (bl <= a[i] && a[i] <= br) {if (!fall[i]) a[i] -= tag[u];else fall[i] = false;res = res + data(a[i], a[i], a[i], 1);}info[u] = res;tag[u] = 0;}inline data leaf_query(int u, int l, int r, int ql, int qr) {data res;for (int i = l; i <= r; i++)if (bl <= a[i] && a[i] <= br) {a[i] -= tag[u];if (ql <= i && i <= qr)res = res + data(a[i], a[i], a[i], 1);}tag[u] = 0;return res;}inline void pushup(int u) {info[u] = info[ls(u)] + info[rs(u)];}inline void apply(int u, int k) {tag[u] += k;info[u].sum -= 1LL * info[u].cnt * k;info[u].max -= k, info[u].min -= k;}inline void pushdown(int u) {if (tag[u]) {apply(ls(u), tag[u]);apply(rs(u), tag[u]);tag[u] = 0;}}void build(int u, int l, int r) {if (r - l < L) return void(info[u] = leaf_query(u, l, r, l, r));const int mid = (l + r) >> 1;build(ls(u), l, mid);build(rs(u), mid + 1, r);pushup(u);}void insert(int u, int l, int r, int i) {if (r - l < L) return leaf_insert(u, l, r);const int mid = (l + r) >> 1;pushdown(u);if (i <= mid) insert(ls(u), l, mid, i);else insert(rs(u), mid + 1, r, i);pushup(u);}void modify(int u, int l, int r, int ql, int qr, int v, vector<int>& trash) {if (info[u].max <= v) return;if (ql <= l && r <= qr && info[u].min - v >= bl) return apply(u, v);if (r - l < L) return leaf_remove(u, l, r, ql, qr, v, trash);const int mid = (l + r) >> 1;pushdown(u);if (ql <= mid) modify(ls(u), l, mid, ql, qr, v, trash);if (qr > mid) modify(rs(u), mid + 1, r, ql, qr, v, trash);pushup(u);}data query(int u, int l, int r, int ql, int qr) {if (ql <= l && r <= qr) return info[u];if (r - l < L) return leaf_query(u, l, r, ql, qr);const int mid = (l + r) >> 1;pushdown(u);if (qr <= mid) return query(ls(u), l, mid, ql, qr);else if (ql > mid) return query(rs(u), mid + 1, r, ql, qr);else return query(ls(u), l, mid, ql, qr) + query(rs(u), mid + 1, r, ql, qr);}inline void insert(int i) {insert(0, 0, n - 1, i);}inline void subtract(int l, int r, int v, vector<int>& trash) {modify(0, 0, n - 1, l, r, v, trash);}inline data query(int l, int r) {return query(0, 0, n - 1, l, r);}inline void build() {build(0, 0, n - 1);}};struct blocks {int n;vector<segment_tree> sgt;vector<int> trash;vector<bool> fall;vector<int>::iterator a;inline blocks() {}inline blocks(int _n) : n(_n) {}inline void init(vector<int>& a) {sgt.resize(B + 1);fall.resize(n);for (int j = 0; j <= B; j++) {const int bl = 1 << (j * B);const int br = (1 << ((j + 1) * B)) - 1;sgt[j].init(n, bl, br);sgt[j].a = a.begin();sgt[j].fall = fall.begin();sgt[j].build();}this->a = a.begin();}inline void subtract(int l, int r, int x) {for (int j = 0; j <= B; j++) {sgt[j].subtract(l, r, x, trash);if (j > 0) {for (auto i : trash) for (int k = 0; k < j; k++)if (sgt[k].bl <= a[i] && a[i] <= sgt[k].br) {sgt[k].insert(i);break;}trash.clear();}}}inline data query(int l, int r) {data res;for (int j = 0; j <= B; j++) res = res + sgt[j].query(l, r);return res;}};
}