「Codeforces 341D」Iahub and Xors – 题解

主要思路

首先看到这个题可以考虑树套树，然后就做完了。

我们考虑用二维树状数组进行差分。当然，如果按正常的想法差分的话，我们只能想到用前缀和维护单点值，而不是维护区间异或和。我们设差分后的结果：

\[ d_{i, j} = a_{i, j} \oplus a_{i – 1, j} \oplus a_{i, j – 1} \oplus a_{i – 1, j – 1} \]

这个差分的方式有点不太一样，因为我们比传统差分多算了 \(a_{i – 1, j – 1}\) 的贡献。

每当我们进行区域操作时，通过对二维差分的联想，我们大概知道操作 \(d_{x_1, y_1}, d_{x_2 + 1, y_1}, d_{x_1, y_2 + 1}, d_{x_2 + 1, y_2 + 1}\) 可以达到目的。那么我们思考一下，这个二维差分做完之后，我们如何做区间异或和。这里，我们用 \(\sum\) 代表区间异或和的结果：

\[ ans = \sum_{i = 1}^{x} \sum_{j = 1}^{y} a_{i, j} \]

强行带入 \(d_{i, j}\) 的定义式：

\[ ans = \sum_{i = x_1}^{x_2} \sum_{j = y_1}^{y_2} d_{i, j} \oplus a_{i – 1, j} \oplus a_{i, j – 1} \oplus a_{i – 1, j – 1} \]

最终变成了：

\[ ans = \sum_{i = 2k + (x \bmod 2)}^x \sum_{j = 2k + (y \bmod 2)}^y d_{i, j} \]

所以，在这个地方直接做差分是有意义的。我们可以对 \((x, y)\) 的奇偶性开 4 个二维树状数组，然后对奇偶性做即可。

代码

// CF341D.cpp
#include <bits/stdc++.h>

using namespace std;

typedef long long ll;

const int MAX_N = 1010;

int n, q;

struct BIT
{
    inline int lowbit(int x) { return x & (-x); }

    ll nodes[MAX_N][MAX_N];

    void update(int x, int y, ll d)
    {
        for (int i = x; i <= n; i += lowbit(i))
            for (int j = y; j <= n; j += lowbit(j))
                nodes[i][j] ^= d;
    }

    ll query(int x, int y)
    {
        ll ret = 0;
        for (int i = x; i >= 1; i -= lowbit(i))
            for (int j = y; j >= 1; j -= lowbit(j))
                ret ^= nodes[i][j];
        return ret;
    }
} tr[4];

int getParity(int x, int y) { return (x & 1) | ((y & 1) << 1); }

void modify(int x, int y, ll d) { tr[getParity(x, y)].update(x, y, d); }

ll query(int x, int y) { return tr[getParity(x, y)].query(x, y); }

int main()
{
    scanf("%d%d", &n, &q);
    while (q--)
    {
        int opt, x1, y1, x2, y2;
        ll d;
        scanf("%d%d%d%d%d", &opt, &x1, &y1, &x2, &y2);
        if (opt == 1)
        {
            ll ans = 0;
            ans ^= query(x2, y2);
            ans ^= query(x1 - 1, y2);
            ans ^= query(x2, y1 - 1);
            ans ^= query(x1 - 1, y1 - 1);
            printf("%lld\n", ans);
        }
        else
        {
            scanf("%lld", &d), modify(x1, y1, d);
            modify(x2 + 1, y1, d), modify(x1, y2 + 1, d);
            modify(x2 + 1, y2 + 1, d);
        }
    }
    return 0;
}