首页 > 其他 > 详细

UESTC 4 Complete Building the Houses 树状数组

时间:2014-07-27 23:27:59      阅读:324      评论:0      收藏:0      [点我收藏+]

题目来源:

http://acm.uestc.edu.cn/#/problem/show/4

分析:就是一个很普通的区间修改,单点查询的树状数组,但是今天忘记吃药了,一直写不对,中午迷迷糊糊地,直接把数据读入到数组里而不是update,然后又总是考虑后面的数被减到0以下要怎么处理,其实根本不用考虑,直接判断大于0就行了,要是修改那些值,就无法满足数组a[]的性质了(a[]是原式的做差,a[i] = x[i] - x[i-1], a[1] = x[1])。想想还是贴出来纪念一下(这有什么好纪念的?!)

 

 1 #include<cstdio>
 2 #include<cstring>
 3 using namespace std;
 4 
 5 int n, m, T;
 6 long long a[100100];
 7 long long ans;
 8 int lowbit(int x)
 9 {
10     return x & -x;
11 }
12 void update(int x, long long val)
13 {
14     for (int i = x; i <= n; i += lowbit(i))
15         a[i] += val;
16 }
17 long long query(int x)
18 {
19     long long ans = 0;
20     for (int i = x; i > 0; i -= lowbit(i))
21         ans += a[i];
22     return ans;
23 }
24 int main()
25 {
26     int cas = 0;
27     scanf("%d", &T);
28     while(T--)
29     {
30         memset(a, 0, sizeof(a));
31         scanf("%d %d", &n, &m);
32         long long x;
33         for (int i = 1; i <= n; i++){
34             scanf("%lld", &x);
35             update(i, x);
36             update(i+1, -x);
37         }
38         ans = 0;
39         for (int i = 1; i <= n; i++){
40             int tmp = query(i);
41             if (tmp > 0){
42                 ans += tmp;
43                 update(i, -tmp);
44                 update(i+m, tmp);
45             }
46         }
47         cas++;
48         printf("Case #%d: %lld\n", cas, ans);
49     }
50     return 0;
51 }

 

UESTC 4 Complete Building the Houses 树状数组,布布扣,bubuko.com

UESTC 4 Complete Building the Houses 树状数组

原文:http://www.cnblogs.com/james47/p/3871934.html

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