做网站销售大概多少钱,滨州网站建设制作,58同城长沙招聘,wordpress解压主题没反应P3801 红色的幻想乡 - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)
题目背景
蕾米莉亚的红雾异变失败后#xff0c;很不甘心。
题目描述
经过上次失败后#xff0c;蕾米莉亚决定再次发动红雾异变#xff0c;但为了防止被灵梦退治#xff0c;她决定将红雾以奇怪的阵势释…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≤1051≤x1,x2,x≤nx1≤x21≤y1,y2,y≤my1≤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));
#includeiostream
#includecstdio
#includecstdlib
#includestring
#includecstring
#includecmath
#includectime
#includealgorithm
#includeutility
#includestack
#includequeue
#includevector
#includeset
#includemapusing 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 (Ll 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;
}
树状数组
经过上述分析显而易见本题也可使用树状数组来做
#includeiostream
#includecstdio
#includecstdlib
#includestring
#includecstring
#includecmath
#includectime
#includealgorithm
#includeutility
#includestack
#includequeue
#includevector
#includeset
#includemapusing 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 (; xp; 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);elseadd(cx, x, n, 1);ax[x] ^ 1;if (ay[y] 1)add(cy, y, m, -1);elseadd(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;
}