题目分析
(摘自这篇博客,原博主关于包含的定义有错误,在此处做了修改)
给出一个长度为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;
}
标签:包含,int,h1,矩阵,cin,long,1722E,Counting,Rectangles
From: https://www.cnblogs.com/Panmaru/p/16937044.html