题解 P4514 上帝造题的七分钟

题意简述

给定一个 \(n \times m\) 的矩阵，若干次操作（操作不超过 \(2\times 10^5\) 个）：

• L a b c d delta —— 代表将 \((a,b),(c,d)\) 为顶点的矩形区域内的所有数字加上 \(delta\) 。
• k a b c d —— 代表求 \((a,b),(c,d)\) 为顶点的矩形区域内所有数字的和。

对于每次操作 k 输出一个答案。

\(1 \leq n,m \leq 2^{11}\) 。保证运算过程中及最终结果均不超过 32 位有符号整数类型的表示范围。

Solution

发现数据范围用线段树套线段树会 \(MLE\) ，考虑二维树状数组。

修改

因为有区间修改，考虑差分。

首先现象一下二维前缀和是什么？

那么差分的方法就是：

这样的话，在如下矩阵中，如果要让 \((2,2)\to (3,3)\) 整体加 \(x\) ，差分数组的变化：

0 0 0 0 0
0 0 0 0 0
0 0 0 0 0
0 0 0 0 0

0 0 0 0 0
0 x 0 -x 0
0 0 0 0 0
0 -x 0 x 0

读者可以手推一下。

那么修改直接在二维树状数组上用差分修改就可以。

查询

下面记 \(s(x,y)\) 表示以 \((1,1)\) 为左上角， \((x,y)\) 为右下角的矩阵和。

因为 \((x_1,y_1)\sim(x_2,y_2)\) 的和可以拆分成 \(s(x_2,y_2)-s(x_2,y_1-1)-s(x_1-1,y_2)+s(x_1-1,y_1-1)\) 。所以我们只要能求 \(s(x,y)\) 就能回答询问。

分析一下，因为差分和前缀和互逆，所以：

然后我们如果要求 \(\sum_{i=1}^x\sum_{j=1}^ya_{i,j}\) 的话，其实就是：

然后考虑 \(d_{c,d}\) 被算了几次：当 \(i \geq c \and j \geq d\) 时， \(d_i,j\) 就会被算一次。

根据乘法原理， \(d_{c,d}\) 被算的次数就是 \((x-c+1)\times(y-d+1)\) 。

所以就相当于：

化简可得：

于是分别用四个树状数组维护 \(d_{i,j},d_{i,j}\times i,d_{i,j}\times j,d_{i,}\times ij\) 即可。

代码如下：

#include <cstdio>
#include <cstring>
#include <cctype>
#include <algorithm>
#include <iostream>
#include <queue>
using namespace std;
inline int read() {
    int num = 0 ,f = 1; char c = getchar();
    while (!isdigit(c)) f = c == ‘-‘ ? -1 : f ,c = getchar();
    while (isdigit(c)) num = (num << 1) + (num << 3) + (c ^ 48) ,c = getchar();
    return num * f;
}
const int N = 2050;
struct BIT {
    int t[N][N] ,n ,m;
    inline int lowbit(int x) {return x & (-x);}
    inline void modify(int x ,int y ,int k) {
        for (int i = x; i <= n; i += lowbit(i))
            for (int j = y; j <= m; j += lowbit(j))
                t[i][j] += k;
    }
    inline int sum(int x ,int y) {
        int ans = 0;
        for (int i = x; i ; i -= lowbit(i))
            for (int j = y ; j ; j -= lowbit(j))
                ans += t[i][j];
        return ans;
    }
}t ,ti ,tj ,tij;
int n ,m; char opt[10];
inline void modify(int x ,int y ,int k) {
    t.modify(x ,y ,k);
    ti.modify(x ,y ,k * x);
    tj.modify(x ,y ,k * y);
    tij.modify(x ,y ,k * x * y);
}
inline int sum(int x ,int y) {
    int ans = 0;
    ans += t.sum(x ,y) * (x * y + x + y + 1);
    ans -= ti.sum(x ,y) * (y + 1);
    ans -= tj.sum(x ,y) * (x + 1);
    ans += tij.sum(x ,y);
    return ans;
}
signed main() {
    scanf("%s" ,opt + 1);
    n = read(); m = read();
    t.n = ti.n = tj.n = tij.n = n;
    t.m = ti.m = tj.m = tij.m = m;
    while (~scanf("%s" ,opt + 1)) {
        if (opt[1] == ‘L‘) {
            int x1 = read() ,y1 = read() ,x2 = read() ,y2 = read() ,k = read();
            modify(x1 ,y1 ,k);
            modify(x1 ,y2 + 1 ,-k);
            modify(x2 + 1 ,y1 ,-k);
            modify(x2 + 1, y2 + 1 ,k);
        }
        else {
            int x1 = read() ,y1 = read() ,x2 = read() ,y2 = read();
            printf("%d\n" ,sum(x2 ,y2) - sum(x2 ,y1 - 1) - sum(x1 - 1 ,y2) + sum(x1 - 1 ,y1 - 1));
        }
    }
    return 0;
}

题解 P4514 上帝造题的七分钟

原文：https://www.cnblogs.com/Dragon-Skies/p/14728010.html