首页 > 试题广场 >

牛妹吃豆子

[编程题]牛妹吃豆子

时间限制：C/C++ 1秒，其他语言2秒空间限制：C/C++ 256M，其他语言512M
算法知识视频讲解

牛妹为了打比赛经常不吃饭，但是牛妹非常喜欢吃豆子，她经常会吃很多很多的豆子，所以牛妹不会感觉到饿，自然就不想吃饭了。

现在牛妹有一个 $n∗m$ 个格子的棋盘.左下角的格子坐标为 $(1, 1)$ ，右上角的格子坐标为 $(n,m)$ .棋盘的每个格子都能放任意个豆子.

这时牛可乐带着一袋豆子走了过来，打算跟牛妹分享这些豆子，但是牛可乐并不想就这么简单的让牛妹吃到豆子，所以牛可乐给牛妹出了一个难题.
现在牛可乐有 $k$ 次操作，每次操作给出四个数字 $x1,y1,x2,y2$ : 表示牛可乐会将所有满足 $x1\leq x\leq x2,y1\leq y \leq y2$ 这两个条件的位置上放一个豆子。
牛可乐放完豆子后给出了 $q$ 次询问，每次询问给出四个数字 $x1,y1,x2,y2$ : 表示询问所有满足 $x1\leq x\leq x2,y1\leq y \leq y2$ 这两个条件的位置上中总共有多少个豆子.
这个问题可难住牛妹了，牛妹想要吃到豆子就必须答对牛可乐的所有询问。

输入描述:

输入一行四个数字 $n,m,k,q$

$n,m$ 表示棋盘的大小.有 $k$ 次操作和 $q$ 次询问

下面 $k$ 行,每行四个数字 $x1,y1,x2,y2$

表示牛可乐会将所有满足 $x1\leq x\leq x2,y1\leq y \leq y2$ 这两个条件的位置上放一个豆子。

下面 $q$ 行,每行四个数字 $x1,y1,x2,y2$

表示询问所有满足 $x1\leq x\leq x2,y1\leq y \leq y2$ 这两个条件的位置上中总共有多少个豆子。

输出描述:

每次询问，输出一行一个数字表示答案。

示例1

输入

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

输出

备注:

算法知识视频讲解

这道题你会答吗？花几分钟告诉大家答案吧！

提交观点

问题信息

难度：

0条回答 0收藏 2浏览

热门推荐

相关试题

牛妹吃豆子

扫描二维码，关注牛客网
意见反馈
下载牛客APP，随时随地刷题

扫一扫，把题目装进口袋

求职之前，先上牛客: 扫描二维码，进入QQ群



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

公司地址：北京市朝阳区北苑路北美国际商务中心K1座一层-北京牛客科技有限公司
联系方式：010-60728802 投诉举报电话：010-57596212（朝阳人力社保局）
牛客科技© All rights reserved admin@nowcoder.com
京ICP备14055008号-4 增值电信业务经营许可证营业执照人力资源服务许可证
京公网安备 11010502036488号