分块练习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;

}

巴特西

分块练习C. interval

分块练习C. interval

题目描述

输入格式

输出格式

样例

样例输入

样例输出

数据范围与提示

分析

代码

最新文章

热门文章