题意

给定一个平面\((n,m)\)，处理如下操作：

• OPT = 1：使点\((x,y)\)处使横纵行全部0/1取反。
• OPT = 2：矩形\((x_1,y_1,x_2,y_2)\)内的和。

主要思路

这道题还是很有意思的。

首先设置数组\(\text{stat_x[],stat_y[]}\)，记录每一行的0/1情况；再搞两个树状数组，来维护区间内点的个数。在加点的时候，如果当前行/列已被操作过，那就在 stat 数组内取反即可，并且在当前行/列所对应的树状数组中加/减这个点的贡献，也就是\(\pm 1\)。计算的时候，区间查询出长方形长区间和宽区间对应的点数，然后再乘上相应贡献（也就是矩形长度或宽度），然后再减去消掉的点。

代码

// P3801.cpp
#include <bits/stdc++.h>
#define lowbit(x) (x & -x)
using namespace std;
const int MAX_N = 101000;
int n, m, q, x_ctn[MAX_N], y_ctn[MAX_N], x_tree[MAX_N], y_tree[MAX_N], opt, tmpx, tmpy;
void add(int x, int d, int limit, int *tree)
{
    while (x <= limit)
        tree[x] += d, x += lowbit(x);
}
int sum(int x, int *tree)
{
    int ans = 0;
    while (x > 0)
        ans += tree[x], x -= lowbit(x);
    return ans;
}
void change(int x, int y)
{
    x_ctn[x] ^= 1, add(x, x_ctn[x] ? 1 : -1, n, x_tree);
    y_ctn[y] ^= 1, add(y, y_ctn[y] ? 1 : -1, m, y_tree);
}
int main()
{
    scanf("%d%d%d", &n, &m, &q);
    x_tree[0] = n, y_tree[0] = m;
    while (q--)
    {
        scanf("%d", &opt);
        if (opt == 1)
            scanf("%d%d", &tmpx, &tmpy), change(tmpx, tmpy);
        else
        {
            int x1, x2, y1, y2;
            scanf("%d%d%d%d", &x1, &y1, &x2, &y2);
            int s1 = sum(x2, x_tree) - sum(x1 - 1, x_tree);
            int s2 = sum(y2, y_tree) - sum(y1 - 1, y_tree);
            long long ans = 1LL * s1 * (y2 - y1 + 1) + 1LL * s2 * (x2 - x1 + 1) - 2LL * s1 * s2;
            printf("%lld\n", ans);
        }
    }
    return 0;
}