1. 题目

传送门= ̄ω ̄=

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

  1. 给定一个矩形区域,该区域内的0变成1,1变成0(区间异或)
  2. 询问某个位置的值为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;
}

分享至ヾ(≧∇≦*)ゝ:
分类: 所有

XZYQvQ

炒鸡辣鸡的制杖蒟蒻一枚QvQ

发表评论

电子邮件地址不会被公开。 必填项已用*标注

你是机器人吗? =。= *