题解 P5309 【[Ynoi2011]初始化】

YLWang · 2020-03-22 10:55:23 · 题解

我们看到这种跳着加 / 统计跳着加和的题目，应该想到的就是根号分治。

还有一种要预处理和查询平衡的题也是根号分治的常见例子。

我们设一个阈值 T，在 x 大于 T 的时候直接暴力修改。这里我们需要一个 O(1) 修改的 ds，那么首选分块了。

问题就在于 x 小于 T 的时候怎么搞。

考虑维护。我们发现序列可以抽象成一些大小为 x 的段。

显然中间完整的段一定会被所有含 x 的操作修改，两边的小段会被部分修改。

一条条线段就是分出来的长度为 x 的段。橙色的线是查询的两端。

我们可以用一个数组 v(x, y) 表示修改的时候 (x, y) 位置上的权值和。再记录一个前缀和和后缀和就可以快速查询了。

const int MAXN = 200005;
const int MAXB = 505;
int a[MAXN], bel[MAXN], n, m, bn = 0, S, T;
int L[MAXB], R[MAXB], sum[MAXB];
int pre[MAXB][MAXB], suf[MAXB][MAXB];
void init() {
    for(rint tL = 1, tR; tL <= n; tL = tR + 1) {
        tR = tL + S - 1; ckmin(tR, n);
        L[++bn] = tL, R[bn] = tR;
        For(i, tL, tR) bel[i] = bn, addmod(sum[bn], a[i]); 
    }
    mst(pre, 0); mst(suf, 0);
}
int query(int l, int r) {
    int bl = bel[l], br = bel[r], res = 0;
    if(bl == br) {
        For(i, l, r) addmod(res, a[i]);
    } else {
        For(i, l, R[bl]) addmod(res, a[i]);
        For(i, L[br], r) addmod(res, a[i]);
        For(i, bl+1, br-1) addmod(res, sum[i]);
    }
    For(x, 1, min(T, n)) {
        bl = (l - 1) / x + 1, br = (r - 1) / x + 1;
        if(bl == br) {
            addmod(res, pre[x][r-(br-1)*x]);
            addmod(res, P-pre[x][l-1-(bl-1)*x]);
        } else {
            addmod(res, 1ll * pre[x][x] * (br - bl - 1) % P);
            addmod(res, pre[x][r-(br-1)*x]);
            addmod(res, suf[x][l-(bl-1)*x]);
        }

    }
    return res % P;
}
signed main()
{
    cin >> n >> m; S = pow(n, 0.5); T = 60;
    For(i, 1, n) a[i] = read() % P;
    init();
    while(m--) {
        int op = read(), x = read(), y = read(), z;
        if(op == 1) {
            z = read() % P;
            if(x <= T) {
                For(i, y, x) addmod(pre[x][i], z);
                foR(i, y, 1) addmod(suf[x][i], z);
            } else {
                for(rint i = y; i <= n; i += x)
                    addmod(a[i], z), addmod(sum[bel[i]], z);
            }
        } else {
            printf("%d\n", query(x, y));
        }
    }
    return 0;
}