题解 [email protected]洛谷 【[Ynoi2011]初始化】

这是我以前做的第一道由乃题(到写作时也是唯一一道),写篇题解纪念一下。

看到由乃题应该想到什么?

  • 分块
  • 卡常

思路:

我们考虑分块维护块内的和。

本题难点主要在修改操作:

  • 操作一:将编号为 y,y+x,y+2×x,,y+k×xy,y+x,y+2\times x,\cdots,y+k\times x 的星星亮度增加 zz

对于 xSIZEx\ge\operatorname{SIZE}SIZE\operatorname{SIZE} 是块的大小,约为 n\sqrt{n}),由于需要修改的位置不超过块数(约为 n\sqrt{n}),我们直接暴力修改即可。

对于 x<SIZEx\lt\operatorname{SIZE},我们不能直接修改,考虑其他方法:

因为亮度变化在整个星星序列内是周期性的,我们可以统计长度为 xx 的周期中,每一个位置的累计修改总和。但是这种方法在查询的时候耗费时间极多,因此我们需要优化。容易想到通过前后缀和可以解决单点改、区间查的问题,我们统计修改的前后缀和即可。

  • 操作二:查询 ilrai\displaystyle\sum_{i-l}^ra_i,其中 aia_i 表示亮度。

对于两侧的不完整块,我们直接暴力统计即可。

对于中间的完整块,我们按照块来统计即可。

等等,不要忘记前面统计的前后缀和!在得到按块统计的结果后,我们需要将结果加上对于每一个周期长度,根据前后缀和统计出的累计修改总和


简单总结:

我们需要维护原数组、分块数组和周期短前后缀和,修改时修改块或者周期的前后缀和,查询时统计两侧不完整块、中间完整块和不同周期在查询区间内的修改总和即可。


然后就是漫长的卡常数过程,我在第 8989 次才卡常成功,主要是一直用 C++,别人告诉我 C++11 更快,才去试的。

由于卡常原因,码风可能与我的正常码风有一些不同,敬请谅解。

主要代码:

#define whichBlock(x) (\
	(x - 1) / SIZE + 1\
)
inline void initBlock() {
	tot = whichBlock(n);
	for(register int i=1;i<=tot;++i) {
		l[i] = r[i-1] + 1;
		r[i] = i * SIZE;
	}
	r[tot] = n;
}
inline int sumBlock(register int x, register int y) {
	register const int X = whichBlock(x), Y = whichBlock(y);
	register int res = 0;
	if(X == Y) {
		for(register int i=x;i<=y;++i) res = (res + a[i]) % mod;
	}
	else {
		for(register int i=x;i<=r[X];++i) res = (res + a[i]) % mod;
		for(register int i=X+1;i<=Y-1;++i) res = (res + s[i]) % mod;
		for(register int i=l[Y];i<=y;++i) res = (res + a[i]) % mod;
	}
	return res;
}
inline void modify(register int x, register int y, register int z=read()) {
	if(x >= SIZE) {
		for(register int i=y;i<=n;i+=x) {
			register const int _ = whichBlock(i);
			a[i] = (a[i] + z) % mod;
			s[_] = (s[_] + z) % mod;
		}
	}
	else {
		for(register int i=y;i<=x;++i) pre[x][i] = (pre[x][i] + z) % mod;
		for(register int i=1;i<=y;++i) suf[x][i] = (suf[x][i] + z) % mod;
	}
}
inline int query(register int x, register int y) {
	register int res = sumBlock(x, y);
	for(register int i=1;i<SIZE;++i) {
		register const int X = (x - 1) / i + 1, Y = (y - 1) / i + 1;
		register const int L = Y - X - 1;
		if(X == Y) res = (res - pre[i][(x-1)%i] + pre[i][(y-1)%i+1]) % mod;
		else res = (res + 1LL * L * pre[i][i] + pre[i][(y-1)%i+1] + suf[i][(x-1)%i+1]) % mod;
	}
	return (res+mod)%mod;
}