首页 > 试题广场 >

牛妹吃豆子

[编程题]牛妹吃豆子


牛妹为了打比赛经常不吃饭，但是牛妹非常喜欢吃豆子，她经常会吃很多很多的豆子，所以牛妹不会感觉到饿， 自然就不想吃饭了。
现在牛妹有一个 个格子的棋盘.左下角的格子坐标为 ， 右上角的格子坐标为 .棋盘的每个格子都能放任意个豆子.
这时牛可乐带着一袋豆子走了过来， 打算跟牛妹分享这些豆子， 但是牛可乐并不想就这么简单的让牛妹吃到豆子， 所以牛可乐给牛妹出了一个难题.
现在牛可乐有  次操作，每次操作给出四个数字 : 表示牛可乐会将所有满足  这两个条件的位置上放一个豆子。
牛可乐放完豆子后给出了  次询问， 每次询问给出四个数字 : 表示询问所有满足  这两个条件的位置上中总共有多少个豆子.
这个问题可难住牛妹了， 牛妹想要吃到豆子就必须答对牛可乐的所有询问。



输入描述:
输入一行四个数字 
 表示棋盘的大小.有  次操作和  次询问
下面  行,每行四个数字 
表示牛可乐会将所有满足  这两个条件的位置上放一个豆子。
下面  行,每行四个数字 
表示询问所有满足  这两个条件的位置上中总共有多少个豆子。


输出描述:
每次询问，输出一行一个数字表示答案。
示例1

输入

2 2 1 1
1 1 2 2
1 1 2 1

输出

2

备注:



算法知识视频讲解
开通博客
头像 白色L号谢谢
发表于 2020-04-18 22:46:07
考点:二维差分，前缀和。这题题意很明确，做法也很明确，先对前k个操作差分，再进行二维前缀和，直接O(1)查询就行了。 #include <bits/stdc++.h> #include <unordered_map> using namespace std; typedef 展开全文
去ta的博客 赞 (3) 回复(0) 收起
头像 Meul
发表于 2020-04-19 17:06:32
Qustion 给你一个的矩阵，有 次操作，每次操作给出四个数字 : 表示牛可乐会将所有满足 这两个条件的位置上放一个豆子。 次询问， 每次询问给出四个数字 : 表示询问所有满足 这两个条件的位置上中总共有多少个豆子. Solution 二维差分+二位前缀和 ←不会的戳这里← 先根据次操作 展开全文
去ta的博客 赞 (3) 回复(1) 收起
头像 QQQQwQQQQ
发表于 2020-04-19 16:40:11
本题考查 二维差分+二维前缀和虽然点(1,1)在左下角，(n,m)在右上角，但画图翻转一下可发现无影响 1.二维前缀和，a[i][j]求得是从(1,1)开始到(i,j)这一块矩形的总和，公式如下 For(i, 1, n) For(j, 1, m) a[i][j] = a[i - 1][j] + a[ 展开全文
去ta的博客 赞 (2) 回复(0) 收起

问题信息

难度：
0条回答 3浏览

热门推荐

相关试题

牛妹吃豆子

扫一扫，把题目装进口袋

求职之前，先上牛客

扫描二维码，进入QQ群

扫描二维码，关注牛客公众号