CF 1722E Counting Rectangles（前缀和）()-其他

发表于： 11月 29, 2022 11月 29, 2022
分类：其他
标签：其他

CF 1722E Counting Rectangles（前缀和）()

题目分析

（摘自这篇博客，原博主关于包含的定义有错误，在此处做了修改）

给出一个长度为1e5的矩阵序列和1e5次询问，每次询问给出两个上下界矩阵，保证大矩阵包含小矩阵，请输出矩阵序列中所有能包含小矩阵且被大矩阵包含的矩阵面积和。矩阵不能被旋转。
包含：A包含B，当且仅当A的长宽都大于B。

由于拥有1e5次数的查询，所以我们可以简单的想到用前缀和来维护面积和，且可以发现题目询问的包含关系是满足单调的。所以我们要知道的就是，如何快速找到这个包含关系。用公式表示这个包含关系就是h1<h<h2，w1<w<w2(h和w不能等于下界或上界)。将问题抽象化，可以用a[x][y]表示长为x，宽为y的矩阵的面积，那么通过二维前缀和就可以O(1)查询包含小矩阵且被大矩阵包含的所有矩阵的面积和。

不明白的还可以参考官方题解

坑

注意题目关于包含的定义，题目要求不能与那两个矩阵的长或宽相等

参考代码

#include <bits/stdc++.h>
using namespace std;

const int N = 1010;
long long s[N][N];	// 记得开long long

int main()
{
	ios::sync_with_stdio(false);
	cin.tie(0), cout.tie(0);
	
	int t;
	cin >> t;
	while (t -- )
	{
		memset(s, 0, sizeof s);	// 重置数组
		
		int n, q;
		cin >> n >> q;
		
		while (n -- )
		{
			int h, w;
			cin >> h >> w;
			
			s[h][w] += h * w;	// (h, w)处加上矩阵的面积
		}
		
		for (int i = 1; i <= 1000; i ++ )
			for (int j = 1; j <= 1000; j ++ )
			{
				// 对数组求一遍前缀和，s[i][j]为这一点到原点处所有矩阵面积的和
				s[i][j] += s[i - 1][j] + s[i][j - 1] - s[i - 1][j - 1];
			}
		
		while (q -- )
		{
			int h1, w1, h2, w2;
			cin >> h1 >> w1 >> h2 >> w2;
			// 左上角为(h1 + 1, w1 + 1)、右下角为(h2 - 1, w2 - 1)
			cout << s[h2 - 1][w2 - 1] - s[h1][w2 - 1] - s[h2 - 1][w1] + s[h1][w1] << '\n';
		}
	}
	
	return 0;
}

————————

题目分析

（摘自这篇博客，原博主关于包含的定义有错误，在此处做了修改）

不明白的还可以参考官方题解

坑

注意题目关于包含的定义，题目要求不能与那两个矩阵的长或宽相等

参考代码

#include <bits/stdc++.h>
using namespace std;

const int N = 1010;
long long s[N][N];	// 记得开long long

int main()
{
	ios::sync_with_stdio(false);
	cin.tie(0), cout.tie(0);
	
	int t;
	cin >> t;
	while (t -- )
	{
		memset(s, 0, sizeof s);	// 重置数组
		
		int n, q;
		cin >> n >> q;
		
		while (n -- )
		{
			int h, w;
			cin >> h >> w;
			
			s[h][w] += h * w;	// (h, w)处加上矩阵的面积
		}
		
		for (int i = 1; i <= 1000; i ++ )
			for (int j = 1; j <= 1000; j ++ )
			{
				// 对数组求一遍前缀和，s[i][j]为这一点到原点处所有矩阵面积的和
				s[i][j] += s[i - 1][j] + s[i][j - 1] - s[i - 1][j - 1];
			}
		
		while (q -- )
		{
			int h1, w1, h2, w2;
			cin >> h1 >> w1 >> h2 >> w2;
			// 左上角为(h1 + 1, w1 + 1)、右下角为(h2 - 1, w2 - 1)
			cout << s[h2 - 1][w2 - 1] - s[h1][w2 - 1] - s[h2 - 1][w1] + s[h1][w1] << '\n';
		}
	}
	
	return 0;
}