P3801:红色的幻想乡题解

题意

给定一个平面\((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;
}

发布者

Kal0rona

江西师大附中全机房最弱

发表评论

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