LOJ6277 数列分块入门 1

题面

给出一个长为 \(n\) 的数列，以及 \(n\) 个操作，操作涉及区间加法，单点查值。

$ 1\le n \le 50000$。数据在 int 范围内。

思路

分块模板题。

先对数列分成 \(\sqrt{n}\) 块，然后查询就是数据+ tag，但是更新怎么办呢？

先对非整块直接暴力修改，然后再整块累加即可。

时间复杂度

分块 \(O(n)\)。

查询 \(O(1)\)。

修改 \(O(\sqrt{n})\)。

总时间复杂度 \(O(n\sqrt{n})\)。

代码

AC 提交记录

#include 
using namespace std;

int n;
int block;
int v[50005];
int ba[50005];
int tag[50005];

void update(int a, int b, int c) {
    for (int i = a; i <= min(ba[a]*block, b); i++) {
        v[i] += c;
    }

    if (ba[a] != ba[b]) {
        for (int i = (ba[b] - 1) * block + 1; i <= b; i++) {
            v[i] += c;
        }
    }

    for (int i = ba[a] + 1; i <= ba[b] - 1; i++) {
        tag[i] += c;
    }
}

int query(int y) {
    return v[y] + tag[ba[y]];
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    cin >> n;

    for (int i = 1; i <= n; i++) {
        cin >> v[i];
    }

    block = sqrt(n);

    for (int i = 1; i <= n; i++) {
        ba[i] = (i - 1) / block + 1;
    }

    for (int i = 1; i <= n; i++) {
        int op, x, y, z;
        cin >> op >> x >> y >> z;

        if (op == 0) {
            update(x, y, z);
        } else {
            cout << query(y) << endl;
        }
    }

    return 0;
}