题解 P5309 【[Ynoi2011]初始化】

· · 题解

这是我当时做时候Ynoi第一血，发一篇题解。

知识点：

给你一个序列，让你维护区间和还有区间下表为 y,x,2x,3x...kx 的数加 z。

  1. 如果 x \ge \sqrt n，也就是说 x 大于等于块长，那么可以暴力修改。因为如果 x 大于等于根号n，那么跳的次数会小于等于 \sqrt n。换句话说，这个操作的复杂度就不会超过 O(\sqrt n)。

  2. 如果 x \lt \sqrt n，我们就以 x 为跳的周期，每个点统计累计修改总和。Ynoi题肯定会有一个地方卡你，而在这道题中，刚刚这种方法就太慢了。为了优化，我们采用前缀后缀统计方法。

所以根据情况，选择统计块、前缀后缀和。

  1. 暴力求两边不完整块。

  2. 根据块统计，然后加对应每个周期的前后缀累计修改和。

则统计完整和不完整块中的前缀后缀求改总和。

  1. 这道题不用卡常，我加了一个 ios::sync_with_stdio(0); 然后就用cin cout过了。

  2. 需要模数的地方一定要模好，减完数时候千万不要模，在求和的时候要把式子合起来，要不然会炸int。

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;

#define MOD 1000000007

//#define int long long

const int MAXN = 200005;

int block, L[MAXN], R[MAXN], num, n, m, a[MAXN], sum[MAXN], pre[500][500], suf[500][500];

/* num：块的个数
 * pre，suf 前缀后缀和
 * block：每块的大小
 * L[i]：i这块左端点的位置
 * R[i]：i这块右端点的位置 */

inline int blockpos(int i) {
    return (i - 1) / block + 1;
}

inline void update(int x, int y, int z) {
    if (x >= block) { // 跳的长度大于块长，复杂度也是sqrt(n)
        for (int i = y; i <= n; i += x) {
            int cur = blockpos(i);
            a[i] += z;
            a[i] %= MOD;
            sum[cur] += z;
            sum[cur] %= MOD;
        }
        return;
    }
    for (int i = y; i <= x; ++i) {
        pre[x][i] += z;
        pre[x][i] %= MOD;
    }
    for (int i = 1; i <= y; ++i) {
        suf[x][i] += z;
        suf[x][i] %= MOD;
    }
}

inline int block_sum(int l, int r) {
    int Ll = blockpos(l), Rr = blockpos(r), ans = 0;
    if (Ll == Rr) {
        for (int i = l; i <= r; ++i) {
            ans += a[i];
            ans %= MOD;
        }
        return ans;
    }
    for (int i = l; i <= R[Ll]; ++i) {
        ans += a[i];
        ans %= MOD;
    }
    for (int i = L[Rr]; i <= r; ++i) {
        ans += a[i];
        ans %= MOD;
    }
    for (int i = Ll + 1; i < Rr; ++i) {
        ans += sum[i];
        ans %= MOD;
    }
    return ans;
}

inline int query_sum(int l, int r) {
    int bsum = block_sum(l, r);
    for (int i = 1; i < block; ++i) {
        int Ll = (l - 1) / i + 1, Rr = (r - 1) / i + 1;
        if (Ll == Rr) {
            bsum -= pre[i][(l - 1) % i];
            bsum += pre[i][(r - 1) % i + 1];
            bsum %= MOD;
        } else {
            bsum = (bsum + 1LL * (Rr - Ll - 1) * pre[i][i] + pre[i][(r - 1) % i + 1] + suf[i][(l - 1) % i + 1]) % MOD;
        }
    }
    return (bsum + MOD) % MOD;
}

void solve() {
    ios::sync_with_stdio(0);
    cin >> n >> m;
    for (int i = 1; i <= n; ++i) {
        cin >> a[i];
    }
    block = sqrt(n);
    num = n / block; //求块的个数
    if (n % block) num++;
    for (int i = 1; i <= num; ++i) L[i] = R[i - 1] + 1, R[i] = i * block;
    R[num] = n;
    for (int i = 1; i <= num; ++i) {
        for (int j = L[i]; j <= R[i]; ++j) {
            sum[i] += a[j];
            sum[i] %= MOD;
        }
    }
    while (m--) {
        int op;
        cin >> op;
        if (op == 1) {
            int x, y, z;
            cin >> x >> y >> z;
            update(x, y, z);
            /*for (int i = 1; i <= n; ++i) {
                cout << a[i] << ' ';
            }
            cout << "\n";*/
        }
        if (op == 2) {
            int l, r;
            cin >> l >> r;
            cout << query_sum(l, r) << '\n';
        }
    }
}

int main() {
    solve();
    return 0;
}