洛谷 P3801 红色的幻想乡

题目背景

蕾米莉亚的红雾异变失败后，很不甘心。

题目描述

经过上次失败后，蕾米莉亚决定再次发动红雾异变，但为了防止被灵梦退治，她决定将红雾以奇怪的阵势释放。

我们将幻想乡看做是一个n*m的方格地区，一开始没有任何一个地区被红雾遮盖。蕾米莉亚每次站在某一个地区上，向东南西北四个方向各发出一条无限长的红雾，可以影响到整行/整列，但不会影响到她所站的那个地区。如果两阵红雾碰撞，则会因为密度过大而沉降消失。灵梦察觉到了这次异变，决定去解决它。但在解决之前，灵梦想要了解一片范围红雾的密度。可以简述为两种操作:

1 x y 蕾米莉亚站在坐标(x,y)的位置向四个方向释放无限长的红雾。

2 x1 y1 x2 y2 询问左上点为(x1,y1)，右下点为(x2,y2)的矩形范围内，被红雾遮盖的地区的数量。

输入格式

第一行三个整数n,m,q，表示幻想乡大小为n*m，有q个询问。

接下来q行，每行3个或5个整数,用空格隔开，含义见题目描述。

输出格式

对于每一个操作2，输出一行一个整数，表示对应询问的答案。

输入输出样例

输入 #1复制

输出 #1复制

说明/提示

样例解释:

用o表示没有红雾，x表示有红雾，两次释放红雾后幻想乡地图如下:

oxox

xoxo

oxox

xoxo

数据范围:

对于20%的数据，1<=n,m,q<=200

对于 40%的数据，1<=n,m,q<=1000

对于100%的数据，1<=n,m,q<=100000

1<=x1,x2,x<=n x1<=x2

1<=y1,y2,y<=m y1<=y2

by-orangebird

思路：区域前缀和，想到树状数组，重复两次抵消，即交点，则是容斥定理，注意站的点不收影响，即再次站在这会取消上次的影响，需要记录一下

typedef long long LL;

typedef pair<LL, LL> PLL;

const int maxm = 1e5+;

int Cx[maxm], Cy[maxm], ax[maxm], ay[maxm];

void add(int *C, int x, int val) {

    for(; x <= C[]; x += lowbit(x))

        C[x] += val;

}

int getsum(int *C, int x) {

    int ret = ;

    for(; x; x -= lowbit(x))

        ret += C[x];

    return ret;

}

int main() {

    ios::sync_with_stdio(false), cin.tie();

    int n, m, q, type, x1, x2, y1, y2;

    cin >> n >> m >> q;

    Cx[] = n, Cy[] = m;

    while(q--) {

        cin >> type;

        if(type == ) {

            cin >> x1 >> y1;

            if(ax[x1]) {

                ax[x1] = ;

                add(Cx, x1, -);

            } else {

                ax[x1] = ;

                add(Cx, x1, );

            }

            if(ay[y1]) {

                ay[y1] = ;

                add(Cy, y1, -);

            } else {

                ay[y1] = ;

                add(Cy, y1, );

            }

        } else if(type == ) {

            cin >> x1 >> y1 >> x2 >> y2;

            int s1 = getsum(Cx, x2) - getsum(Cx, x1-);

            int s2 = getsum(Cy, y2) - getsum(Cy, y1-);

            cout << 1LL*(y2-y1+)*s1 + 1LL*(x2-x1+)*s2-1LL*s1*s2*<<"\n";

        }

    }

    return ;

}

巴特西