专栏首页wymHDU 6514 Monitor 二维前缀和

HDU 6514 Monitor 二维前缀和

Monitor

s[i][j]表示i 行j列所有面积之和,二维前缀和

#include <bits/stdc++.h>
using namespace std;
int main()
{
	int n, m, q, a, b, c, d;
	while (scanf("%d%d", &n, &m) > 0)
	{
		int s[n + 5][m + 5];
		memset(s, 0, sizeof(s));
		scanf("%d", &q);
		while (q--)
		{
			scanf("%d%d%d%d", &a, &b, &c, &d);
			s[a][b]++;
			s[c+1][d+1]++;
			s[a][d+1]--;
			s[c+1][b]--;
		}	
		for(int i=1;i<=n;i++)
			for(int j=1;j<=m;j++)
				s[i][j] = s[i][j] + s[i-1][j] + s[i][j-1] - s[i-1][j-1]; 
	
		for(int i=1;i<=n;i++)
			for(int j=1;j<=m;j++)
				if(s[i][j]>0)
					s[i][j] = 1;

		for(int i=1;i<=n;i++)
			for(int j=1;j<=m;j++)
				s[i][j] = s[i][j] + s[i-1][j] + s[i][j-1] - s[i-1][j-1];

		scanf("%d", &q);
		while (q--)
		{
			scanf("%d%d%d%d", &a, &b, &c, &d);
			if ((c - a + 1) * (d - b + 1) == s[c][d] - s[a - 1][d] - s[c][b - 1] + s[a - 1][b - 1])
				printf("YES\n");
			else
				printf("NO\n");
		}
	}
}

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

我来说两句

0 条评论
登录 后参与评论

相关文章

  • RMQ——模板

     RMQ(rang minimun/maximun query,区间最佳查询)的主要思想是动态规划。

    用户2965768
  • HDU 6628 (2019杭电第五场 1005) permutation 1 (全排列)

    题意:求 n的 全排列 差值序列(后一项减前一项 n-1项) 第 k 小的全排列,2 <=n<=20, 1<= k <=min(10000,n!)

    用户2965768
  • [USACO06JAN]牛的舞会 Tarjan模版

    用户2965768
  • Codeforces Round #513 C. Maximum Subrectangle(思维)

    题目链接:http://codeforces.com/contest/1060/problem/C

    Ch_Zaqdt
  • 1002: C语言实验题——两个数比较

    描述:求2个数中较大者。 输入:第一行为测试的数据组数N,接下来的N行分别是两个待比较的整数 输出:输出N行,每一行的值为每组数中较大的整数 样例输入:2...

    bboysoul
  • 04:病毒

    04:病毒 查看 提交 统计 提问 总时间限制:1000ms内存限制:65535kB描述     有一天,小y突然发现自己的计算机感染了一种病毒!还好,小y发现...

    attack
  • 冒泡排序

    #include<stdio.h> void BubbleSort(int n,int a[]) { for(int i=0;i<n-1;i++) ...

    用户1624346
  • cf1000F. One Occurrence(线段树 set)

    首先把询问离线,预处理每个数的\(pre, nxt\),同时线段树维护\(pre\)(下标是\(pre\),值是\(i\)),同时维护一下最大值

    attack
  • cf1056B. Divide Candies(数论 剩余系)

    求满足\(i^2 + j^2 \% M = 0\)的数对\((i, j)\)的个数,\(1 \leqslant i, j \leqslant 10^9, M \...

    attack
  • 【Codeforces 707B】Bakery 水题

    饶文津

扫码关注云+社区

领取腾讯云代金券