自动搬运

查看原文

来自洛谷，原作者为

	rui_er 九万里风鹏正举

搬运于2025-08-24 22:09:22，当前版本为作者最后更新于2020-09-06 16:02:41，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

（update 2020.9.6：修错别字及公式错误，望通过）

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

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

• 分块
• 卡常

思路：

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

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

• 操作一：将编号为 $y,y+x,y+2\times x,\cdots,y+k\times x$ 的星星亮度增加 $z$。

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

对于 $x\lt\operatorname{SIZE}$，我们不能直接修改，考虑其他方法：

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

• 操作二：查询 $\displaystyle\sum_{i=l}^ra_i$，其中 $a_i$ 表示亮度。

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

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

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

简单总结：

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

然后就是漫长的卡常数过程，我在第 $89$ 次才卡常成功，主要是一直用 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;
}