题解 SP1043 GSS1 - Can you answer these queries I

· · 个人记录

分块大法好！！！

你没有看错，这是一篇分块的题解。。。

看到题解区里大多是线段树的题解，如此良心的数据范围之下（N<=5e4)却没看到有分块的题解，敲完线段树正解的蒟蒻我并不甘心，决定用分块——这一优雅的暴力来水过这题

定义：

同线段树的解法一样，在分块做法里，我们同样需要维护四个东西：

struct Node {
    int sum, pre, lmax, rmax;
} f[block][block];

即区间总和，区间最大子段和，区间最大前缀和，区间最大后缀和

不同的是这里维护的是以每个块作为一个单位，f[i][j](i <= j)表示从第i块到第j块这一区间内维护的信息

实现：

在线段树里，我们可以通过遍历整棵树，自下而上的方式进行维护，可分块又是怎样维护的呢？

实则是与线段树的的维护方法大同小异，先是通过暴力求出每个块内(f[i][i](1<=i<=n))的信息，再利用小块来计算出大块，具体步骤可参考线段树的写法，鉴于本文作者实在太蒻，这里不加阐述了

答案：

这应该是唯一一点与线段树写法不太一样的地方

如果l和r在同一块里，暴力统计

如不在同一块里，则答案有六种可能：

1.中间连续整块的区间最大子段和

2.中间连续整块的区间最大前缀和 + 左端散块最大后缀和

3.中间连续整块的区间最大后缀和 + 右端散块最大前缀和

4.中间连续整块的区间总和 + 左端散块最大后缀和 + 右端散块最大前缀和

5.左端散块最大子段和

6.右端散块最大子段和

最后是完整代码啦：
#include <bits/stdc++.h>
using std::max;
using std::cin;
using std::cout;

const int N = 5e4 + 10;
const int block = 300;

struct Node {
    int sum, pre, lmax, rmax;
} f[block][block];

int n, m, cnt;
int a[N], pos[N], l[N], r[N];

signed main() {
    std::ios::sync_with_stdio(0);
    cin >> n;
    cnt = n / block + (n % block != 0);
    for (int i = 1; i <= n; i++) {
        cin >> a[i]; pos[i] = (i - 1) / block + 1;
    }
    for (int i = 1; i <= cnt; i++) {
        l[i] = r[i - 1] + 1;
        r[i] = r[i - 1] + block;
    } r[cnt] = n;
    for (int i = 1; i <= cnt; i++) {
        for (int j = l[i]; j <= r[i]; j++) {
            f[i][i].sum += a[j];
        } 
        int tmp = a[l[i]]; f[i][i].lmax = tmp;
        for (int j = l[i] + 1; j <= r[i]; j++) {
            tmp += a[j];
            f[i][i].lmax = max(f[i][i].lmax, tmp);
        }
        tmp = a[r[i]]; f[i][i].rmax = tmp;
        for (int j = r[i] - 1; j >= l[i]; j--) {
            tmp += a[j];
            f[i][i].rmax = max(f[i][i].rmax, tmp);
        }
        tmp = a[l[i]]; f[i][i].pre = tmp;
        for (int j = l[i] + 1; j <= r[i]; j++) {
            if (tmp < 0) { tmp = a[j]; }
            else { tmp += a[j]; }
            f[i][i].pre = max(f[i][i].pre, tmp);
        }
    }
    for (int l = 2; l <= cnt; l++) {
        for (int i = 1; i <= cnt; i++) {
            for (int j = i + l - 1; j <= cnt; j++) {
                f[i][j].sum = f[i][j - 1].sum + f[j][j].sum;
                f[i][j].lmax = max(f[i][j - 1].lmax, f[i][j - 1].sum + f[j][j].lmax);
                f[i][j].rmax = max(f[i + 1][j].rmax, f[i + 1][j].sum + f[i][i].rmax);
                f[i][j].pre = max(max(f[i][j - 1].pre, f[j][j].pre), f[i][j - 1].rmax + f[j][j].lmax);
            }
        }
    }
    cin >> m;
    int L, R, ans;
    while (m --> 0) {
        cin >> L >> R;
        if (pos[L] == pos[R]) {
            int tmp = a[L]; ans = tmp;
            for (int i = L + 1; i <= R; i++) {
                if (tmp < 0) { tmp = a[i]; }
                else { tmp += a[i]; }
                ans = max(ans, tmp);
            }
        } else {
            ans = f[pos[L] + 1][pos[R] - 1].pre;
            int tmpx, tmpy, prex, prey;
            tmpx = prex = a[r[pos[L]]];
            for (int i = r[pos[L]] - 1; i >= L; i--) {
                tmpx += a[i];
                prex = max(prex, tmpx);
            }
            tmpy = prey = a[l[pos[R]]];
            for (int i = l[pos[R]] + 1; i <= R; i++) {
                tmpy += a[i];
                prey = max(prey, tmpy);
            }
            ans = max(ans, f[pos[L] + 1][pos[R] - 1].lmax + prex);
            ans = max(ans, f[pos[L] + 1][pos[R] - 1].rmax + prey);
            ans = max(ans, f[pos[L] + 1][pos[R] - 1].sum + prex + prey);
            tmpx = prex = a[r[pos[L]]];
            for (int i = r[pos[L]] - 1; i >= L; i--) {
                if (tmpx < 0) { tmpx = a[i]; }
                else { tmpx += a[i]; }
                prex = max(prex, tmpx);
            }
            tmpy = prey = a[l[pos[R]]];
            for (int i = l[pos[R]] + 1; i <= R; i++) {
                if (tmpy < 0) { tmpy = a[i]; }
                else { tmpy += a[i]; }
                prey = max(prey, tmpy);
            }
            ans = max(max(prex, prey), ans);
        }
        cout << ans << "\n";
    }
    return 0;
}

Summary:

一般来说这一类区间操作的题目，在数据范围不是很大的情况下,（<=3e5）思路简明代码易于实现的分块，总是不错的选择