uva 12501 Bulky process of bulk reduction 线段树(mid)

　　线段树的应用。【成段更新，成段查询】

　　因为每个位置都要乘上相应的权值，而且乘的大小依次递增，所以就要构建两棵线段树，一棵记录原始值，另外一个就乘上它所在位置的标号就好了。query的时候就直接两部分相减，得到答案。例如，第一棵树的结点记录为a[i]，那么第二棵树的就是i*a[i]了。

　　其实这题不难，不过打上来是为了提醒自己注意延迟标记的更新。这题因为延迟标记更新搞错了，所以就产生了严重错误。同时，这次也要感谢Troy师兄，让我明白了debug还是要靠自己的，不是所有问题都有oj帮你检测代码是否通过，不是所有问题的解决都会有标程给你。所以，要证明一个算法没问题，最好还是自己打个暴力的程序，跑一跑随机的数据，然后跟自己优化的算法作比较。

暴力统计以及随机数据产生的代码：

View Code

 1 #define prog 1
 2 
 3 #if prog == 0
 4 
 5 #include <cstdio>
 6 #include <cstring>
 7 
 8 const int maxn = 100;
 9 typedef long long ll;
10 int a[maxn];
11 
12 int main() {
13     int T;
14 
15     freopen("in", "r", stdin);
16     freopen("cmp", "w", stdout);
17 
18     scanf("%d", &T);
19     while (T--) {
20         int n, m;
21 
22         puts("");
23         scanf("%d%d", &n, &m);
24         for (int i = 1; i <= n; i++) {
25             a[i] = 100;
26         }
27         while (m--) {
28             char op[10];
29 
30             scanf("%s", op);
31             if (!strcmp(op, "query")) {
32                 ll ans = 0;
33 
34                 int l, r;
35 
36                 scanf("%d%d", &l, &r);
37                 for (int i = l; i <= r; i++) {
38                     ans += a[i] * (i - l + 1);
39                 }
40                 printf("%lld\n", ans);
41             } else {
42                 int l, r, d;
43 
44                 scanf("%d%d%d", &l, &r, &d);
45                 for (int i = l; i <= r; i++) {
46                     a[i] += d;
47                 }
48             }
49         }
50     }
51 
52     return 0;
53 }
54 
55 #endif
56 
57 #if prog == 1
58 
59 #include <cstdio>
60 #include <ctime>
61 #include <cmath>
62 #include <algorithm>
63 #include <cstdlib>
64 
65 using namespace std;
66 
67 int main() {
68     int T;
69 
70     freopen("in", "w", stdout);
71     scanf("%d", &T);
72     printf("%d\n", T);
73 
74     srand(time(NULL));
75     while (T--) {
76         int n = rand() % 10 + 40, m = rand() % 10 + 40;
77 
78         printf("%d %d\n", n, m);
79         while (m--) {
80             if (rand() & 1) {
81                 int a = rand() % n + 1, b = rand() % n + 1;
82 
83                 if (a > b) swap(a, b);
84                 printf("query %d %d\n", a, b);
85             } else {
86                 int a = rand() % n + 1, b = rand() % n + 1;
87 
88                 if (a > b) swap(a, b);
89                 printf("change %d %d %d\n", a, b, rand() % 2000 - 1000);
90             }
91         }
92     }
93 
94     return 0;
95 }
96 
97 #endif

AC代码：

View Code

  1 #include <cstdio>
  2 #include <cstring>
  3 #include <algorithm>
  4 #include <cstdlib>
  5 
  6 using namespace std;
  7 
  8 #define lson l, m, rt << 1
  9 #define rson m + 1, r, rt << 1 | 1
 10 typedef long long ll;
 11 
 12 const int maxn = 100005;
 13 ll sum1[maxn << 2], sum2[maxn << 2], late[maxn << 2];
 14 
 15 void up(int rt) {
 16     int ls = rt << 1, rs = rt << 1 | 1;
 17 
 18     sum1[rt] = sum1[ls] + sum1[rs];
 19     sum2[rt] = sum2[ls] + sum2[rs];
 20 }
 21 
 22 void down(int rt, int l, int r) {
 23     if (late[rt]) {
 24         int ls = rt << 1, rs = rt << 1 | 1;
 25         int m = (l + r) >> 1;
 26 
 27         late[ls] += late[rt];
 28         late[rs] += late[rt];
 29 
 30         sum1[ls] += late[rt] * (m - l + 1);
 31         sum1[rs] += late[rt] * (r - m);
 32 
 33         sum2[ls] += late[rt] * ((ll)l + m) * (m - l + 1) / 2;
 34         sum2[rs] += late[rt] * ((ll)m + 1 + r) * (r - m) / 2;
 35 
 36         late[rt] = 0;
 37 //        printf("l %d r %d  %lld %lld %lld %lld\n", l, r, sum1[ls], sum1[rs], sum2[ls], sum2[rs]);
 38     }
 39 }
 40 
 41 void build(int l, int r, int rt) {
 42     late[rt] = 0;
 43     if (l == r) {
 44         sum1[rt] = 100;
 45         sum2[rt] = 100 * l;
 46 
 47         return ;
 48     }
 49     int m = (l + r) >> 1;
 50 
 51     build(lson);
 52     build(rson);
 53     up(rt);
 54 }
 55 
 56 void update(int L, int R, ll key, int l, int r, int rt) {
 57     if (L <= l && r <= R) {
 58 //        printf("l %d r %d  %lld\n", l, r, late[rt]);
 59         late[rt] += key;
 60         sum1[rt] += key * (r - l + 1);
 61         sum2[rt] += key * ((ll)l + r) * (r - l + 1) / 2;
 62 
 63         return ;
 64     }
 65     int m = (l + r) >> 1;
 66 
 67     down(rt, l, r);
 68     if (L <= m) update(L, R, key, lson);
 69     if (m < R) update(L, R, key, rson);
 70     up(rt);
 71 //    printf("%d %d : %lld %lld\n", l, r, sum1[rt], sum2[rt]);
 72 }
 73 
 74 ll query(int L, int R, int l, int r, int rt) {
 75     if (L <= l && r <= R) {
 76 //        printf("query %lld %lld\n", sum1[rt], sum2[rt]);
 77         return sum2[rt] - sum1[rt] * (L - 1);
 78     }
 79     int m = (l + r) >> 1;
 80     ll ret = 0;
 81 
 82     down(rt, l, r);
 83     if (L <= m) ret += query(L, R, lson);
 84     if (m < R) ret += query(L, R, rson);
 85 
 86     return ret;
 87 }
 88 
 89 int main() {
 90     int T;
 91     char op[10];
 92 
 93 //    freopen("in", "r", stdin);
 94 //    freopen("out", "w", stdout);
 95 
 96     scanf("%d", &T);
 97 
 98     for (int cc = 1; cc <= T; cc++) {
 99         int n, m;
100 
101         scanf("%d%d", &n, &m);
102         build(1, n, 1);
103         printf("Case %d:\n", cc);
104 
105         while (m--) {
106             scanf("%s", op);
107             if (!strcmp(op, "query")) {
108                 int a, b;
109 
110                 scanf("%d%d", &a, &b);
111                 printf("%lld\n", query(a, b, 1, n, 1));
112             } else {
113                 int a, b;
114                 ll c;
115 
116                 scanf("%d%d%lld", &a, &b, &c);
117                 update(a, b, c, 1, n, 1);
118             }
119         }
120     }
121 
122     return 0;
123 }

　　继续学习如何debug！

——written by Lyon