题解 P5309 【[Ynoi2011]初始化】

· · 题解

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

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

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

思路：

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

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

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

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

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

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

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

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

简单总结：

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

然后就是漫长的卡常数过程，我在第 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;
}