【题解】P4117 [Ynoi2018] 五彩斑斓的世界

题意

P4117 [Ynoi2018] 五彩斑斓的世界

给定一个长度为 \(n\) 的序列和 \(m\) 个操作,每次操作可以:

  1. 将区间 \([l, r]\) 中所有大于 \(x\) 的值减去 \(x\)

  2. 询问区间 \([l, r]\) 中值 \(x\) 的出现次数

\(1 \leq n \leq 10^6, 1 \leq m \leq 5 \times 10^5, 1 \leq l \leq r \leq n, 0 \leq a_i, x \leq 10^5 + 1\)

思路

前置知识

第二分块。

分块 + 逐块处理 + 并查集。

设 \([l, r]\) 中最大值为 \(k\)。第一种操作可以转化为两种形式:

  1. \(2 \times x \leq k\),将值域在 \([0, x]\) 中的值全部加上 \(x\),之后给区间整体打上减法标记

  2. \(2 \times x > k\),将值域在 \([x + 1, k]\) 中的值全部减去 \(x\)

这里可以考虑用并查集维护。我们对于每一个值 \(x\) 都维护一个下标的并查集,则我们需要维护:

  1. 值 \(i\) 对应并查集的根 \(rt_i\)

  2. 并查集的根 \(i\) 对应的值 \(val_i\)

  3. 并查集的大小

则修改时整块直接合并两个值对应的并查集,散块直接暴力修改并重构。询问时整块直接统计并查集大小,散块则暴力统计。

当块长取 \(\sqrt{n}\) 时,该做法的空间复杂度为 \(\mathcal{O}(n \sqrt{n})\),会 \(MLE\)

考虑逐块处理,统计每个块对 \(m\) 个询问的贡献。

对于整块 \(x\),修改时:

  1. 若整块 \(x\) 被 \([l, r]\) 完全覆盖,直接合并值对应的并查集

  2. 若整块 \(x\) 未被 \([l, r]\) 完全覆盖,暴力修改并重构该整块

查询时:

  1. 若整块 \(x\) 被 \([l, r]\) 完全覆盖,直接统计并查集大小

  2. 若整块 \(x\) 未被 \([l, r]\) 完全覆盖,暴力统计

这样只用开单块需要的空间,空间复杂度为 \(\mathcal{O}(n)\)

显然整块经过若干次减法修改后值域不断缩小,当值域大小为 \(v\) 时,枚举的值域是 \(\mathcal{O}(v)\) 的。

由于我们只关心并查集根的 \(size\),所以可以进行路径压缩。路径压缩后并查集合并复杂度为 \(\mathcal{O}(1)\),查询复杂度为 \(\mathcal{O}(\log n)\)

所以时间复杂度为 \(\mathcal{O}(\sqrt{n}m + v \sqrt{n} \log n)\)

代码需要略微优化。快读快写套 inline,当前整块与询问区间无交集时不查询,值域上限减去标记后小于 \(x\) 不查询。

代码

#include <cstdio>
#include <cmath>
#include <cstring>
#include <algorithm>
using namespace std;

const int maxn = 1e6 + 5;
const int maxq = 5e5 + 5;
const int maxv = 1e5 + 5;
const int inf = 2147483647;

struct node {
	int opt, l, r, x;
} q[maxq];

int n, m;
int st, ed, cur, lazy;
int a[maxn], val[maxn], fa[maxn], size[maxn];
int rt[maxv];
int ans[maxq];

inline int read() {
	int res = 0;
	char ch = getchar();
	while ((ch < '0') || (ch > '9')) {
		ch = getchar();
	}
	while ((ch >= '0') && (ch <= '9')) {
		res = res * 10 + ch - '0';
		ch = getchar();
	}
	return res;
}

inline void write(int x) {
	if (x > 9) {
		write(x / 10);
	}
	putchar(x % 10 + '0');
}

inline int get(int x) {
	if (fa[x] == x) {
		return x;
	}
	return fa[x] = get(fa[x]);
}

inline void merge(int x, int y) {
	if (rt[y]) {
		fa[rt[x]] = rt[y];
	} else {
		rt[y] = rt[x];
		val[rt[x]] = y;
	}
	size[y] += size[x];
	rt[x] = size[x] = 0;
}

inline void init() {
	cur = -inf, lazy = 0;
	memset(rt, 0, sizeof(rt));
	memset(size, 0, sizeof(size));
}

inline void build(int pos) {
	cur = -inf, lazy = 0;
	for (int i = st; i <= ed; i++) {
		cur = max(cur, a[i]);
		if (!rt[a[i]]) {
			val[i] = a[i];
			fa[i] = i;
			rt[a[i]] = i;
		} else {
			fa[i] = rt[a[i]];
		}
		size[a[i]]++;
	}
}

inline void modify(int l, int r, int x, int pos) {
	for (int i = st; i <= ed; i++) {
		int w = val[get(i)];
		a[i] = w - lazy;
		rt[w] = size[w] = 0;
	}
	for (int i = st; i <= ed; i++) {
		val[i] = 0; 
	}
	l = max(l, st);
	r = min(r, ed);
	for (int i = l; i <= r; i++) {
		if (a[i] > x) {
			a[i] -= x;
		}
	}
	build(pos);
}

inline void update(int x) {
	if ((x << 1) <= (cur - lazy)) {
		for (int i = lazy; i <= x + lazy; i++) {
			if (rt[i]) {
				merge(i, i + x);
			}
		}
		lazy += x;
	} else {
		for (int i = cur; i > lazy + x; i--) {
			if (rt[i]) {
				merge(i, i - x);
			} 
		}
		cur = min(cur, x + lazy);
	}
}

inline int query(int l, int r, int x) {
	int res = 0;
	l = max(l, st);
	r = min(r, ed);
	for (int i = l; i <= r; i++) {
		if (val[get(i)] - lazy == x) {
			res++;
		}
	}
	return res;
}

int main() {
	int opt, l, r, x;
	n = read(), m = read();
	int block = sqrt(n);
	int tot = ceil(n * 1.0 / block);
	for (int i = 1; i <= n; i++) {
		a[i] = read();
	}
	for (int i = 1; i <= m; i++) {
		q[i].opt = read(), q[i].l = read(), q[i].r = read(), q[i].x = read();
	}
	for (int i = 1; i <= tot; i++) {
		init();
		st = (i - 1) * block + 1;
		ed = (i == tot ? n : i * block);
		build(i);
		for (int j = 1; j <= m; j++) {
			if ((q[j].l > ed) || (q[j].r < st)) {
				continue;
			}
			if (q[j].opt == 1) {
				if ((q[j].l <= st) && (ed <= q[j].r)) {
					update(q[j].x);
				} else {
					modify(q[j].l, q[j].r, q[j].x, i);
				}
			} else {
				if (q[j].x + lazy > 1e5 + 1) {
					continue;
				}
				if ((q[j].l <= st) && (ed <= q[j].r)) {
					ans[j] += size[q[j].x + lazy];
				} else {
					ans[j] += query(q[j].l, q[j].r, q[j].x);
				}
			}
		}
	}
	for (int i = 1; i <= m; i++) {
		if (q[i].opt == 2) {
			write(ans[i]);
			putchar('\n');
		}
	}
	return 0;
}
上一篇:CSS – Display block, inline, inline-block


下一篇:OkHttp工具类封装,更优雅的调用接口