树状数组，线段树，容斥，P3801 红色的幻想乡

P3801 红色的幻想乡 - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)

题目背景

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

题目描述

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

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

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

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

输入格式

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

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

输出格式

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

输入输出样例

输入 #1复制

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

输出 #1复制

8

说明/提示

样例输入输出 1 解释

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

oxox
xoxo
oxox
xoxo

数据规模与约定

• 对于 20% 的数据，1≤n,m,q≤200。
• 对于 40%40% 的数据，11≤n,m,q≤103。
• 对于 100%100% 的数据，1≤n,m,q≤105，1≤x1​,x2​,x≤n，x1​≤x2​，1≤y1​,y2​,y≤m，y1​≤y2​。

 解析：线段树，容斥

关于这个二维数组的状态统计问题，我们需要找到一个简洁的方法，一个一个找肯定是不现实的。

这里我们应用容斥来统计：

容斥原理是一种组合数学中常用的计数技巧，用于计算多个集合的并集、交集等情况下的元素个数。容斥原理通常用于解决包含排列组合的问题，特别是计算集合的大小或元素的个数。

容斥原理的基本思想是通过将不同集合的贡献逐一相加，并在适当情况下减去重复计数的部分，以获得最终的结果。通常，容斥原理适用于处理以下问题：

1. 求多个集合的并集中元素的个数。
2. 求多个集合的交集中元素的个数。
3. 求满足某些条件的元素个数。

容斥原理的一般形式如下：

如果有n个集合A₁、A₂、...、Aₙ，那么它们的并集中的元素个数可以表示为：

|A₁ ∪ A₂ ∪ ... ∪ Aₙ| = Σ(|Aᵢ|) - Σ(|Aᵢ₁ ∩ Aᵢ₂|) + Σ(|Aᵢ₁ ∩ Aᵢ₂ ∩ Aᵢ₃|) - ... + (-1)ⁿ⁻¹ |A₁ ∩ A₂ ∩ ... ∩ Aₙ|

其中，Σ 表示求和，|Aᵢ| 表示集合 Aᵢ 中元素的个数，|Aᵢ₁ ∩ Aᵢ₂| 表示集合 Aᵢ₁ 和 Aᵢ₂ 的交集中元素的个数，以此类推。

容斥原理的应用范围广泛，包括组合数学、概率论、计算机科学等领域。它可以帮助解决各种计数问题，包括排列、组合、概率计算等。在解决复杂问题时，容斥原理通常是一个强大的工具，可以帮助简化问题的分析和计算。

我们可以发现这道题中的答案实际上就等于：
放过的行数×行长度+放过的列数×列长度-抵消块数。

LL ans = tx * (y1 - y + 1)) + (ty * (x1 - x + 1)) - (2 * tx * ty));

#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
 
using namespace std;
typedef long long LL;
const int  N = 1e5 + 5;
int n, m, q;
int ax[N*4], ay[N*4];
 
void change(int* arr, int p, int y,int l,int r) {
	if (l == r) {
		arr[p] ^= 1;
		return;
	}
	LL mid = (l + r)/2;
	if (y <= mid)change(arr, p * 2, y, l, mid);
	if (y > mid)change(arr, p * 2 + 1, y, mid + 1, r);
	arr[p] = arr[p * 2] + arr[p * 2 + 1];
}
 
LL ask(int *arr,int p,int l,int r,int L,int R) {
	if (L<=l && R >= r) {
		return arr[p];
	}
	LL mid = (l + r) / 2;
	LL ret = 0;
	if (L <= mid)ret += ask(arr, p * 2, l, mid, L, R);
	if (R > mid)ret += ask(arr, p * 2 + 1, mid + 1, r, L, R);
	return ret;
}
 
int main() {
	cin >> n >> m >> q;
	for (int i = 1,op,x,y,x1,y1; i <= q; i++) {
		scanf("%d", &op);
		if (op == 1) {
			scanf("%d%d", &x, &y);
			change(ax, 1, x, 1, n);
			change(ay, 1, y, 1, m);
		}
		else {
			scanf("%d%d%d%d", &x, &y, &x1, &y1);
			LL tx = ask(ax, 1, 1, n, x, x1);
			LL ty = ask(ay, 1, 1, m, y, y1);
			LL ans = (LL)((LL)(tx * (y1 - y + 1)) + (LL)(ty * (x1 - x + 1)) - (LL)(2 * tx * ty));
			printf("%lld\n", ans);
		}
	}
	return 0;
}

树状数组

经过上述分析，显而易见，本题也可使用树状数组来做

#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
 
using namespace std;
typedef long long LL;
const int  N = 1e5 + 5;
int n, m, q;
int ax[N], ay[N],cx[N],cy[N];
 
void add(int* arr,int x,int p,int d) {
	for (; x<=p; x += x&-x) {
		arr[x] +=d;
	}
}
 
int sum(int* arr, int x) {
	int ans = 0;
	for (; x; x -= x & -x) {
		ans += arr[x];
	}
	return ans;
}
 
int main() {
	cin >> n >> m >> q;
	for (int i = 1, op, x, y, x1, y1; i <= q; i++) {
		scanf("%d", &op);
		if (op == 1) {
			scanf("%d%d", &x, &y);
			if (ax[x] == 1)
				add(cx, x, n, -1);
			else
				add(cx, x, n, 1);
			ax[x] ^= 1;
			if (ay[y] == 1)
				add(cy, y, m, -1);
			else
				add(cy, y, m, 1);
			ay[y] ^= 1;
		}
		else {
			scanf("%d%d%d%d", &x, &y, &x1, &y1);
			LL tx = sum(cx, x1) - sum(cx, x - 1);
			LL ty = sum(cy, y1) - sum(cy, y - 1);
			LL ans = (LL)((LL)(tx * (y1 - y + 1)) + (LL)(ty * (x1 - x + 1)) -(LL)( 2 * ty * tx));
			printf("%lld\n", ans);
		}
	}
	return 0;
}