题解 P5309 【[Ynoi2011]初始化】
rui_er
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 更快，才去试的。
由于卡常原因，码风可能与我的正常码风有一些不同，敬请谅解。
主要代码：
```cpp
#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;
}
```