[洛谷月赛] 红色的幻想乡

题目背景

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

题目描述

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

我们将幻想乡看做是一个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

这个题算一个还不错的数据结构题，勉强和容斥原理搞在一起了。。。

设bj[i]表示第i行是否放过奇数次红雾，bj2[i]表示第j列是否放过奇数次红雾(如果是偶数次就自己把自己抵消了)

那么我们对于一个矩形(x,y),(xx,yy) 内的被红雾覆盖的点数为：

$\sum_{i=x}^{xx}\sum_{j=y}^{yy} [bj[i]||bj[j]]-\sum_{i=x}^{xx}\sum_{j=y}^{yy}[bj[i]==1]*[bj[j]==1]$

就是求出点对(i,j)中只有行被覆盖或只有列被覆盖的数量(一个点的行和列都覆盖的话也会相互抵消)

设放过奇数次的行的数目为g，放过奇数次的列的数目为gg，由容斥原理则答案为：

$g*(yy-y+1)+gg*(xx-x+1)-2*g*gg$

那么我们就可以对行和列分别建线段树来维护，那么操作就是有单点异或和区间求和了。。。

// MADE BY QT666
#include<cstdio>
#include<algorithm>
#include<cmath>
#include<iostream>
#include<cstring>
using namespace std;
typedef long long ll;
const int N=200050;
int rt1,rt2,sz,sz2,ls[N],rs[N],ls2[N],rs2[N],sum1[N],sum2[N],n,m,q;
void update(int &x,int l,int r,int id){
  if(!x) x=++sz;
  if(l==r){sum1[x]^=1;return;}
  int mid=(l+r)>>1;
  if(id<=mid) update(ls[x],l,mid,id);
  else update(rs[x],mid+1,r,id);
  sum1[x]=sum1[ls[x]]+sum1[rs[x]];
}
void update2(int &x,int l,int r,int id){
  if(!x) x=++sz2;
  if(l==r){sum2[x]^=1;return;}
  int mid=(l+r)>>1;
  if(id<=mid) update2(ls2[x],l,mid,id);
  else update2(rs2[x],mid+1,r,id);
  sum2[x]=sum2[ls2[x]]+sum2[rs2[x]];
}
int query(int x,int l,int r,int xl,int xr){
  if(xl<=l&&r<=xr) return sum1[x];
  int mid=(l+r)>>1;
  if(xr<=mid) return query(ls[x],l,mid,xl,xr);
  else if(xl>mid) return query(rs[x],mid+1,r,xl,xr);
  else return query(ls[x],l,mid,xl,mid)+query(rs[x],mid+1,r,mid+1,xr);
}
int query2(int x,int l,int r,int xl,int xr){
  if(xl<=l&&r<=xr) return sum2[x];
  int mid=(l+r)>>1;
  if(xr<=mid) return query2(ls2[x],l,mid,xl,xr);
  else if(xl>mid) return query2(rs2[x],mid+1,r,xl,xr);
  else return query2(ls2[x],l,mid,xl,mid)+query2(rs2[x],mid+1,r,mid+1,xr);
}
int main(){
  scanf("%d%d%d",&n,&m,&q);
  for(int i=1;i<=q;i++){
    int type;scanf("%d",&type);
    if(type==1){
      int x,y;scanf("%d%d",&x,&y);
      update(rt1,1,n,x);update2(rt2,1,m,y);
    }
    else{
      int x,y,xx,yy;scanf("%d%d%d%d",&x,&y,&xx,&yy);
      int g=query(rt1,1,n,x,xx),gg=query2(rt2,1,m,y,yy);
      ll ans=1ll*g*(yy-y+1)+1ll*gg*(xx-x+1)-1ll*2*g*gg;
      printf("%lld
",ans);
    }
  }
  return 0;
}