Subject link: http://acm.hdu.edu.cn/showproblem.php?pid=2642
——————— ——————————————————————–.
Stars
Time Limit: 5000/2000 MS (Java/Others) Memory Limit: 32768/65536 K (Java/Others)
Total Submission(s): 1675 Accepted Submission(s): 706
Problem Description
Yifenfei is a romantic guy and he likes to count the stars in the sky.
To make the problem easier, we considerate the sky is a two-dimension plane.Sometimes the star will be bright and sometimes the star will be dim.At first,there is no bright star in the sky, then some information will be given as “B xy” where’B’ represent bright and x represent the X coordinate and y represent the Y coordinate means the star at (x,y) is bright,And the’D’ in “D xy ”Mean the star at(x,y) is dim.When get a query as “Q X1 X2 Y1 Y2”, you should tell Yifenfei how many bright stars there are in the region correspond X1,X2,Y1,Y2.
There is only one case.
Input
The firs t line contain a M(M <= 100000), then M line followed.
each line start with a operational character.
if the character is B or D,then two integer X,Y (0 <=X ,Y<= 1000)followed.
if the character is Q then four integer X1,X2,Y1,Y2(0 <=X1,X2,Y1,Y2<= 1000) followed.
Output
For each query, output the number of bright stars in one line.
Sample Input
5
B 581 145
B 581 145
Q 0 600 0 200
D 581 145
Q 0 600 0 200
Sample Output
1
0
Author
teddy
Source
Millions of Qin Guan will eventually belong to Chu
————————————————————————————————.
The main idea of the topic:
There are a total of M operations
There are 3 types of operations
1) A star appears at the position of B xy (x, y)
2) D xy The star at the position (x, y) disappeared
3) Q x1 x2 y1 y1 Query how many stars are in the rectangle
Question-solving ideas:
There is no idea What can be said, because it is dynamic, it must be a two-dimensional tree array, which can be maintained.
Note that there can be at most one star under the same coordinate. If you delete it, there will be no stars in this coordinate.
Note When doing the question, pay attention to the range of coordinates, because it starts from 0 so all coordinates must be added by 1 when calculating, otherwise it will be infinite TLE
< p>Attach this question code
—————————————————————————————.
#include
Subject link: http://acm.hdu.edu.cn/showproblem.php?pid=2642
— ————————————————————————————.
Stars
Time Limit: 5000/2000 MS (Java /Others) Memory Limit: 32768/65536 K (Java/Others)
Total Submission(s): 1675 Accepted Submission(s): 706
Problem Description
Yifenfei is a romantic guy and he likes to count the stars in the sky.
To make the problem easier, we considerate the sky is a two-dimension plane.Sometimes the star will be bright and sometimes the star will be dim.At first,there is no bright star in the sky, then some information will be given as “B xy” where’B’ rep resent bright and x represent the X coordinate and y represent the Y coordinate means the star at (x,y) is bright,And the’D’ in “D xy” mean the star at(x,y) is dim.When get a query as “Q X1 X2 Y1 Y2”,you should tell Yifenfei how many bright stars there are in the region correspond X1,X2,Y1,Y2.
There is only one case.
Input
The first line contain a M(M <= 100000), then M line followed.
each line start with a operational character.
if the character is B or D, then two integer X,Y (0 <=X,Y<= 1000) followed.
if the character is Q then four integer X1,X2,Y1,Y2(0 <=X1,X2,Y1,Y2<= 1000) followed .
Output
For each query, output the number of bright stars in one line.
Sample Input
5
B 581 145
B 581 145
Q 0 600 0 200
D 581 145
Q 0 600 0 200
Sample Output
1
0
Author
teddy
Source
Millions of Qin Guan will eventually belong to Chu
——————————————————————— ——————–.
The main idea of the topic:
There are a total of M operations
There are a total of 3 operations
1) B xy A star appears at the position (x, y)
2) The star at the position D xy (x, y) disappears
3) Q x1 x2 y1 y1 Query how many stars are in the rectangle
< p>Question-solving idea:
There is nothing to say in the idea, because it is dynamic, it must be a two-dimensional tree array, which can be maintained.
Note that the same coordinates There can only be one star in the bottom. If you delete it, there will be no stars in this coordinate.
Note When doing the question, pay attention to the range of the coordinates, because it starts from 0 when calculating All coordinates must be added by 1, otherwise there will be infinite TLE
Attach the code of this question
———————————————————————— —————.
#include