1. 题目

传送门=￣ω￣=

题意：给出一个 $N\times N$ 的矩阵，矩阵初始为 0，有 $M$ 个操作，操作有如下两种：

给定一个矩形区域，该区域内的 0 变成 1，1 变成 0（区间异或）
询问某个位置的值为 0 还是 1

$N\leq 1000, M\leq 50000$

有多组数据，数据组数不超过 10 组

2. 题解

主要是来记录一下二维差分方法的。

设原二维数组为 $a[i][j]$

设差分数组为 $d[i][j]$

则 $d[i][j]=a[i][j]+a[i-1][j-1]-a[i-1][j]-a[i][j-1]$

然后 $a[i][j]$ 的值就是 $d$ 的二维前缀和。

这个推导就不做过多赘述了。可以根据二维前缀和的容斥原理弄出来。

修改二维矩阵 $[(x1,y1),(x2,y2)]$ 时，就 $d[x1][y1]+=1,d[x2+1][y2+1]+=1,d[x1][y2+1]-=1,d[x2+1][y2]-=1$ 即可。

这题的话。。。

修改就是 $d[x1][y1]\oplus=1,d[x2+1][y2+1]\oplus=1,d[x1][y2+1]\oplus=1,d[x2+1][y2]\oplus=1$

单点询问就是求前缀异或和啦～~(≧▽≦)/~啦啦啦

代码：

#include <cstdio>
#include <cctype>
#include <cstring>

#define NS (1005)
#define lowbit(a) (a & -a)

using namespace std;

template <typename _Tp> inline void IN(_Tp& dig)
{
    char c; bool flag = 0; dig = 0;
    while (c = getchar(), !isdigit(c)) if (c == '-') flag = 1;
    while (isdigit(c)) dig = dig * 10 + c - '0', c = getchar();
    if (flag) dig = -dig;
}

int T, n, m;

char opt[3];

bool t[NS][NS];

void Rev(int a, int b)
{
    for (int i = a; i <= n; i += lowbit(i))
        for (int j = b; j <= n; j += lowbit(j))
            t[i][j] ^= 1;
}

int sum(int a, int b)
{
    int res = 0;
    for (int i = a; i; i -= lowbit(i))
        for (int j = b; j; j -= lowbit(j))
            res ^= t[i][j];
    return res;
}

int main(int argc, char const* argv[])
{
    IN(T);
    while (T--)
    {
        IN(n), IN(m), memset(t, 0, sizeof(t));
        for (int i = 1, a, b, c, d; i <= m; i += 1)
        {
            scanf("%s", opt), IN(a), IN(b);
            if (opt[0] == 'C')
            {
                IN(c), IN(d);
                Rev(a, b), Rev(c + 1, d + 1);
                Rev(a, d + 1), Rev(c + 1, b);
            }
            else printf("%d\n", sum(a, b));
        }
        putchar(10);
    }
    return 0;
}

【题解】Matrix 二维树状数组 POJ – 2155

于2018年5月29日2018年5月29日由XZYQvQ发布

1. 题目

2. 题解

XZYQvQ

0 条评论

发表回复取消回复

【题解】Matrix 二维树状数组 POJ – 2155

于2018年5月29日2018年5月29日由XZYQvQ发布

1. 题目

2. 题解

XZYQvQ

0 条评论

发表回复 取消回复

发表回复取消回复