1266 - Points in Rectangle
Time Limit:2 second(s)
|
Memory Limit:32 MB
|
As the name says, this problem is about finding the number of points in a rectangle whose sides are parallel to axis. All the points and rectangles consist of 2D Cartesian co-ordinates. A point that lies in the boundary of a rectangle is considered inside.
Input
Input starts with an integerT (≤ 10), denoting the number of test cases.
Each case starts with a line containing an integerq (1 ≤ q ≤ 30000)denoting the number of queries. Each query is either one of the following:
1)0 x y, meaning that you have got a new point whose co-ordinate is(x, y). But the restriction is that, if a point(x, y)is already listed, then this query has no effect.
2)1 x1y1x2y2meaning that you are given a rectangle whose lower left co-ordinate is(x1, y1)and upper-right corner is(x2, y2);
your task is to find the number of points, given so far, that lie inside this rectangle. You can assume that(x1< x2, y1< y2).
You can assume that the values of the co-ordinates lie between0and1000(inclusive).
Output
For each case, print the case number in a line first. Then for each query type (2), you have to answer the number of points that lie inside that rectangle. Print each of the results in separated lines.
Sample Input
|
Output for Sample Input
|
1
9
0 1 1
0 2 6
1 1 1 6 6
1 2 2 5 5
0 5 5
1 0 0 6 5
0 3 3
0 2 6
1 2 1 10 10
|
Case 1:
2
0
2
3
|
Note
Dataset is huge, use faster I/O methods.
题意:在(0,0)-(1000,1000)的矩阵中给定若干个询问,询问分为两种,第一种把某个点置1,第二种,统计一个矩形里面1的个数(包含边界),很明显使用二维树状数组实现(单点更新,范围求和)。
代码:
#include<iostream>
#include<cstdio>
#include<cstring>
using namespace std;
const int MAXN = 1111,BOUND = 1001;
int c[MAXN][MAXN],t,q,type,x1,x2,y1,y2;
void build(){
memset(c,0,sizeof(c));
}
int lowbit(int x){
return x&(-x);
}
int sum(int px,int py){
int s = 0;
for(int i=px;i>0;i-=lowbit(i)){
for(int j=py;j>0;j-=lowbit(j)){
s+=c[i][j];
}
}
return s;
}
void add(int px,int py){
for(int i=px;i<=BOUND;i+=lowbit(i)){
for(int j=py;j<=BOUND;j+=lowbit(j)){
c[i][j]++;
}
}
}
int QueryPoint(int x,int y){
return sum(x,y)-sum(x-1,y)-sum(x,y-1)+sum(x-1,y-1);
}
int QueryRec(int x1,int y1,int x2,int y2){//询问矩阵时候要注意别写错坐标
return sum(x2,y2)-sum(x1-1,y2)-sum(x2,y1-1)+sum(x1-1,y1-1);
}
int main(){
scanf("%d",&t);
for(int cas=1;cas<=t;cas++){
build();
scanf("%d",&q);
printf("Case %d:\n",cas);
while(q--){
scanf("%d",&type);
if(!type){
scanf("%d%d",&x1,&y1);
x1++,y1++;
if(!QueryPoint(y1,x1))add(y1,x1);
}else{
scanf("%d%d%d%d",&x1,&y1,&x2,&y2);
x1++,y1++,x2++,y2++;
printf("%d\n",QueryRec(y1,x1,y2,x2));
}
}
}
return 0;
}
分享到:
相关推荐
LightOJ-已解决代码我所有的Light Online Judge的解决问题代码。
轻描淡写 像Codeforces编辑模式一样在lightoj上发表社论!
LightOJ-solutions
leetcode中国 数据结构和算法编码 议程 :balloon: 不是为了比赛,而是为了训练和兴趣。 Python3 你可以在这里找到我的 LeetCode 解决方案:(等待打开) ...LightOJ 1012 --- dfs transform 13. HDU 1495 --- compl
LightOJ
解析编程问题,并将其发送给CHelper插件以实现IntelliJ IDEA。 竞争性伴侣解析程序...-HackerRank-HDU在线法官-Kattis-LightOJ-NYTD在线法官-PEG法官-POJ-QDUOJ-Timus-URI在线法官 支持语言:English (United States)
问题教程:一个包含有关LightOJ问题的教程的存储库
leetcode 2 和 c 动态规划 动态规划相关问题的解答。 这些问题来自各种在线评委,包括 、 、 等。 解决方案是用 C++ 编码的。 —— —— —— —— —— —— —— —— —— —— —— —— ...——
光OJ 收集我在发现的一些问题的解决方案
已解决的编程问题 Online Judges 这个存储库包含我解决的各种在线法官的编程问题的解决方案,即 UVa、Topcoder、Codeforces、Hackerrank、LightOj、Spoj、Project Euler 等。
race_words = [“后缀数组”,“前缀特里”,“动态编程”,“竞赛”,“ codeforces”,“编程”,“竞争性编程”,“算法”,“数据结构”,“ codeforces”,“ light oj”,“ lightoj”,“ spoj”,“堆栈”,...
这是乔杜里医学博士。 伊斯玛姆·拉赫曼(Ishmam Rahman) :closed_mailbox_with_raised_flag: 联络我: ... LightOJ: ://lightoj.com/user/ishmam64 脸书: : 目标:使自己在新技术的海洋中立足,在这里我可
描述在这里,您可以从uva,lightoj,spoj,timus等不同的在线法官那里找到我解决的问题。
开心农场java源码AA Noman Ansary 你好呀! 我的名字是AA Noman Ansary 。 但我更喜欢被称为Showrav...问题解决:LightOJ。 代码部队。 蒂姆斯。 紫外线。 成就 以下是我的一些显著成就: BRAC 大学副校长证书。 (2019)
这个仓库是关于什么的 创建该存储库是为了组织与数据结构和算法有关的问题的解决方案。 并且,如果可能的话,为学习与数据结构和算法有关的各种概念提供一种更简单的方法。 以下评委使用的问题 ...
测试程序TestProgram 是针对竞争性编程程序(即 Codeforces、lightOJ、OmegaUp 等)的专用测试工具。 当我们解决问题时,我们必须非常小心,并致力于解决所有可能的情况。 我们的解决方案在登顶前正确解决的测试用例...
problemSolving