题目描述
经过上次失败后，蕾米莉亚决定再次发动红雾异变，但为了防止被灵梦退治，她决定将红雾以奇怪的阵势释放。
我们将幻想乡看做是一个n*m的方格地区，一开始没有任何一个地区被红雾遮盖。蕾米莉亚每次站在某一个地区上，向东南西北四个方向各发出一条无限长的红雾，可以影响到整行/整列，但不会影响到她所站的那个地区。如果两阵红雾碰撞，则会因为密度过大而沉降消失。
灵梦察觉到了这次异变，决定去解决它。但在解决之前，灵梦想要了解一片范围红雾的密度。可以简述为两种操作:
1 x y 蕾米莉亚站在坐标(x,y)的位置向四个方向释放无限长的红雾。
2 x1 y1 x2 y2 询问左上点为(x1,y1)，右下点为(x2,y2)的矩形范围内，被红雾遮盖的地区的数量。
解法
因为对于一次修改，一定会修改到底，怎么说的，就是这一列或者是这一整行都被我们修改了，那么我们就可以将这幅图抽象成两条数轴上的操作。
对于每一次的修改，我们只需要单点修改某一个节点上的数。
但是这个节点上需要记录什么信息呢？这种题目很明显用线段树维护比较好（树状数组也很好，但是我还是喜欢线段树），那么要节点要记录的数值有\(l\)，和\(r\)，除此之外，我们需要知道在这一段区间中，被红雾所覆盖的节点的总数。
然后单点修改就到这里位置。
关于查询操作，我们每次是查询两个线段树的区间和。
我们假设求出求出来的值分别是\(ansx\)和\(ansy\)，对于的分别是\(x\)轴上的答案和\(y\)轴上的答案。
然后在定义\(lenx\)和\(leny\)表示查找区间\(x\)的长度和和\(y\)区间的长度。
因为我们知道，两个红雾重合在一起就会被抵消掉，也就是说在查找区间内，所有的\(ansx\)和所有\(ansy\)全都会重合。 为什么？因为每一次修改就一定是修改到底。
那么我们通过容斥原理，如果仅算\(x\)的答案就是\(ansy*x\)，也就是当前\(x\)数×有的\(y\)，同理\(y\)的答案是\(ansx*y\)，但是有消除，所以我们需要\(-\)掉\(2*ansx*ansy\)，为什么是\(2*ansx*ansy\)，而不是\(ansx*ansy\)，因为你不是在去掉重复，而是减掉消除的部分。
ac代码
#include<bits/stdc++.h>
#define LL long long
#define N 100005
using namespace std;
int read(){
int w=0,x=0;char ch=0;
while(!isdigit(ch))w|=ch=='-',ch=getchar();
while(isdigit(ch))x=(x<<1)+(x<<3)+(ch^48),ch=getchar();
return w?-x:x;
}
int n,m,q;
struct segment_tree{
#define ls (nod<<1)
#define rs (nod<<1|1)
#define mid ((l+r)>>1)
struct node{
int l,r;
LL s;
}tr[N<<2];
void pushup(int nod){tr[nod].s=tr[ls].s+tr[rs].s;}
void build(int l,int r,int nod){
tr[nod].l=l; tr[nod].r=r; tr[nod].s=0;
if(l==r) return;
build(l,mid,ls);
build(mid+1,r,rs);
}
void update_point(int nod,int k){
int l=tr[nod].l,r=tr[nod].r;
if(l==r){tr[nod].s^=1;return;}
if(k<=mid) update_point(ls,k);
else update_point(rs,k);
pushup(nod);
}
LL query_sec(int nod,int ql,int qr){
int l=tr[nod].l,r=tr[nod].r;
if(ql<=l&&r<=qr) return tr[nod].s;
LL res=0;
if(ql<=mid) res+=query_sec(ls,ql,qr);
if(qr>mid) res+=query_sec(rs,ql,qr);
return res;
}
}tr1,tr2;
int main(){
n=read(),m=read(),q=read();
tr1.build(1,n,1); tr2.build(1,m,1);
while(q--){
int opt=read();
if(opt==1){
int x=read(),y=read();
tr1.update_point(1,x); tr2.update_point(1,y);
}
else{
#define x1 saber
#define x2 archer
#define y1 caster
#define y2 rider
int x1=read(),y1=read(),x2=read(),y2=read();
LL a1=tr1.query_sec(1,x1,x2),a2=tr2.query_sec(1,y1,y2);
LL ans=a1*(LL)(y2-y1+1)+a2*(LL)(x2-x1+1)-a1*a2*2;
printf("%lld\n",ans);
}
}
return 0;
}
对于自己代码的感想
因为\(y1\)成为了关键字，那么就重定义一下（我是一个\(Fate\)迷）QAQ。