首页 > 代码库 > UESTC 4 Complete Building the Houses 树状数组

UESTC 4 Complete Building the Houses 树状数组

2024-07-14 07:58:41   213人阅读

题目来源：

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 }

 


联系
我们