P4514 上帝造题的七分钟

P4514 上帝造题的七分钟

题意： 二维区间修改 区间查询

**错误日志： 写了个 4 重循环忘记调用 \(i\) **

---

Solution

二维树状数组 巨尼玛毒瘤

听说二维线段树会 \(MLE\) 反正我两个都不会 就学了二维树状数组

然而这是什么东西啊太恶心了

首先是推导：

设 \(b[x][y]\) 为二维增量数组， 那么有：

\[SUM[x,y]=\sum_{i = 1}^{x}\sum_{j = 1}^{y}\sum_{k = 1}^{i}\sum_{l = 1}^{j}b[k][l]$$ $$=\sum_{i = 1}^{x}\sum_{j = 1}^{y}(x - i + 1)(y - j + 1)b[i][j]$$把有关 $i, j$ 的丢到一边， 展开化简得
$$(xy + x + y + 1)\sum_{i = 1}^{x}\sum_{j = 1}^{y}b[i][j] - (x +1)\sum_{i = 1}^{x}\sum_{j = 1}^{y}j * b[i][j] - (y + 1)\sum_{i = 1}^{x}\sum_{j = 1}^{y}i * b[i][j] + \sum_{i = 1}^{x}\sum_{j = 1}^{y}ij * b[i][j]\]

所以， 我们维护 \(b[i][j], b[i][j] * i, b[i][j] * j, b[i][j] * i * j\) 这四个前缀和即可 二维树状数组区间修改区间查询

Code

#include<iostream>

#include<cstdio>

#include<queue>

#include<cstring>

#include<algorithm>

#include<climits>

#define LL long long

using namespace std;

int RD(){

    int out = 0,flag = 1;char c = getchar();

    while(c < '0' || c >'9'){if(c == '-')flag = -1;c = getchar();}

    while(c >= '0' && c <= '9'){out = out * 10 + c - '0';c = getchar();}

    return flag * out;

    }

const int maxn = 4019;

int lenx, leny;

int num, na;

#define lowbit(i) ((i) & (-i))

int c[maxn][maxn][4];

void update(int x, int y, int val, int o){

    if(x < 1 || x > lenx || y < 1 || y > leny)return ;

    if(o == 0)val = val;

    else if(o == 1)val *= x;

    else if(o == 2)val *= y;

    else val *= x * y;

    for(int i = x;i <= lenx;i += lowbit(i))

        for(int j = y;j <= leny;j += lowbit(j))

            c[i][j][o] += val;

    }

int get_sum(int x, int y, int o){

    int ans = 0;

    for(int i = x;i > 0;i -= lowbit(i))

        for(int j = y;j > 0;j -= lowbit(j))

            ans += c[i][j][o];

    return ans;

    }

void uprange(int x1, int y1, int x2, int y2, int val){

    for(int i = 0;i < 4;i++){

        update(x1, y1, val, i), update(x1, y2 + 1, -val, i);

        update(x2 + 1, y2 + 1, val, i), update(x2 + 1, y1, -val, i);

        }

    }

int query(int x, int y){

    return

    (x * y + x + y + 1) * get_sum(x, y, 0) -

    (x + 1) * get_sum(x, y, 2) -

    (y + 1) * get_sum(x, y, 1) +

    get_sum(x, y, 3);

    }

char cmd;

int main(){

    cin>>cmd;lenx = RD();leny = RD();

    while(cin>>cmd){

        int x1 = RD(), y1 = RD(), x2 = RD(), y2 = RD();

        if(cmd == 'L'){

            int val = RD();

            uprange(x1, y1, x2, y2, val);

            }

        else{

            printf("%d\n",

            query(x2, y2) +

            query(x1 - 1, y1 - 1) -

            query(x2, y1 - 1) -

            query(x1 - 1, y2)

            );

            }

        }

    }