首页 > 其他分享 >CF 1722E Counting Rectangles(前缀和)

CF 1722E Counting Rectangles(前缀和)

时间:2022-11-29 23:33:47浏览次数:72  
标签:包含 int h1 矩阵 cin long 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;
}

标签:包含,int,h1,矩阵,cin,long,1722E,Counting,Rectangles
From: https://www.cnblogs.com/Panmaru/p/16937044.html

相关文章

  • 数数字(Digit Counting)
    DigitCountingTimelimit:3.000secondsTrungisboredwithhismathematicshomeworks.Hetakesapieceofchalkandstartswritingasequenceofconsecutiveint......
  • Java 8 | Collectors counting() with Examples
    https://www.geeksforgeeks.org/java-8-collectors-counting-with-examples/Collectorscounting() methodisusedtocountthenumberofelementspassedinthestr......
  • [AGC005D] ~K Perm Counting
    [AGC005D]~KPermCounting智慧转化,但不是很难想到。首先考虑容斥,设\(f_i\)表示强制\(i\)个位置\(|P_i-i|=k\)的方案数,那么答案就为\(\sum_{i=0}^nf_i(n-i)!\),......
  • Hitachi2020E Odd Sum Rectangles
    Hitachi2020E看到\(\oplus\)操作和\(2^n-1\)时猜结论\(ans_{i,j}=\operatorname{popcount}(i\&j)\bmod2\),过不去,然后就不会了。然而令答案的二维前缀和为\(\opera......
  • LG4778 Counting swaps 题解
    LG4778Countingswaps给定你一个\(1\simn\)的排列\(p\),可进行若干次操作,每次选择两个整数\(x,y\),交换\(p_x,p_y\)。用最少的操作次数将给定排列变成单调上升的序......
  • Counting Rectangles(二维数组前缀和)
    题目链接题目描述:Youhave\(n\)rectangles,the\(i\)-threctanglehasheight\(h_i\)andwidth\(w_i\).Youareasked\(q\)queriesoftheform\(h_sw_sh_b......
  • CF1650G 『Counting Shortcuts』 题解
    从洛谷博客那里搬过来的(图论专题本来打算先挑最简单的做,结果做了两个多小时(题意就是让你找从起点\(s\)到终点\(t\)的最短路以及次短路个数,本题次短路长度指的是最短......
  • DTOJ 5932 Counting 题解
    题目链接portal题解认识到了生成函数很好用,于是摆了一篇题解10分直接dp,\(f_{i,j}\)表示走了\(i\)步之后,当前位置在\(j\)的方案数然后就有状态转移方程\(f_{i,......
  • CF1748E Yet Another Array Counting Problem 题解
    可能更好的阅读体验题目传送门题目大意给定一个长度为\(n\)的序列\(a\)和\(m\),定义\([l,r]\)的最左边的最大值为最小的\(l\lei\ler\)满足\(x_i=\max\{a_......
  • 题解 P4778【Counting swaps】
    problem一次操作指随意选定\(x,y\)并交换\(a_x,a_y\),请问有多少种方案,能用最少的操作次数重排一个排列\(a\)?\(n\leq10^5,P=10^9+7\)。solution0连边\(i\toa_i\)......