洛谷P7492 [传智杯 #3 决赛] 序列 题解 数列分块

题目链接：https://www.luogu.com.cn/problem/P7492

解题思路：

分块。解题思路全部来自 yzy1大佬的博客

额外掌握技能：

编译时加入 -Wall 参数。

示例程序：

#include <bits/stdc++.h>
using namespace std;
const int maxn = 1e5 + 5;
int n, m, blo,             // n表示数列长度，m表示操作次数，blo表示分块大小
        a[maxn],        // a[i]表示序列中第i个元素的数字
        v[400],         // v[i]表示第i个分块的所有元素的按位与
        bl[maxn];       // bl[i]表示序列中第i个元素所属的分块的编号
long long lsum[400],    // lsum[i]表示第i个分块的所有前缀对应的最大子段和
        rsum[400],      // rsum[i]表示第i个分块的所有后缀对应的最大子段和
        msum[400],      // msum[i]表示第i个分块（单独算）对应的最大子段和
        sum[400];       // sum[i]表示第i个分块中所有元素之和

// 更新第p个分块的信息
void upd(int p) {
    int l = (p - 1) * blo + 1, r = min(n, p * blo);
    lsum[p] = rsum[p] = msum[p] = sum[p] = 0;
    // 更新 msum[p] 和 sum[p]
    long long tmp = 0;
    for (int i = l; i <= r; i++) {
        tmp = max(tmp, 0ll) + a[i];
        msum[p] = max(msum[p], tmp);
        sum[p] += a[i];
    }
    // 更新 lsum[p]
    tmp = 0;
    for (int i = l; i <= r; i++) {
        tmp += a[i];
        lsum[p] = max(lsum[p], tmp);
    }
    // 更新 rsum[p]
    tmp = 0;
    for (int i = r; i >= l; i--) {
        tmp += a[i];
        rsum[p] = max(rsum[p], tmp);
    }
}

// 将第 p 个分块的所有元素整体按位或上k
void func_or(int p, int k) {
    if ((v[p] & k) == k)  // 如果第p个分块的所有元素在k为1的那些位也都为1了
        return;             // 则不用再进行按位或操作了
    v[p] |= k;
    for (int i = (p - 1) * blo + 1; i <= min(n, p * blo); i++)
        a[i] |= k;
    upd(p);
}

// 操作2：将 a[l..r] 都按位或上 k
void update(int l, int r, int k) {
    if (bl[l] == bl[r]) {
        for (int i = l; i <= r; i++)
            a[i] |= k;
        upd(bl[l]);
        return;
    }
    for (int i = l; i <= bl[l] * blo; i++)
        a[i] |= k;
    upd(bl[l]);
    for (int i = (bl[r] - 1) * blo + 1; i <= r; i++)
        a[i] |= k;
    upd(bl[r]);
    for (int i = bl[l]+1; i < bl[r]; i++)
        func_or(i, k);
}

// 操作1：查询 a[l..r] 的最大子段和
long long query(int l, int r) {
    long long res = 0, tmp = 0;
    if (bl[l] == bl[r]) {
        for (int i = l; i <= r; i++) {
            tmp = max(tmp, 0ll) + a[i];
            res = max(res, tmp);
        }
    }
    else {
        // 最左边的分块的最大子段和
        for (int i = bl[l] * blo; i >= l; i--) {
            tmp = max(tmp, 0ll) + a[i];
            res = max(res, tmp);
        }
        // 最左边的分块的最大后缀和
        long long sum1 = 0;
        tmp = 0;
        for (int i = bl[l] * blo; i >= l; i--) {
            tmp += a[i];
            sum1 = max(sum1, tmp);
        }
        for (int i = bl[l]+1; i <= bl[r]; i++) {
            if (i < bl[r]) {
                res = max(res, msum[i]);
                res = max(res, sum1 + lsum[i]);
                sum1 = max(sum1 + sum[i], rsum[i]);
            }
            else {  // i == bl[r]
                // 最右边的分块的最大子段和
                tmp = 0;
                for (int j = (bl[r]-1)*blo+1; j <= r; j++) {
                    tmp = max(tmp, 0ll) + a[j];
                    res = max(res, tmp);
                }
                // 最右边的分块的最大前缀和
                long long sum2 = 0;
                tmp = 0;
                for (int j = (bl[r]-1)*blo+1; j <= r; j++) {
                    tmp += a[j];
                    sum2 = max(sum2, tmp);
                }
                res = max(res, sum1 + sum2);
            }
        }
    }
    return res;
}

int main() {
    scanf("%d%d", &n, &m);
    for (int i = 1; i <= n; i++)
        scanf("%d", a+i);
    blo = sqrt(n);
    for (int i = 1; i <= n; i++) bl[i] = (i - 1) / blo + 1;
    for (int i = 1; i <= bl[n]; i++) upd(i);
    while (m--) {
        int op, l, r, k;
        scanf("%d%d%d", &op, &l, &r);
        if (op == 1) {
            printf("%lld\n", query(l, r));
        }
        else {
            scanf("%d", &k);
            update(l, r, k);
        }
    }
    return 0;
}