首页 > 代码库 > hdu 1166 敌兵布阵 解题报告

hdu 1166 敌兵布阵 解题报告

2024-07-18 12:02:29   220人阅读

题目链接：http://acm.hdu.edu.cn/showproblem.php?pid=1166

题目意思：给出 N 个数你，通过对某些数进行更改（或者 + 或者 -），当输入的是 Query 的时候，需要计算出 某个区间的和。

     树状数组第一题，算是模板吧 ^_^

     有个小细节，wa 了几次，细心~细心~~~细心

     

 1 #include <iostream> 2 #include <cstdio> 3 #include <cstdlib> 4 #include <cstring> 5 #include <string> 6 using namespace std; 7  8 const int maxn = 5e4 + 5; 9 int c[maxn];10 int n;11 12 int lowbit(int x)        // 求某个点的管辖范围13 {14     return x & (-x);15 }16 17 int query(int x)18 {19     int s = 0;20     while (x > 0)21     {22         s += c[x];23         x -= lowbit(x);  // 得到 x 这个点的管辖区间的下个区间的管辖点24     }25     return s;26 }27 28 void insert(int x, int num)29 {30     while (x <= n)31     {32         c[x] += num;33         x += lowbit(x);   // 得到的该点的父节点的值，比如x = 4，下次就能得到834     }35 36 }37 38 int main()39 {40     int T, tmp;41     while (scanf("%d", &T) != EOF)42     {43         for (int j = 1; j <= T; j++)44         {45             memset(c, 0, sizeof(c));     // 一开始不记得写这个，错了，细心啊~~~~46             scanf("%d", &n);47             for (int i = 1; i <= n; i++)48             {49                 scanf("%d", &tmp);50                 insert(i, tmp);51             }52             printf("Case %d:\n", j);53             string command;54             int l, r;55             while (cin >> command)56             {57                 if (command == "End")58                     break;59                 scanf("%d%d", &l, &r);60                 if (command == "Query")61                     printf("%d\n", query(r)-query(l-1));62                 else if (command == "Add")63                     insert(l, r);64                 else if (command == "Sub")65                     insert(l, -r);66             }67         }68     }69     return 0;70 }

 


联系
我们