紅色的幻想鄉

題目背景

蕾米莉亞的紅霧異變失敗後，很不甘心。

題目描述

經過上次失敗後，蕾米莉亞決定再次發動紅霧異變，但為了防止被靈夢退治，她決定將紅霧以奇怪的陣勢釋放。

我們將幻想鄉看做是一個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，輸出一行一個整數，表示對應詢問的答案。

輸入輸出樣例

4 4 3
1 2 2
1 4 4
2 1 1 4 4

8

說明

樣例解釋:

用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

 線段樹的運用。

用兩個線段樹表示行和列，維護第x行，第y列有沒有放過霧

由於兩片紅霧會抵消，相當於每次修改，對應行^=1,對應列^=1。

每一次詢問，即區間求和。令x=∑c1[x2-x1]，y=∑c2[y2-y1];

由容斥原理，可知ans=x*(y2-y1+1)+y*(x2-x1+1)-x*y*2;

記得開long long

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
using namespace std;
int c1[400001],c2[400001],n,m,q;
void addh(int rt,int l,int r,int x)
{
	if (l==r)
	{
		c1[rt]^=1;
		return;
	}
	int mid=(l+r)/2;
	if (x<=mid) addh(rt*2,l,mid,x);
	else addh(rt*2+1,mid+1,r,x);
 c1[rt]=c1[rt*2]+c1[rt*2+1];
}
void addl(int rt,int l,int r,int x)
{
	if (l==r)
	{
		c2[rt]^=1;
		return;
	}
	int mid=(l+r)/2;
	if (x<=mid) addl(rt*2,l,mid,x);
	else addl(rt*2+1,mid+1,r,x);
 c2[rt]=c2[rt*2]+c2[rt*2+1];
}
int geth(int rt,int l,int r,int L,int R)
{
	if (l>=L&&r<=R)
	{
		return c1[rt];
	}
	 int mid=(l+r)/2; 
	int s=0;
	 if (L<=mid) s+=geth(rt*2,l,mid,L,R);
	 if (R>mid) s+=geth(rt*2+1,mid+1,r,L,R);
	return s;
}
int getl(int rt,int l,int r,int L,int R)
{
	if (l>=L&&r<=R)
	{
		return c2[rt];
	}
	 int mid=(l+r)/2; 
	int s=0;
	 if (L<=mid) s+=getl(rt*2,l,mid,L,R);
	 if (R>mid) s+=getl(rt*2+1,mid+1,r,L,R);
	return s;
}
int main()
{int i,j,ch,x,y,x1,x2,y1,y2;
   scanf("%d%d%d",&n,&m,&q);
    for (i=1;i<=q;i++)
    {
    	scanf("%d",&ch);
    	if (ch==1)
    	{
    		scanf("%d%d",&x,&y);
    		addh(1,1,n,x);
    		addl(1,1,n,y);
    	}
    	if (ch==2)
    	{
    		scanf("%d%d%d%d",&x1,&y1,&x2,&y2);
           　　　　 int x=geth(1,1,n,x1,x2);
		   int y=getl(1,1,n,y1,y2);
		   printf("%lld\n",y*(long long)(x2-x1+1)+x*(long long)(y2-y1+1)-(long long)x*y*2);		
    	}
    }
}