由 POJ3468 想到的线段树懒操作

发表于 分类于

这题被范围卡了挺久，线段树的懒操作是指访问到的指定区间如果在需要求的区间内部，那么就直接返回，这样，就遇到了一个问题，就是如何记录子区间的状态，用一个 deldel 变量来记录子区间的状态，注意，是子区间，这样我们就可以用精简的代码来完成更新区间查找区间的操作。

我的代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
#include <algorithm>
#include <cstdio>
#include <cstdlib>
#include <cstring>

using namespace std;
typedef long long LL;
const int MAX = 210000;

struct Seg {
  int l, r;
  LL val;
  LL del;
} seg[4 * MAX];
int arr[MAX];

void init(int k, int l, int r) {
  seg[k].l = l;
  seg[k].r = r;
  seg[k].del = 0;
  if (l == r) {
    seg[k].val = arr[l];
    return;
  }
  int mid = (l + r) >> 1;
  init(k << 1, l, mid);
  init(k << 1 | 1, mid + 1, r);
  seg[k].val = seg[k << 1].val + seg[k << 1 | 1].val;
}

void add(int k, int a, int b, LL v) {
  if (seg[k].l > b || seg[k].r < a) return;
  if (seg[k].l >= a && seg[k].r <= b) {
    seg[k].val += v * (seg[k].r - seg[k].l + 1);
    seg[k].del += v;
    return;
  }
  if (seg[k].del) {
    seg[k << 1].val += seg[k].del * (seg[k << 1].r - seg[k << 1].l + 1);
    seg[k << 1 | 1].val +=
        seg[k].del * (seg[k << 1 | 1].r - seg[k << 1 | 1].l + 1);
    seg[k << 1].del += seg[k].del;
    seg[k << 1 | 1].del += seg[k].del;
    seg[k].del = 0;
  }
  add(k << 1, a, b, v);
  add(k << 1 | 1, a, b, v);
  seg[k].val = seg[k << 1].val + seg[k << 1 | 1].val;
}

LL sum(int k, int a, int b) {
  if (seg[k].l > b || seg[k].r < a) return 0;
  if (seg[k].del) {
    seg[k << 1].val += seg[k].del * (seg[k << 1].r - seg[k << 1].l + 1);
    seg[k << 1 | 1].val +=
        seg[k].del * (seg[k << 1 | 1].r - seg[k << 1 | 1].l + 1);
    seg[k << 1].del += seg[k].del;
    seg[k << 1 | 1].del += seg[k].del;
    seg[k].del = 0;
  }
  if (seg[k].l >= a && seg[k].r <= b) return seg[k].val;
  LL k1 = sum(k << 1, a, b);
  LL k2 = sum(k << 1 | 1, a, b);
  return k1 + k2;
}

int main() {
  int n, m;
  int x, y;
  LL v;
  char op[10];  // freopen("in.txt","r",stdin);
  while (~scanf("%d%d", &n, &m)) {
    for (int i = 1; i <= n; i++) {
      scanf("%d", &arr[i]);
    }
    init(1, 1, n);
    for (int i = 0; i < m; i++) {
      scanf("%s%d%d", op, &x, &y);
      if (op[0] == 'Q') {
#ifdef DEBUG1 puts("******************");
        for (int i = 1; i < 4 * n; i++) {
          if (seg[i].l) {
            printf("%d %d %lld %lld\n", seg[i].l, seg[i].r, seg[i].val,
                   seg[i].del);
          }
        }
        puts("******************");
#endif printf("%lld\n", sum(1, x, y));
      } else {
        scanf("%lld", &v);
        add(1, x, y, v);
      }
    }
  }
  return 0;
}