POJ 3468 A Simple Problem with Integers (分块解法)-蒲公英云

POJ 3468 A Simple Problem with Integers (分块解法)

题意: 输入 n, m表初始有 n 个数, 接下来 m 行输入, Q x y 表示询问区间 [x, y]的和；

C x y z 表示区间 [x, y] 内所有数加上 z 。

分析:

我们将所给序列分成一个一个大小为根号n的块，每次询问时在线处理：

额外用到的数组：

pos[maxn]：pos[i]表示第i个元素属于哪个块。

add[maxn]:add[i]表示第i个块的增量。

sum[maxn]:sum[i]表示第i个块的总和。

L[maxn]:L[i]表示第i个块的左端点。

R[maxn]:R[i]表示第i个块的右端点。

一·询问操作 Q l r ：

1.如果l和r都在一个块内，直接利用朴素算法从a[l]加到a[r]。

2.如果不一样，我们令p=pos[l],q=pos[r],l和r之间完整的块为从p+1到q-1，所以我们累加sum[i]+add*(R[i]-L[i]+1),i从p+1到q-1。

之后我们对于不完整的两端进行朴素处理。

二·改变操作 C l r val:

1.如果l和r都在一个块内，直接利用朴素算法从a[l]改变到a[r]。

2.如果不一样，我们令p=pos[l],q=pos[r],l和r之间完整的块为从p+1到q-1，所以我们改变add[i]+=val,i从p+1到q-1。

之后我们对于不完整的两端进行朴素处理。

总复杂度为O((N+M)*√N)。

代码:

//参考《算法竞赛进阶指南》
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<cmath>
using namespace std;
long long a[100010], sum[100010], add[100010];
int L[100010], R[100010]; // 每段左右端点
int pos[100010]; // 每个位置属于哪一段
int n, m, t;
void change(int l, int r, long long d) {
    int p = pos[l], q = pos[r];
    if (p == q) {
        for (int i = l; i <= r; i++) a[i] += d;
        sum[p] += d*(r - l + 1);
    }
    else {
        for (int i = p + 1; i <= q - 1; i++) add[i] += d;
        for (int i = l; i <= R[p]; i++) a[i] += d;
        sum[p] += d*(R[p] - l + 1);
        for (int i = L[q]; i <= r; i++) a[i] += d;
        sum[q] += d*(r - L[q] + 1);
    }
}
long long ask(int l, int r) {
    int p = pos[l], q = pos[r];
    long long ans = 0;
    if (p == q) {
        for (int i = l; i <= r; i++) ans += a[i];
        ans += add[p] * (r - l + 1);
    }
    else {
        for (int i = p + 1; i <= q - 1; i++)
            ans += sum[i] + add[i] * (R[i] - L[i] + 1);
        for (int i = l; i <= R[p]; i++) ans += a[i];
        ans += add[p] * (R[p] - l + 1);
        for (int i = L[q]; i <= r; i++) ans += a[i];
        ans += add[q] * (r - L[q] + 1);
    }
    return ans;
}
int main() {
    cin >> n >> m;
    for (int i = 1; i <= n; i++) scanf("%lld", &a[i]);
    // 分块
    t = sqrt(n*1.0);
    for (int i = 1; i <= t; i++) {
        L[i] = (i - 1)*sqrt(n*1.0) + 1;
        R[i] = i*sqrt(n*1.0);
    }
    if (R[t] < n) t++, L[t] = R[t - 1] + 1, R[t] = n;
    // 预处理
    for (int i = 1; i <= t; i++)
        for (int j = L[i]; j <= R[i]; j++) {
            pos[j] = i;
            sum[i] += a[j];
        }
    // 指令
    while (m--) {
        char op[3];
        int l, r, d;
        scanf("%s%d%d", op, &l, &r);
        if (op[0] == 'C') {
            scanf("%d", &d);
            change(l, r, d);
        }
        else printf("%lld\n", ask(l, r));
    }
}