POJ 1195 Mobile phones

早上起来A题，结果隔壁寝室的不知道在争论什么，声音真是大。。。。

让人都静不下心来。。

View Code

 1 #include <iostream>
 2 #include <stdio.h>
 3 using namespace std;
 4 const int maxn = 1050;
 5 int ans[maxn][maxn];
 6 
 7 int lowbit(int x)
 8 {
 9     return x & (-x);
10 }
11 
12 void mod(int temp[], int x, int c)
13 {
14     int i;
15     for(i=x;i<maxn;i+=lowbit(i))
16         temp[i]+=c;
17 }
18 
19 int getSum(int temp[],int x)
20 {
21     int i,sum=0;
22     for(i=x;i>0;i-=lowbit(i))
23         sum+=temp[i];
24     return sum;
25 }
26 int main()
27 {
28     int n,m,d,i,j;
29     scanf("%d%d",&n,&m);
30     for(i=0;i<maxn;i++)
31     for(j=0;j<maxn;j++)
32     ans[i][j]=n;
33     while(~scanf("%d",&d),d!=3)
34     {
35         int a,b,x,y;
36         if(d%2)
37         {
38             scanf("%d%d%d",&x,&y,&a);
39             mod(ans[x],y+1,a);
40         }
41         else
42         {
43             int sum=0;
44             scanf("%d%d%d%d",&a,&b,&x,&y);
45             for(i=a;i<=x;i++){
46                 sum+=getSum(ans[i],y+1)-getSum(ans[i],b);
47             }
48             printf("%d\n",sum);
49         }
50     }
51     return 0;
52 }
53 
54

原来真是够暴力。。o(╯□╰)o

这个的话就可以了。

View Code

 1 #include <iostream>
 2 #include <stdio.h>
 3 using namespace std;
 4 const int maxn = 1050;
 5 int ans[maxn][maxn],m;
 6 
 7 int lowbit(int x)
 8 {
 9     return x & (-x);
10 }
11 
12 void mod(int x, int y, int a)
13 {
14     int i,j;
15     for(i=x;i<=m;i+=lowbit(i))
16     {
17         for(j=y;j<=m;j+=lowbit(j))
18             ans[i][j]+=a;
19     }
20 }
21 
22 int getSum(int x,int y)
23 {
24     int i,j,sum=0;
25     for(i=x;i>0;i-=lowbit(i))
26     {
27         for(j=y;j>0;j-=lowbit(j))
28             sum+=ans[i][j];
29     }
30     return sum;
31 }
32 int main()
33 {
34     int n,d,i,j;
35     scanf("%d%d",&n,&m);
36     for(i=0;i<maxn;i++)
37     for(j=0;j<maxn;j++)
38     ans[i][j]=0;
39     while(~scanf("%d",&d),d!=3)
40     {
41         int a,b,x,y;
42         if(d%2)
43         {
44             scanf("%d%d%d",&x,&y,&a);
45             x++;
46             y++;
47             mod(x,y,a);
48         }
49         else
50         {
51             int sum=0;
52             scanf("%d%d%d%d",&a,&b,&x,&y);
53             a++;
54             b++;
55             x++;
56             y++;
57             sum=getSum(x,y)-getSum(x,b-1)-getSum(a-1,y)+getSum(a-1,b-1);
58             printf("%d\n",sum);
59         }
60     }
61     return 0;
62 }
63 
64