首页 > 其他 > 详细

poj 1195 Mobile phones

时间:2018-05-21 22:33:29      阅读:216      评论:0      收藏:0      [点我收藏+]

题意:

初始化一个矩阵,有几种操作:

1.X Y A,想坐标为(X,Y)的格子里面加A;

2.L B R T,查询L <= x <= R,B <= y <= T的范围内的数的和是多少。

思路:

二维树状数组,加一重循环查询前缀和。

代码:

 1 #include <stdio.h>
 2 #include <string.h>
 3 #include <algorithm>
 4 using namespace std;
 5 const int N = 1035;
 6 int c[N][N];
 7 int S;
 8 int lowbit(int x)
 9 {
10     return x&(-x);
11 }
12 void add(int x,int y,int cc)
13 {
14     for (int i = x;i <= S;i += lowbit(i)) c[i][y] += cc;
15 }
16 int getsum(int x,int y1,int y2)
17 {
18     int ans = 0;
19     for (int i = y1;i <= y2;i++)
20     {
21         for (int j = x;j > 0;j -= lowbit(j)) ans += c[j][i]; 
22     }
23     return ans;
24 }
25 int main()
26 {
27     int x;
28     for (;;)
29     {
30         scanf("%d",&x);
31         if (x == 3) break;
32         if (x == 0)
33         {
34             scanf("%d",&S);
35             memset(c,0,sizeof(c));
36         }
37         if (x == 1)
38         {
39             int a,b,num;
40             scanf("%d%d%d",&a,&b,&num);
41             a++,b++;
42             add(a,b,num);
43         }
44         if (x == 2)
45         {
46             int l,b,r,t;
47             scanf("%d%d%d%d",&l,&b,&r,&t);
48             l++,b++,r++,t++;
49             int cnt1 = getsum(l-1,b,t);
50             int cnt2 = getsum(r,b,t);
51             printf("%d\n",cnt2 - cnt1);
52         }
53     }
54     return 0;
55 }

 

poj 1195 Mobile phones

原文:https://www.cnblogs.com/kickit/p/9069590.html

(0)
(0)
   
举报
评论 一句话评论(0
关于我们 - 联系我们 - 留言反馈 - 联系我们:wmxa8@hotmail.com
© 2014 bubuko.com 版权所有
打开技术之扣,分享程序人生!