洛谷P4514 上帝造题的七分钟题解

题意：

裸体（裸题）就意味着身体（神题）。

“第一分钟，X 说，要有矩阵，于是便有了一个里面写满了 \(0\) 的 \(n\times m\) 矩阵。

第二分钟，L 说，要能修改，于是便有了将左上角为 \((a,b)\)，右下角为 \((c,d)\) 的一个矩形区域内的全部数字加上一个值的操作。

第三分钟，k 说，要能查询，于是便有了求给定矩形区域内的全部数字和的操作。

第四分钟，彩虹喵说，要基于二叉树的数据结构，于是便有了数据范围。

第五分钟，和雪说，要有耐心，于是便有了时间限制。

第六分钟，吃钢琴男说，要省点事，于是便有了保证运算过程中及最终结果均不超过 \(32\) 位有符号整数类型的表示范围的限制。

第七分钟，这道题终于造完了，然而，造题的神牛们再也不想写这道题的程序了。”

——《上帝造裸题的七分钟》。

所以这个神圣的任务就交给你了。

输入格式：

输入数据的第一行为 X n m，代表矩阵大小为 \(n\times m\)。

从输入数据的第二行开始到文件尾的每一行会出现以下两种操作：

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

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

请注意，\(k\) 为小写。

输出格式：

针对每个 \(k\) 操作，在单独的一行输出答案。

数据范围：

\(1 \le n \le 2048\)，\(1 \le m \le 2048\)，\(-500 \le \Delta \le 500\)，操作不超过 \(2\times 10^5\) 个，保证运算过程中及最终结果均不超过 \(32\) 位带符号整数类型的表示范围。

本来以为这道题可以 cdq 分治的，结果写完才发现三维偏序只能算 \(x_i \le x\) 且 \(y_i \le y\) 的矩形的贡献。

因此还是来讲讲本题的正解吧，二维树状数组。

听上去肯定是个极为复杂的数据结构，但是仔细思考一下并非如此。

常规的，二维数据结构通常在一维数据结构的每个数据节点再次维护一层结构。

void add(int x, int y, int v)
{
    for(int i = x; i <= n; i += lowbit(i))
        for(int j = y; j <= m; j += lowbit(j)) tr[i][j] += v; 
}

上面的代码就是维护二维树状数组的代码，但是我们不能直接得到它维护的东西。

首先看到本题容易想到二维差分以及区间加&区间查询的一维树状数组

那么这两者该如何结合呢？后者我们是通过数学推导得到了一个式子，于是维护两个树状数组得到答案。 \[ \begin{aligned} S(1,r) & =\sum_{i=1}^r a_i \\ & =\sum_{i=1}^r \sum_{j=1}^i b_j \\ & =\sum_{i=1}^r b_i \times(r-i+1) \\ & =\sum_{i=1}^r b_i \times(r+1)-\sum_{i=1}^r b_i \times i \end{aligned} \] 我们不妨继续推导二维的情况，考虑左下角和右上角分别为 \((1,1),(x,y)\) 的矩形 \[ S(1,1,x,y) = \sum_{i=1}^x\sum_{j=1}^y\sum_{l}^{i}\sum_{r}^{j}b_{l,r} \] 根据一维的推导中第二补到第三步的变换，我们可以考察每个 \(b_{l,r}\) 出现的次数 \[ \sum_{i=1}^x\sum_{j=1}^y b_{i, j}\times (x - i + 1)\times(y - j + 1) \] 拆开来可得 \[ \sum_{i=1}^x\sum_{j=1}^y b_{i, j}\times [(xy-xj+x) + (-yi+ij-i)+(y-j+1)] \] 最后可得 \[ \sum_{i=1}^x\sum_{j=1}^yb_{i,j} \times[(xy+x+y+1) - i(y+1) - j(x+1)+ij)] \] 于是我们可以维护四个二维的树状数组得到我们要的答案，即 \[ b_{i,j},\quad b_{i,j}\times i,\quad b_{i,j}\times j,\quad b_{i,j}\times ij \] 时间复杂度 \(\mathcal{O}(n \log^2 n)\)

代码：

#include <bits/stdc++.h>
using namespace std;
// #define int long long
#define INF 0x3f3f3f3f3f3f3f3f
void up(int &x,int y) { x < y ? x = y : 0; }
void down(int &x,int y) { x > y ? x = y : 0; }
#define N ((int)(3e3 + 15))

int n,m;
struct BIT
{
    int tr[N][N];
    int lowbit(int x) { return x & (-x); }
    void add(int x, int y, int v)
    {
        for(int i = x; i <= n; i += lowbit(i))
            for(int j = y; j <= m; j += lowbit(j)) tr[i][j] += v; 
    }
    int sum(int x, int y)
    {
        int r = 0;
        for(int i = x; i; i -= lowbit(i))
            for(int j = y; j; j -= lowbit(j)) r += tr[i][j];
        return r;
    }
}k,xk,yk,xyk;
void add(int x, int y, int v)
{
    k.add(x, y, v); xyk.add(x, y, v * x * y);
    xk.add(x, y, v * x); yk.add(x, y, v * y);
}
int sum(int x, int y)
{
    return k.sum(x, y) * (x * y + x + y + 1)
        - xk.sum(x, y) * (y + 1)
        - yk.sum(x, y) * (x + 1)
        + xyk.sum(x, y);
}
signed main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);cout.tie(0);
    // freopen("check.in","r",stdin);
    // freopen("check.out","w",stdout);
    char op; cin >> op >> n >> m;
    for(int a,b,c,d,x; cin >> op; )
    {
        cin >> a >> b >> c >> d;
        if(op == 'L')
        {
            cin >> x;
            add(a, b, x); add(a, d + 1, -x);
            add(c + 1, b, -x); add(c + 1, d + 1, x);
        }else {
            cout << sum(c, d) - sum(a - 1, d) - sum(c, b - 1) + sum(a - 1, b - 1) << '\n';
        }
    }
    return 0;
}