题解：P13826 [Ynoi Easy Round 2026] 寒蝉鸣泣之时

Easy Round 还是比较善良的

题目相当于是矩形加，求有多少个点值为

x

，

x

是

m

的倍数。

首先这东西是无法直接做的，考虑将矩阵加离线下来做扫描线。那么有

n

次区间加，

\frac{n^2}{m}

次查询，可以联想到分块，但是发现单次

O(1)

并不好做，我自己就只能想到这了。

看了其他题解后，我们可以转换思路，发现可以不对每个

m

的倍数

x

查询答案，而是在散块修改时对每个块重构统计答案。但我们又发现了一个问题，因为单次暴力重构是

O(\frac{n}{m}\sqrt{n})=O(n)

的，而我们每次散块修改都要重构，散块会修改

n

次，所以一共会重构

n

次，时间复杂度就炸了。但我们发现真正可能会对答案产生贡献的

x

其实很少，我们可以维护一个块的最大最小值，

x

一定在这个范围内。

设

k

为区间最大值减区间最小值，我们此时重构一次的复杂度时

O(\frac{k}{m}\sqrt{n})=O(k)

。对于每个块，因为操作只有加减

1

，所以一个块内的极差最大只有

n

，因此总的复杂度时

O(n\sqrt{n})

的。

到这里思路就讲完了，但是 Ynoi 的题是不会让你这么轻松的通过的。直接开

n\sqrt{n}

的数组空间会不够用，但不会超很多，而逐块处理又会被卡常。这里就有两种做法，一种是可以开一个 short 和一个 char 用来代替 int，是够表示的。或者分成几次处理，可能需要稍微卡卡常数。然后记得最后处理一次。最后放上卡常前的代码。

CPP

inline void rebuild(int x) {
	if (mn[x] <= mx[x]) {
		for (int i = L[x]; i <= R[x]; i ++) {
			//-tag + m * t = v
			//-tag = v - m * t
			//m * r <= v - mn
			//m * l >= v - mx
			int v = a[i];
			for (int j = max(1, (v - mx[x] + m - 1) / m); j <= min(k, (v - mn[x]) / m); j ++) {
				ans[j] += sum[x][N + v - j * m];
			}
		}
		for(int i = mn[x];i <= mx[x];i ++)sum[x][i + N] = 0;
		mx[x] = -inf, mn[x] = inf;
	}
}
inline void add(int l, int r, int x) {
	if (pos[l] == pos[r]) {
		rebuild(pos[l]);
		for (int i = l; i <= r; i ++)a[i] += x;
	} else {
		rebuild(pos[l]);
		rebuild(pos[r]);
		for (int i = l; i <= R[pos[l]]; i ++)a[i] += x;
		for (int i = pos[l] + 1; i <= pos[r] - 1; i ++)tag[i] += x;
		for (int i = L[pos[r]]; i <= r; i ++)a[i] += x;
	}
}
signed main() {
	ios :: sync_with_stdio(0);
	cin.tie(0), cout.tie(0);
	cin >> n >> m;
	block = sqrt(n);
	tot = (n + block - 1) / block;
	L[1] = 1, R[tot] = n;
	for (int i = 2; i <= tot; i ++) L[i] = min(L[i - 1] + block, n);
	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;
	k = n / m;
	for(int i = 1;i <= tot;i ++) mx[i] = -inf,mn[i] = inf;
	for (int i = 1; i <= n; i ++) {
		int a, b, c, d;
		cin >> a >> b >> c >> d;
		E[a].push_back({c, d - 1, 1});
		E[b].push_back({c, d - 1, -1});
	}
	for (int i = 1; i <= n; i ++) {
		for (auto p : E[i])add(p.l, p.r, p.x);
		for (int j = 1; j <= tot; j ++)sum[j][N - tag[j]], mn[j] = min(mn[j], -tag[j]), mx[j] = max(mx[j], -tag[j]);
	}
	for(int i = 1;i <= tot;i ++)rebuild(i);
	//最后记得处理
	for(int i = 1;i <= k;i ++)cout << ans[i] << '\n';
	return 0;
}

题解：P13826 [Ynoi Easy Round 2026] 寒蝉鸣泣之时

文章操作

相关推荐

评论

题解：P13826 [Ynoi Easy Round 2026] 寒蝉鸣泣之时