区间历史最值线段树记录

区间+/chkmin/求最值/求历史最值

Description

维护一个线段树，使得可以实现区间加、区间 chkmin、求区间和、区间历史最大值、区间历史最大值。

Solution

先不考虑区间 chkmin 和历史最值，可以直接对于每个线段树节点维护一个 tag，每次 addtag 更新。

加上区间历史最值后，先考虑对于单个线段树节点怎么更新。

容易发现对于一个节点，在它下传标记之前一定就是很多次整体加某个数，并且儿子的 sumsum 和 maxmax 数组是不会变的。

考虑维护 tag2[x]tag2[x] 表示 xx 这个节点上次下传标记到当前时刻的最大前缀和，那么每次下传标记时先让 maxb[son]←maxa[son]+tag2[x]maxb[son]\leftarrow maxa[son]+tag2[x] 再更新 maxa[son]maxa[son] 就可以维护区间历史最值了。

加上区间 chkmin 就用吉司机线段树的技巧维护区间最大值、次大值，并且由于这里最大值和非最大值有些操作是分开的，所以需要对于最大、非最大值分别维护 tag。

时间复杂度：O(nlog⁡2n)O(n\log^2 n)。

Code

Code
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
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
#include <bits/stdc++.h>

// #define int int64_t

const int kMaxN = 5e5 + 5;

int n, m;
int a[kMaxN];

struct SGT {
  int maxa[kMaxN * 4], maxb[kMaxN * 4];
  int cnt[kMaxN * 4], se[kMaxN * 4];
  int tag1[kMaxN * 4], tag2[kMaxN * 4], tag3[kMaxN * 4], tag4[kMaxN * 4];
  int64_t sum[kMaxN * 4];

  void pushup(int x) {
    sum[x] = sum[x << 1] + sum[x << 1 | 1];
    maxa[x] = std::max(maxa[x << 1], maxa[x << 1 | 1]);
    maxb[x] = std::max(maxb[x << 1], maxb[x << 1 | 1]);
  
    if (maxa[x << 1] == maxa[x << 1 | 1]) {
      se[x] = std::max(se[x << 1], se[x << 1 | 1]);
      cnt[x] = cnt[x << 1] + cnt[x << 1 | 1];
    } else if (maxa[x << 1] > maxa[x << 1 | 1]) {
      se[x] = std::max(se[x << 1], maxa[x << 1 | 1]);
      cnt[x] = cnt[x << 1];
    } else {
      se[x] = std::max(maxa[x << 1], se[x << 1 | 1]);
      cnt[x] = cnt[x << 1 | 1];
    }
  }

  void addtag(int x, int l, int r, int v1, int v2, int v3, int v4) {
    maxb[x] = std::max(maxb[x], maxa[x] + v2);
    tag2[x] = std::max(tag2[x], tag1[x] + v2);
    tag4[x] = std::max(tag4[x], tag3[x] + v4);
    maxa[x] += v1, tag1[x] += v1, tag3[x] += v3;
    sum[x] += 1ll * cnt[x] * v1 + 1ll * (r - l + 1 - cnt[x]) * v3;
    if (se[x] != -1e18) se[x] += v3;
  }

  void pushdown(int x, int l, int r) {
    if (tag1[x] || tag2[x] || tag3[x] || tag4[x]) {
      int mx = std::max(maxa[x << 1], maxa[x << 1 | 1]);
      int mid = (l + r) >> 1;
      if (maxa[x << 1] == mx) {
        addtag(x << 1, l, mid, tag1[x], tag2[x], tag3[x], tag4[x]);
      } else {
        addtag(x << 1, l, mid, tag3[x], tag4[x], tag3[x], tag4[x]);
      }
      if (maxa[x << 1 | 1] == mx) {
        addtag(x << 1 | 1, mid + 1, r, tag1[x], tag2[x], tag3[x], tag4[x]);
      } else {
        addtag(x << 1 | 1, mid + 1, r, tag3[x], tag4[x], tag3[x], tag4[x]);
      }
      tag1[x] = tag2[x] = tag3[x] = tag4[x] = 0;
    }
  }

  void build(int x, int l, int r) {
    se[x] = -2e9;
    if (l == r) {
      sum[x] = maxa[x] = maxb[x] = a[l], cnt[x] = 1;
      return;
    }
    int mid = (l + r) >> 1;
    build(x << 1, l, mid), build(x << 1 | 1, mid + 1, r);
    pushup(x);
  }

  void update1(int x, int l, int r, int ql, int qr, int v) { // 区间 +
    if (l > qr || r < ql) return;
    else if (l >= ql && r <= qr) return addtag(x, l, r, v, std::max<int>(v, 0), v, std::max<int>(v, 0));
    pushdown(x, l, r);
    int mid = (l + r) >> 1;
    update1(x << 1, l, mid, ql, qr, v), update1(x << 1 | 1, mid + 1, r, ql, qr, v);
    pushup(x);
  }

  void update2(int x, int l, int r, int ql, int qr, int v) { // 区间 chkmin
    if (l > qr || r < ql || maxa[x] <= v) return;
    else if (l >= ql && r <= qr && se[x] < v)
      return addtag(x, l, r, v - maxa[x], 0, 0, 0);
    pushdown(x, l, r);
    int mid = (l + r) >> 1;
    update2(x << 1, l, mid, ql, qr, v), update2(x << 1 | 1, mid + 1, r, ql, qr, v);
    pushup(x);
  }

  int64_t querysum(int x, int l, int r, int ql, int qr) {
    if (l > qr || r < ql) return 0;
    else if (l >= ql && r <= qr) return sum[x];
    pushdown(x, l, r);
    int mid = (l + r) >> 1;
    return querysum(x << 1, l, mid, ql, qr) + querysum(x << 1 | 1, mid + 1, r, ql, qr);
  }

  int querymaxa(int x, int l, int r, int ql, int qr) {
    if (l > qr || r < ql) return -2e9;
    else if (l >= ql && r <= qr) return maxa[x];
    pushdown(x, l, r);
    int mid = (l + r) >> 1;
    return std::max(querymaxa(x << 1, l, mid, ql, qr), querymaxa(x << 1 | 1, mid + 1, r, ql, qr));
  }

  int querymaxb(int x, int l, int r, int ql, int qr) {
    if (l > qr || r < ql) return -2e9;
    else if (l >= ql && r <= qr) return maxb[x];
    pushdown(x, l, r);
    int mid = (l + r) >> 1;
    return std::max(querymaxb(x << 1, l, mid, ql, qr), querymaxb(x << 1 | 1, mid + 1, r, ql, qr));
  }
} sgt;

void dickdreamer() {
  std::cin >> n >> m;
  for (int i = 1; i <= n; ++i) std::cin >> a[i];
  sgt.build(1, 1, n);
  for (int i = 1; i <= m; ++i) {
    int op, l, r, v;
    std::cin >> op >> l >> r;
    if (op == 1) {
      std::cin >> v;
      sgt.update1(1, 1, n, l, r, v);
    } else if (op == 2) {
      std::cin >> v;
      sgt.update2(1, 1, n, l, r, v);
    } else if (op == 3) {
      std::cout << sgt.querysum(1, 1, n, l, r) << '\n';
    } else if (op == 4) {
      std::cout << sgt.querymaxa(1, 1, n, l, r) << '\n';
    } else {
      std::cout << sgt.querymaxb(1, 1, n, l, r) << '\n';
    }
  }
}

int32_t main() {
#ifdef ORZXKR
  freopen("in.txt", "r", stdin);
  freopen("out.txt", "w", stdout);
#endif
  std::ios::sync_with_stdio(0), std::cin.tie(0), std::cout.tie(0);
  int T = 1;
  // std::cin >> T;
  while (T--) dickdreamer();
  // std::cerr << 1.0 * clock() / CLOCKS_PER_SEC << "s\n";
  return 0;
}

区间+/赋值/求最值/求历史最值

Description

维护一个线段树，使得可以实现区间加、区间赋值、求区间最值、区间历史最值。

Solution

如果没有区间覆盖就像刚才一样维护两个 tag。但是如果加上区间覆盖后由于 tag 维护的是初始到终止的整体位移量，而只要一个节点被区间赋值后所有数就变得相等，那么这个位移量就没用了。

所以考虑对于每个节点，维护做区间赋值之前的两个 tag，然后维护做区间赋值后的当前赋的值和赋的值的最大值。

时间复杂度：O(nlog⁡n)O(n\log n)。

Code

Code
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
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
#include <bits/stdc++.h>

#define int int64_t

const int kMaxN = 1e5 + 5;

int n, m;
int a[kMaxN];

struct SGT {
  int maxa[kMaxN * 4], maxb[kMaxN * 4];
  int tag1[kMaxN * 4], tag2[kMaxN * 4], tagcov1[kMaxN * 4], tagcov2[kMaxN * 4];

  void pushup(int x) {
    maxa[x] = std::max(maxa[x << 1], maxa[x << 1 | 1]);
    maxb[x] = std::max(maxb[x << 1], maxb[x << 1 | 1]);
  }

  void addtag1(int x, int v1, int v2) {
    maxb[x] = std::max(maxb[x], maxa[x] + v2);
    maxa[x] += v1;
    if (tagcov1[x] == -1e18) {
      tag2[x] = std::max(tag2[x], tag1[x] + v2), tag1[x] += v1;
    } else {
      tagcov2[x] = std::max(tagcov2[x], tagcov1[x] + v2), tagcov1[x] += v1;
    }
  }

  void addtag2(int x, int v1, int v2) {
    maxb[x] = std::max(maxb[x], v2);
    maxa[x] = v1;
    tagcov2[x] = std::max(tagcov2[x], v2);
    tagcov1[x] = v1;
  }

  void pushdown(int x) {
    if (tag1[x] || tag2[x]) {
      addtag1(x << 1, tag1[x], tag2[x]);
      addtag1(x << 1 | 1, tag1[x], tag2[x]);
      tag1[x] = tag2[x] = 0;
    }
    if (tagcov1[x] != -1e18 || tagcov2[x] != -1e18) {
      addtag2(x << 1, tagcov1[x], tagcov2[x]);
      addtag2(x << 1 | 1, tagcov1[x], tagcov2[x]);
      tagcov1[x] = tagcov2[x] = -1e18;
    }
  }

  void build(int x, int l, int r) {
    tagcov1[x] = tagcov2[x] = -1e18;
    if (l == r) {
      maxa[x] = maxb[x] = a[l];
      return;
    }
    int mid = (l + r) >> 1;
    build(x << 1, l, mid), build(x << 1 | 1, mid + 1, r);
    pushup(x);
  }

  void update1(int x, int l, int r, int ql, int qr, int v) {
    if (l > qr || r < ql) return;
    else if (l >= ql && r <= qr) return addtag1(x, v, std::max<int>(0, v));
    pushdown(x);
    int mid = (l + r) >> 1;
    update1(x << 1, l, mid, ql, qr, v), update1(x << 1 | 1, mid + 1, r, ql, qr, v);
    pushup(x);
  }

  void update2(int x, int l, int r, int ql, int qr, int v) {
    if (l > qr || r < ql) return;
    else if (l >= ql && r <= qr) return addtag2(x, v, v);
    pushdown(x);
    int mid = (l + r) >> 1;
    update2(x << 1, l, mid, ql, qr, v), update2(x << 1 | 1, mid + 1, r, ql, qr, v);
    pushup(x);
  }

  int querymaxa(int x, int l, int r, int ql, int qr) {
    if (l > qr || r < ql) return -1e18;
    else if (l >= ql && r <= qr) return maxa[x];
    pushdown(x);
    int mid = (l + r) >> 1;
    return std::max(querymaxa(x << 1, l, mid, ql, qr), querymaxa(x << 1 | 1, mid + 1, r, ql, qr));
  }

  int querymaxb(int x, int l, int r, int ql, int qr) {
    if (l > qr || r < ql) return -1e18;
    else if (l >= ql && r <= qr) return maxb[x];
    pushdown(x);
    int mid = (l + r) >> 1;
    return std::max(querymaxb(x << 1, l, mid, ql, qr), querymaxb(x << 1 | 1, mid + 1, r, ql, qr));
  }
} sgt;

void dickdreamer() {
  std::cin >> n;
  for (int i = 1; i <= n; ++i) std::cin >> a[i];
  sgt.build(1, 1, n);
  std::cin >> m;
  for (int i = 1; i <= m; ++i) {
    std::string op;
    int l, r, v;
    std::cin >> op >> l >> r;
    if (op[0] == 'Q') {
      std::cout << sgt.querymaxa(1, 1, n, l, r) << '\n';
    } else if (op[0] == 'A') {
      std::cout << sgt.querymaxb(1, 1, n, l, r) << '\n';
    } else if (op[0] == 'P') {
      std::cin >> v;
      sgt.update1(1, 1, n, l, r, v);
    } else {
      std::cin >> v;
      sgt.update2(1, 1, n, l, r, v);
    }
  }
}

int32_t main() {
#ifdef ORZXKR
  freopen("in.txt", "r", stdin);
  freopen("out.txt", "w", stdout);
#endif
  std::ios::sync_with_stdio(0), std::cin.tie(0), std::cout.tie(0);
  int T = 1;
  // std::cin >> T;
  while (T--) dickdreamer();
  // std::cerr << 1.0 * clock() / CLOCKS_PER_SEC << "s\n";
  return 0;
}
区间历史最值线段树记录
https://sobaliuziao.github.io/2024/08/12/post/23d53246.html
作者
Egg_laying_master
发布于
2024年8月12日
许可协议