POJ 1195 Mobile phones【二维树状数组】

题意：基础的二维数组，注意 0 + lowbit(0)会陷入无限循环-----

之前做一道一维的一直tle,就是因为这个--------------------------

 1 #include<iostream>  
 2 #include<cstdio>  
 3 #include<cstring> 
 4 #include <cmath> 
 5 #include<stack>
 6 #include<vector>
 7 #include<map> 
 8 #include<set>
 9 #include<queue> 
10 #include<algorithm>  
11 using namespace std;
12 
13 typedef long long LL;
14 const int INF = (1<<30)-1;
15 const int mod=1000000007;
16 const int maxn=1000005;
17 
18 int c[1055][1055];
19 int n;
20 
21 int lowbit(int x){ return x & (-x);}
22 
23 int sum(int x,int y){
24     int ret = 0,y1;
25     while(x > 0){
26         y1 = y;
27         while( y1 > 0){
28             ret += c[x][y1];y1 -= lowbit(y1);
29         }
30         x-=lowbit(x);
31     }
32     return ret;
33 }
34 
35 void add(int x,int y,int d){
36     int y1;
37     while(x <= n){
38         y1 = y;
39         while(y1 <= n){
40             c[x][y1] += d; y1 += lowbit(y1);
41         }
42         x += lowbit(x);
43     }
44 }
45 
46 int main(){
47     int cmd;
48     while(scanf("%d %d",&cmd,&n) != EOF){
49         memset(c,0,sizeof(c));
50         while(scanf("%d",&cmd) != EOF && cmd != 3){
51             if(cmd == 1){
52                 int x,y,d;
53                 scanf("%d %d %d",&x,&y,&d);x++;y++;
54                 add(x,y,d);
55             }
56             else{
57                 int x,y,xx,yy;
58                 int ret = 0;
59                 scanf("%d %d %d %d",&x,&y,&xx,&yy);
60                 x++;y++;xx++;yy++;
61                 ret = sum(xx,yy) - sum(x-1,yy) - sum(xx,y-1) + sum(x-1,y-1);
62                 printf("%d
",ret);
63             }
64         }
65     }
66     return 0;
67 }

View Code

话说好几天没有写代码了的说啊----

加油↖(^ω^)↗

goooooooooooooooooo----

POJ 1195 Mobile phones【 二维树状数组 】

POJ 1195 Mobile phones【二维树状数组】