分塊練習C. interval

2020 年 8 月 22 日
筆記
數據結構--分塊

分塊練習C. interval

題目描述

$N$個數$a_i$，$m$個操作

$1$．從第一個數開始，每隔$k_i$個的位置上的數增加$x_i$

$2$．查詢$l$到$r$的區間和

輸入格式

第一行兩個整數$n$，$m$

第二行$n$個數，$a_i$

接下來$m$行，每行三個整數，$a$，$b$，$c$

如果$a=1$，表示修改操作

否則表示查詢 $b$到$c$的區間和

輸出格式

依次輸出每個查詢

樣例

樣例輸入

10 6
5 1 4 2 3 6 4 1 2 3
1 2 4
2 6 8
1 1 4
2 3 6
1 5 4
2 2 9

樣例輸出

15
27
51

數據範圍與提示

數據均隨機生成，保證合法

對於$50\%$的數據 $n,m<=10000$

對於$100\%$的數據,$n,m<=100000$

分析

由於數據水到一定境界，所以暴力即可通過本題

但是，懷著務實求真的心態，我們還是要探究一下本題的分塊解法

分塊的核心是大段維護，局部樸素

因此我們考慮怎麼對一個大段整體打上標記

題目中的修改操作是每間隔固定的長度加上一個值

因此我們可以對每一個塊開一個$vector$記錄每次修改時該塊內被改動的第一個元素，改動的間隔以及增加的價值

對於間隔小於 $ \sqrt{n} $的修改，我們用上面的方式去打標記

對於間隔大於 $\sqrt{n} $的修改，我們暴力去維護會更優

查詢時，我們將區間兩端的散點，暴力去加，同時把標記下放

對於中間的大區間，我們直接維護一個$sum$加上即可

程式碼

#include <cstdio>
#include <cmath>
#include <algorithm>
#include <vector>
const int maxn = 1e5 + 5;
inline int read() {
    int x = 0, f = 1;
    char ch = getchar();
    while (ch < '0' || ch > '9') {
        if (ch == '-')
            f = -1;
        ch = getchar();
    }
    while (ch >= '0' && ch <= '9') {
        x = (x << 1) + (x << 3) + (ch ^ 48);
        ch = getchar();
    }
    return x * f;
}
int n, m, shuyu[maxn], blo, sum[maxn], a[maxn];
struct asd {
    int wz, ad, jz;
    asd() {}
    asd(int aa, int bb, int cc) { wz = aa, ad = bb, jz = cc; }
};
std::vector<asd> g[maxn];
void xg(int jg, int val) {
    if (jg >= blo) {
        for (int i = 1; i <= n; i += jg) {
            a[i] += val;
            sum[shuyu[i]] += val;
        }
    } else {
        int beg = 1;
        for (int i = 1; i <= shuyu[n]; i++) {
            if (shuyu[beg] == i && beg <= n)
                g[i].push_back(asd(beg, jg, val));
            int ed = std::min(i * blo, n);
            int cz = (ed - beg) / jg;
            sum[i] += (cz + 1) * val;
            beg += (cz + 1) * jg;
        }
    }
}
void qk(int id) {
    for (int i = 0; i < g[id].size(); i++) {
        int beg = g[id][i].wz, jg = g[id][i].ad, val = g[id][i].jz;
        for (int j = beg; j <= id * blo; j += jg) {
            a[j] += val;
        }
    }
    g[id].clear();
}
int cx(int l, int r) {
    int ans = 0;
    qk(shuyu[l]);
    for (int i = l; i <= std::min(r, shuyu[l] * blo); i++) {
        ans += a[i];
    }
    if (shuyu[l] == shuyu[r])
        return ans;
    qk(shuyu[r]);
    for (int i = r; i >= (shuyu[r] - 1) * blo + 1; i--) {
        ans += a[i];
    }
    for (int i = shuyu[l] + 1; i <= shuyu[r] - 1; i++) {
        ans += sum[i];
    }
    return ans;
}
int main() {
    n = read(), m = read();
    blo = sqrt(n);
    for (int i = 1; i <= n; i++) {
        a[i] = read();
        shuyu[i] = (i - 1) / blo + 1;
        sum[shuyu[i]] += a[i];
    }
    for (int i = 1; i <= m; i++) {
        int aa, bb, cc;
        aa = read(), bb = read(), cc = read();
        if (aa == 1) {
            bb++;
            xg(bb, cc);
        } else {
            printf("%d\n", cx(bb, cc));
        }
    }
    return 0;
}

Tags: 數據結構--分塊