专栏文章

题解：P14316 [Aboi Round 2] 礎の花冠

jj23wuyifan
P14316题解参与者 1已保存评论 0

文章操作

快速查看文章及其快照的属性，并进行相关操作。

当前评论
0 条
当前快照
1 份
快照标识符
@min2z4vb
此快照首次捕获于
2025/12/01 19:43
3 个月前
此快照最后确认于
2025/12/01 19:43
3 个月前
查看原文
感觉挺牛的数据结构题，至少我不会。。
先将询问离线下来，按照 rr 做扫描线。维护一个数组 numinum_i 表示商为 ii 的最大的 ll。答案就是 numi≥lnum_i \ge l 的 ii 的个数。商为 00 的需要特判一下。考虑从 r−1r-1 到 rr 对 numnum 数组的影响。
对于 ax≤ara_x \le a_r，不难想到用整除分块维护。查询所有与 ara_r 的商相同的 axa_x 最大的 xx 更新 numnum 数组。我们需要一个支持 O(1)O(1) 查询区间最大值，O(n)O(\sqrt{n}) 单点修改的数据结构。O(1)O(1) 修改 O(n)O(\sqrt{n}) 查询只能分块，又要查询最大值，不难想到对于每个块维护一个 st 表。修改会被影响的点，时间是 ∑i=0⌊log⁡2n⌋2i=O(n)\sum_{i=0}^{\left \lfloor \log_2 \sqrt{n} \right \rfloor} 2^i = O(\sqrt{n})。
对于整块查询直接暴力查询整块最大值即可，因为查询合起来是 11 到 VV 的，总共只有 O(n)O(\sqrt{n}) 个整块，所以均摊是 O(1)O(1) 的。
对于 ax>ara_x > a_r 的，对 ara_r 根号分治。若 ar>Ba_r > B，直接暴力枚举 ⌊axar⌋{\left \lfloor \frac{a_x}{a_r} \right \rfloor} 的商更新答案。若 ar≤Ba_r \le B，只需要枚举上一个 ara_r 出现的位置到 rr 的数都除以 ara_r 更新答案。
最后就是对于 numnum 数组求答案：当 numnum 数组有变化时，再开个值域分块维护一下，O(n)O(\sqrt{n}) 查询可以接受。
卡常的话主要是跟官方题解一样把整除分块的常数卡一卡。代码应该不难写，还是放一下吧。
CPP
inline int qrymx(int id, int l, int r) {
	const int len = lg[r - l + 1];
	return max(st[id][len][l], st[id][len][r - (1 << len) + 1]);
}
inline int qry(int l, int r) {
	const int bl = pos[l], br = pos[r];
	if (bl == br)return qrymx(bl, l - L[bl] + 1, r - L[bl] + 1);
	int ans = max(qrymx(bl, l - L[bl] + 1, R[bl] - L[bl] + 1), qrymx(br, 1, r - L[br] + 1));
	for (int i = pos[l] + 1; i < pos[r]; i ++) ans = max(ans, mx[i]);
	return ans;
}
inline void updmx(int x, int v) {
	//更新st表
	const int bl = pos[x], y = x - L[bl] + 1, len = R[bl] - L[bl] + 1;
	st[bl][0][y] = v;
	for (int i = 1; i <= lg[len]; i ++) {
		for (int j = max(y - (1 << i) + 1, 0), lim = min(y, len - (1 << i) + 1); j <= lim; j ++)
			st[bl][i][j] = max(st[bl][i - 1][j], st[bl][i - 1][j + (1 << i - 1)]);
	}
	mx[bl] = qrymx(bl, 1, len);
}
int mn[N], sum1[N], sum2[N];
int pos2[N], block2, tot2, L2[N], R2[N];
inline void updsum(int x, int v) {
	if (mn[x] < v) sum1[mn[x]] --, sum2[pos2[mn[x]]] --, mn[x] = v, sum1[v] ++, sum2[pos2[v]] ++;
}
inline int qrysum(int r) {
	int ans = 0;
	for (int i = r; i <= R2[pos2[r]]; i ++)ans += sum1[i];
	for (int i = pos2[r] + 1; i <= tot2; i ++)ans += sum2[i];
	return ans;
}
int ql[N], qr[N], ans[N];
vector<int> vec[N];
signed main() {
	read(n), read(m);
	int mx = 0;
	for (int i = 1; i <= n; i ++)read(a[i]), mx = max(mx, a[i]);
	block = sqrt(mx);
	tot = (mx + block - 1) / block;
	L[1] = 1, R[tot] = mx;
	for (int i = 2; i <= tot; i ++)L[i] = min(L[i - 1] + block, mx);
	for (int i = 1; i < tot; i ++) R[i] = L[i + 1] - 1;
	for (int i = 1; i <= tot; i ++)
		for (int j = L[i]; j <= R[i]; j ++)pos[j] = i;
	block2 = sqrt(n);
	tot2 = (n + block2 - 1) / block2;
	L2[1] = 1, R2[tot2] = n;
	for (int i = 2; i <= tot2; i ++)L2[i] = min(L2[i - 1] + block2, n);
	for (int i = 1; i < tot2; i ++) R2[i] = L2[i + 1] - 1;
	for (int i = 1; i <= tot2; i ++)
		for (int j = L2[i]; j <= R2[i]; j ++)pos2[j] = i;
	lg[1] = 0;
	for (int i = 2; i < N; i ++)lg[i] = lg[i >> 1] + 1;
	nxt[n] = n;
	for (int i = n - 1; i >= 1; i --)nxt[i] = a[i] == a[i + 1] ? nxt[i + 1] : i;
	for (int i = 1; i <= m; i ++) {
		read(ql[i]), read(qr[i]);
		vec[qr[i]].push_back(i);
		ans[i] = nxt[ql[i]] < qr[i];
	}
	for (int i = 1; i <= n; i ++) {
		const int v = a[i], sq = sqrt(v);
		updmx(v, i);
		for (int j = 1, pre = v, now; j <= sq; j ++)
			updsum(j, qry(now = v / (j + 1) + 1, pre)), pre = now - 1;
		for (int j = 1; j <= sq; j ++)
			updsum(v / j, st[pos[j]][0][j - L[pos[j]] + 1]);
		if (v > block) for (int j = v, k = 1; j <= mx; j += v, k ++)updsum(k, qry(j, min(j + v - 1, mx)));
		else {
			for (int j = lst[v] + 1; j <= i; j ++)if (a[j] >= v)updsum(a[j] / v, j);
			lst[v] = i;
		}
		for (int x : vec[i])ans[x] += qrysum(ql[x]);
	}

评论

共 0 条评论，欢迎与作者交流。

正在加载评论...