Problem 3 二维差分

$des$

考虑一个 n ∗ n 的矩阵 A，初始所有元素均为 0。
执行 q 次如下形式的操作：给定 4 个整数 r,c,l,s，对于每个满足 x ∈ [r,r+l), y ∈ [c,x−r+c]
的元素 (x,y)，将权值增加 s。也就是，给一个左上顶点为 (r,c)、直角边长为 l 的下三角区域加
上 s。
输出最终矩阵的元素异或和。

$sol$

每次加减是一个等腰直角三角形

考虑对每行查分

即对垂直于 x 轴的腰上的每个点 +1 ，所有斜边的后一个点 -1

这样的话，每行形成了查分数组

简化上面的过程

对腰上的点 +1 时同样也可以查分进行

对斜边上的点同理，只不过还原时 $a_{i, j} += a_{i - 1, j - 1}$

注意判断边界条件

$code$

#include <iostream>

#include <cstdio>

#include <algorithm>

#include <cmath>

#include <cstring>

#include <string>

#include <cstdlib>

using namespace std;

const int N = ;

#define gc getchar()

inline int read() {

    int x = ; char c = gc;

    while(c < '' || c > '') c = gc;

    while(c >= '' && c <= '') x = x *  + c - '', c = gc;

    return x;

}

#undef gc

#define Rep(i, a, b) for(int i = a; i <= b; i ++)

#define LL long long

LL add[N][N], cut[N][N];

struct Node {

    int r, c, l, s;

} Ask[(int)3e5 + ];

int n, q;

LL A[N][N], B[N][N];

int main() {

    n = read(), q = read();

    Rep(qq, , q) Ask[qq] = (Node) {

        read(), read(), read(), read()

    };

    Rep(i, , q) {

        int r = Ask[i].r, c = Ask[i].c, l = Ask[i].l, s = Ask[i].s;

        add[r][c] += s; add[r + l][c] -= s;

        cut[r][c + ] += s; cut[r + l][c + l + ] -= s;

    }

    Rep(j, , n) {

        Rep(i, , n) add[i][j] += add[i - ][j];

    }

    Rep(i, , n) {

        Rep(j, , n) cut[i][j] += cut[i - ][j - ];

    }

    Rep(i, , n) {

        Rep(j, , n) A[i][j] += A[i][j - ] + add[i][j] - cut[i][j];

    }

    LL Answer = ;

    Rep(i, , n) Rep(j, , n) Answer ^= A[i][j];

    cout << Answer;

    return ;

}

巴特西

Problem 3 二维差分

最新文章

热门文章