P1253 扶苏的问题

发表于 分类于 阅读次数： Waline： 本文字数： 693 阅读时长 ≈ 2 分钟

考点

  • 线段树

题解

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
97
98
99
100
101
102
103
104
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn = 2e6 + 50;
int n, m, a[maxn];

// mx：最大值
// v：覆盖标签是否有效
// tag_add：新增标签
// tag_cover：覆盖标签
struct {
  int l, r, v;
  ll mx, tag_add, tag_cover;
#define l(x) tr[x].l
#define r(x) tr[x].r
#define v(x) tr[x].v
#define mx(x) tr[x].mx
#define tag_add(x) tr[x].tag_add
#define tag_cover(x) tr[x].tag_cover
#define lc(x) x * 2
#define rc(x) x * 2 + 1
} tr[4 * maxn];

void up(int p) { mx(p) = max(mx(lc(p)), mx(rc(p))); }

void build(int p, int l, int r) {
  l(p) = l, r(p) = r;
  if (l == r) {
    mx(p) = a[l];
    return;
  }
  int mid = (l + r) / 2;
  build(lc(p), l, mid), build(rc(p), mid + 1, r);
  up(p);
}

void add(int p, ll k) {
  // 新增
  if (v(p)) {
    // 如果之前有覆盖
    mx(p) += k, tag_add(p) = 0, tag_cover(p) += k;
  } else {
    // 如果之前没覆盖
    mx(p) += k, tag_add(p) += k;
  }
}

// 覆盖
void cover(int p, ll k) {
  tag_add(p) = 0, tag_cover(p) = k, v(p) = 1, mx(p) = k;
}

void down(int p) {
  if (v(p)) {
    cover(lc(p), tag_cover(p)), cover(rc(p), tag_cover(p));
    v(p) = 0;
  } else if (tag_add(p)) {
    add(lc(p), tag_add(p)), add(rc(p), tag_add(p));
    tag_add(p) = 0;
  }
}

void update(int p, int l, int r, ll k, int opt) {
  if (l <= l(p) && r(p) <= r) {
    opt == 1 ? cover(p, k) : add(p, k);
    return;
  }
  down(p);
  int mid = (l(p) + r(p)) / 2;
  if (l <= mid) update(lc(p), l, r, k, opt);
  if (r > mid) update(rc(p), l, r, k, opt);
  up(p);
}

ll ask(int p, int l, int r) {
  if (l <= l(p) && r(p) <= r) return mx(p);
  down(p);
  int mid = (l(p) + r(p)) / 2;
  ll ans = LLONG_MIN;
  if (l <= mid) ans = max(ans, ask(lc(p), l, r));
  if (r > mid) ans = max(ans, ask(rc(p), l, r));
  return ans;
}

int main() {
  scanf("%d%d", &n, &m);
  for (int i = 1; i <= n; ++i) scanf("%d", &a[i]);
  build(1, 1, n);
  int opt, l, r, x;
  while (m--) {
    scanf("%d", &opt);
    if (opt == 1) {
      scanf("%d%d%d", &l, &r, &x);
      update(1, l, r, x, 1);
    } else if (opt == 2) {
      scanf("%d%d%d", &l, &r, &x);
      update(1, l, r, x, 2);
    } else {
      scanf("%d%d", &l, &r);
      printf("%lld\n", ask(1, l, r));
    }
  }
  return 0;
}

思路

因为本身也可以用0去覆盖，所以需要额外新建一个变量v来表示当前覆盖标记tag_cover是否有效；

累加标记tag_add则可以用0和非0来代表是否有效。

多标记处理主要分以下几种情况，注意，不可能同时两种标记都有效，这样一来就不知道标记处理的先后顺序了。

  1. 覆盖操作

    之前不管有覆盖标签还是新增标签，都给清除咯！

    所以得到下述代码：

    1
    tag_add(p) = 0, tag_cover(p) = k, v(p) = 1, mx(p) = k;

  2. 新增操作

    1. 之前有覆盖标签，即v(p) == 1

      直接把覆盖的数值新增即可，其余不变，很容易得到下述代码：

      1
      mx(p) += k, tag_add(p) = 0, tag_cover(p) += k;

    2. 之前有新增标签，即tag_add(p)不等于0

      所有的内容新增k即可

      1
      mx(p) += k, tag_add(p) += k;