Points in Rectangle(ツリー配列)
Description
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 integer T (≤ 10), denoting the number of test cases.
Each case starts with a line containing an integer q (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 x1 y1 x2 y2 meaning 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 between 0 and 1000 (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
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
Sample Output
Case 1:
2
0
2
3
标题:数回の操作
1.平面上の点を選択
2.x,y軸に平行な長方形を選択し、長方形に何点が含まれているかを尋ねます.
典型的な2 Dツリー配列
中には2つの注意点がある.
1.ツリー配列の下付き文字は0より大きくなければならない.
2.しばしば反発の定理に関連し、その中の境界取捨については、境界を区別するためにスケッチを描いたほうがよく、一度だけ統計することを保証しなければならない.
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 integer T (≤ 10), denoting the number of test cases.
Each case starts with a line containing an integer q (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 x1 y1 x2 y2 meaning 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 between 0 and 1000 (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
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
Sample Output
Case 1:
2
0
2
3
标题:数回の操作
1.平面上の点を選択
2.x,y軸に平行な長方形を選択し、長方形に何点が含まれているかを尋ねます.
典型的な2 Dツリー配列
#include<iostream>
#include<cstring>
#include<cstdio>
using namespace std;
int tree[1005][1005],N;
bool mark[1005][1005];
void update(int x,int y,int change)
{
while(x<=1004)
{
int y1=y;
while(y1<=1004)
{
tree[x][y1]+=change;
y1+=y1&(y1^(y1-1));
}
x+=x&(x^(x-1));
}
}
int query(int x,int y)
{
int coun=0;
while(x>0)
{
int y2=y;
while(y2>0)
{
coun+=tree[x][y2];
y2-=y2&(y2^(y2-1));
}
x-=x&(x^(x-1));
}
return coun;
}
int main()
{
int times;
scanf("%d",×);
for(int time=1;time<=times;++time)
{
memset(tree,0,sizeof(tree));
memset(mark,0,sizeof(mark));
int q;
printf("Case %d:
",time);
scanf("%d",&q);
for(int i=1;i<=q;++i)
{
int que;
scanf("%d",&que);
if(que)
{
int x1,y1,x2,y2;
scanf("%d%d%d%d",&x1,&y1,&x2,&y2);
// int c22=query(x2,y2);
printf("%d
",query(x2+1,y2+1)-query(x2+1,y1)-query(x1,y2+1)+query(x1,y1));
}
else
{
int x,y;
scanf("%d%d",&x,&y);
if(mark[x+1][y+1])
continue;
else
{
mark[x+1][y+1]=true;
update(x+1,y+1,1);
}
}
}
}
return 0;
}中には2つの注意点がある.
1.ツリー配列の下付き文字は0より大きくなければならない.
2.しばしば反発の定理に関連し、その中の境界取捨については、境界を区別するためにスケッチを描いたほうがよく、一度だけ統計することを保証しなければならない.