洛谷P3801 红色的幻想乡

本文主要是介绍洛谷P3801 红色的幻想乡，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

洛谷P3801 红色的幻想乡

1<=n,m<=100000……二维线段树废了。

然而再看看这个题，起始点没有红雾，就像：
1ge

两个重复的会抵消，便是这样：
这里写图片描述

那么，站的位置可否当做抵消掉的呢？
上边图中的红雾数量，可以是：

放 过 的 行 数 \times 行 长 度 + 放 过 的 列 数 \times 列 长 度 - 抵 消 块 数

$放过的行数×行长度+放过的列数×列长度-抵消块数$
行、列的长度就是题中m，n，抵消块数呢？

在算行列时，每一个交叉点是记了两次的。图中有多少交叉点呢？记放过的行数x，放过的列数y，每行每列交叉1个，抵消块数就是2xy。

到现在，求出x，y就拥有了一切！

行列有多少？区间求和。每次放红雾？单点修改。标准线段树。
当站在放过的那行（列）上时，整一行就消了。在上图中，假设在 ( 4 , 3 )点放一次，变成：
这里写图片描述
站的那点本来就红，放一下不影响。而原来白的变红了，不就是没放那一行吗！
若是站在以前站过的点上，同样的道理。

修改时直接异或，0改11改0完事。

#include<iostream>
#include<cstdio>
#define now int l,int r,int num
#define ls l,l+r>>1,num<<1
#define rs (l+r>>1)+1,r,num<<1|1
using namespace std;
int y[262150],x[262150];
int x1,y1,x2,y2;
int n,m,q;
void update(int *a,int num){a[num]=a[num<<1]+a[num<<1|1];}
void change(int *a,int p,now){if(l==r){a[num]^=1;return;}int mid=l+r>>1;if(p<=mid)change(a,p,ls);else change(a,p,rs);update(a,num);}int que(int *a,int al,int ar,now){if(al<=l&&r<=ar)return a[num];int mid=l+r>>1,ans=0;if(al<=mid)ans+=que(a,al,ar,ls);if(mid<ar)ans+=que(a,al,ar,rs);return ans;}
int main(){scanf("%d%d%d",&n,&m,&q);while(q--){int cmd;scanf("%d",&cmd);if(cmd==1){int x0,y0;scanf("%d%d",&x0,&y0);change(x,x0,1,n,1);change(y,y0,1,m,1);}else{scanf("%d%d%d%d",&x1,&y1,&x2,&y2);long long xx=que(x,x1,x2,1,n,1),yy=que(y,y1,y2,1,m,1);printf("%lld\n",xx*(long long)(y2-y1+1)+yy*(long long)(x2-x1+1)-(long long)(xx*yy<<1));}}return 0;}