4C. Stars
stars
2023-09-11 14:15:29 时间
4C. Stars
2000ms
2000ms
65536KB
64-bit integer IO format: %I64d Java class name: Main
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 x y" 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 x y" 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.
View Code
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 x y" 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 x y" 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.
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
解题思路：二维树状数组模板题，注意范围，通常二维数状数组de范围是从1开始的，而题目要求从0开始，所以要偏移1.还有因为星星只有两种状态，为了避免连续对同一个星星进行同样的操作导致结果出错，需要一个数组进行标记状态！
1 #include <iostream> 2 #include <cstdio> 3 #include <cstring> 4 #include <cstdlib> 5 #include <vector> 6 #include <climits> 7 #include <algorithm> 8 #include <cmath> 9 #define LL long long 10 using namespace std; 11 const int maxn = 1010; 12 int tree[maxn][maxn]; 13 bool br[maxn][maxn]; 14 int lowbit(int x) { 15 return x&(-x); 16 } 17 void update(int x,int y,int val) { 18 int t; 19 while(x < maxn) { 20 t = y; 21 while(t < maxn) { 22 tree[x][t] += val; 23 t += lowbit(t); 24 } 25 x += lowbit(x); 26 } 27 } 28 int sum(int x,int y) { 29 int temp = 0,t; 30 while(x) { 31 t = y; 32 while(t) { 33 temp += tree[x][t]; 34 t -= lowbit(t); 35 } 36 x -= lowbit(x); 37 } 38 return temp; 39 } 40 int main() { 41 int m,i,j,a,b,c,d; 42 char s[5]; 43 scanf("%d",&m); 44 while(m--) { 45 scanf("%s",s); 46 if(s[0] == 'B') { 47 scanf("%d %d",&a,&b); 48 if(!br[a+1][b+1]) { 49 br[a+1][b+1] = true; 50 update(a+1,b+1,1); 51 } 52 } else if(s[0] == 'D') { 53 scanf("%d %d",&a,&b); 54 if(br[a+1][b+1]) { 55 update(a+1,b+1,-1); 56 br[a+1][b+1] = false; 57 } 58 } else if(s[0] == 'Q') { 59 scanf("%d %d %d %d",&a,&b,&c,&d); 60 if(a > b) swap(a,b); 61 if(c > d) swap(c,d); 62 b++;d++; 63 printf("%d\n",sum(b,d)+sum(a,c)-sum(a,d)-sum(b,c)); 64 } 65 } 66 return 0; 67 }