Skip to content

Range Chmin/Chmax & Historical Extrema

This article explains how a segment tree handles historical range maximum/minimum problems, as described by Ruyi Ji in the 2016 Chinese national training team papers.

Range chmin/chmax

Broadly speaking, a range chmin/chmax operation replaces every number in the range \([l,r]\) by its \(\max\) or \(\min\) with \(x\), that is, \(a_i=\max(a_i,x)\) or \(a_i=\min(a_i,x)\).

HDU5306 Gorgeous Sequence

Maintain a sequence \(a\) under the following operations:

  1. 0 l r t: \(\forall l\le i\le r,~ a_i=\min(a_i,t)\).
  2. 1 l r: output \(\max\limits_{i=l}^r a_i\).
  3. 2 l r: output \(\sum\limits_{i=l}^r a_i\).

There are multiple test cases. It is guaranteed that \(T\le 100,~\sum n,\sum m\le 10^6\).

A range \(\min\) changes only the numbers greater than \(t\). So the operation no longer acts on the whole range, but on "the numbers in this range that are greater than \(t\)". This suggests the following approach: each node stores the maximum \(Max\) of its range, the second maximum \(Se\), the range sum \(Sum\), and the number \(Cnt\) of occurrences of the maximum. Now consider taking the \(\min\) of a range with \(t\).

  1. If \(Max\le t\), this \(t\) has no effect, and we return immediately.
  2. If \(Se<t < Max\), then \(t\) updates the maximum of the current range. We add \(Cnt(t-Max)\) to the range sum, set \(Max\) to \(t\), and apply a tag.
  3. If \(t\le Se\), we cannot tell how many numbers the update affects. So we simply recurse into the children by brute force, and then pull up.

How fast is this algorithm? The potential method shows that it runs in \(O(m\log n)\). See the paper for the analysis.

  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
#include <algorithm>
#include <cctype>
#include <iostream>
using namespace std;
constexpr int N = 1e6 + 6;

int t, n, m;
int a[N];
int mx[N << 2], se[N << 2], cn[N << 2], tag[N << 2];
long long sum[N << 2];

void pushup(int u) {  // pull up the information
  const int ls = u << 1, rs = u << 1 | 1;
  sum[u] = sum[ls] + sum[rs];
  if (mx[ls] == mx[rs]) {
    mx[u] = mx[rs];
    se[u] = max(se[ls], se[rs]);
    cn[u] = cn[ls] + cn[rs];
  } else if (mx[ls] > mx[rs]) {
    mx[u] = mx[ls];
    se[u] = max(se[ls], mx[rs]);
    cn[u] = cn[ls];
  } else {
    mx[u] = mx[rs];
    se[u] = max(mx[ls], se[rs]);
    cn[u] = cn[rs];
  }
}

void pushtag(int u, int tg) {  // just apply the tag, no brute-force search
  if (mx[u] <= tg) return;
  sum[u] += (1ll * tg - mx[u]) * cn[u];
  mx[u] = tag[u] = tg;
}

void pushdown(int u) {  // push down the tag
  if (tag[u] == -1) return;
  pushtag(u << 1, tag[u]), pushtag(u << 1 | 1, tag[u]);
  tag[u] = -1;
}

void build(int u = 1, int l = 1, int r = n) {  // build the tree
  tag[u] = -1;
  if (l == r) {
    sum[u] = mx[u] = a[l], se[u] = -1, cn[u] = 1;
    return;
  }
  int mid = (l + r) >> 1;
  build(u << 1, l, mid), build(u << 1 | 1, mid + 1, r);
  pushup(u);
}

void modify_min(int L, int R, int v, int u = 1, int l = 1, int r = n) {
  if (mx[u] <= v) return;
  if (L <= l && r <= R && se[u] < v) return pushtag(u, v);
  int mid = (l + r) >> 1;
  pushdown(u);
  if (L <= mid) modify_min(L, R, v, u << 1, l, mid);
  if (mid < R) modify_min(L, R, v, u << 1 | 1, mid + 1, r);
  pushup(u);
}

int query_max(int L, int R, int u = 1, int l = 1, int r = n) {  // query the maximum
  if (L <= l && r <= R) return mx[u];
  int mid = (l + r) >> 1, r1 = -1, r2 = -1;
  pushdown(u);
  if (L <= mid) r1 = query_max(L, R, u << 1, l, mid);
  if (mid < R) r2 = query_max(L, R, u << 1 | 1, mid + 1, r);
  return max(r1, r2);
}

long long query_sum(int L, int R, int u = 1, int l = 1, int r = n) {  // sum of the values
  if (L <= l && r <= R) return sum[u];
  int mid = (l + r) >> 1;
  long long res = 0;
  pushdown(u);
  if (L <= mid) res += query_sum(L, R, u << 1, l, mid);
  if (mid < R) res += query_sum(L, R, u << 1 | 1, mid + 1, r);
  return res;
}

void go() {  // as the problem statement requires
  cin >> n >> m;
  for (int i = 1; i <= n; i++) cin >> a[i];
  build();
  for (int i = 1; i <= m; i++) {
    int op, x, y, z;
    cin >> op >> x >> y;
    if (op == 0)
      cin >> z, modify_min(x, y, z);
    else if (op == 1)
      cout << query_max(x, y) << '\n';
    else
      cout << query_sum(x, y) << '\n';
  }
}

signed main() {
  cin.tie(nullptr)->sync_with_stdio(false);
  cin >> t;
  while (t--) go();
  return 0;
}
BZOJ4695 The Fakest Female Contestant

Maintain a sequence \(a\) under the following operations:

  1. 1 l r x: \(\forall l\le i\le r,~ a_i=a_i+x\).
  2. 2 l r x: \(\forall l\le i\le r,~ a_i=\max(a_i,x)\).
  3. 3 l r x: \(\forall l\le i\le r,~ a_i=\min(a_i,x)\).
  4. 4 l r: output \(\sum\limits_{i=l}^r a_i\).
  5. 5 l r: output \(\max\limits_{i=l}^r a_i\).
  6. 6 l r: output \(\min\limits_{i=l}^r a_i\).

\(n,m\le 5\times 10^5,~|a_i|\le 10^8\). Every operation of type \(1\) has \(|x|\le 10^3\), and all other operations have \(|x|\le10^8\).

In the same way, we maintain the maximum, the second maximum, the count of the maximum, the minimum, the second minimum, the count of the minimum, and the range sum. On top of this information we need tags for range \(\max\), range \(\min\) and range addition. Unlike the previous problem, this raises the question of the order in which tags are pushed down. We use the following strategy:

  1. The range addition tag has the highest priority; the other two kinds of tags are on an equal footing.
  2. When a tag \(v\) is added to a node, we update the satellite data and the node's range addition tag with \(v\), and we also update its range \(\max\) and range \(\min\) tags with this \(v\).
  3. When a node takes the \(\min\) with \(v\) (we ignore the brute-force search here and assume the tag can be applied), we update the satellite data and also compare \(v\) with the range \(\max\) tag. If \(v\) is smaller than the range \(\max\) tag, every number ends up equal to \(v\), so we set the range \(\max\) tag to \(v\) as well. Otherwise we leave it alone.
  4. Taking the \(\max\) of a range with \(v\) works the same way.

When maintaining this information, the sets of numbers may coincide if there are only one or two numbers: a number can be both the maximum and the second minimum, for example. Such cases need special-casing.

  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
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
#include <iostream>
using namespace std;

constexpr int N = 5e5 + 5, SZ = N << 2, INF = 0x7fffffff;

int n, m;
int a[N];

struct data {
  int mx, mx2, mn, mn2, cmx, cmn, tmx, tmn, tad;
  long long sum;
} t[SZ];

void pushup(int u) {
  const int lu = u << 1, ru = u << 1 | 1;
  t[u].sum = t[lu].sum + t[ru].sum;
  if (t[lu].mx == t[ru].mx) {
    t[u].mx = t[lu].mx, t[u].cmx = t[lu].cmx + t[ru].cmx;
    t[u].mx2 = max(t[lu].mx2, t[ru].mx2);
  } else if (t[lu].mx > t[ru].mx) {
    t[u].mx = t[lu].mx, t[u].cmx = t[lu].cmx;
    t[u].mx2 = max(t[lu].mx2, t[ru].mx);
  } else {
    t[u].mx = t[ru].mx, t[u].cmx = t[ru].cmx;
    t[u].mx2 = max(t[lu].mx, t[ru].mx2);
  }
  if (t[lu].mn == t[ru].mn) {
    t[u].mn = t[lu].mn, t[u].cmn = t[lu].cmn + t[ru].cmn;
    t[u].mn2 = min(t[lu].mn2, t[ru].mn2);
  } else if (t[lu].mn < t[ru].mn) {
    t[u].mn = t[lu].mn, t[u].cmn = t[lu].cmn;
    t[u].mn2 = min(t[lu].mn2, t[ru].mn);
  } else {
    t[u].mn = t[ru].mn, t[u].cmn = t[ru].cmn;
    t[u].mn2 = min(t[lu].mn, t[ru].mn2);
  }
}

void push_add(int u, int l, int r, int v) {
  // while updating the addition tag, also update the $\min$ and $\max$ tags
  t[u].sum += (r - l + 1ll) * v;
  t[u].mx += v, t[u].mn += v;
  if (t[u].mx2 != -INF) t[u].mx2 += v;
  if (t[u].mn2 != INF) t[u].mn2 += v;
  if (t[u].tmx != -INF) t[u].tmx += v;
  if (t[u].tmn != INF) t[u].tmn += v;
  t[u].tad += v;
}

void push_min(int u, int tg) {
  // remember to compare with the $\max$ tag
  if (t[u].mx <= tg) return;
  t[u].sum += (tg * 1ll - t[u].mx) * t[u].cmx;
  if (t[u].mn2 == t[u].mx) t[u].mn2 = tg;  // !!!
  if (t[u].mn == t[u].mx) t[u].mn = tg;    // !!!!!
  if (t[u].tmx > tg) t[u].tmx = tg;        // update the $\max$ tag
  t[u].mx = tg, t[u].tmn = tg;
}

void push_max(int u, int tg) {
  if (t[u].mn > tg) return;
  t[u].sum += (tg * 1ll - t[u].mn) * t[u].cmn;
  if (t[u].mx2 == t[u].mn) t[u].mx2 = tg;
  if (t[u].mx == t[u].mn) t[u].mx = tg;
  if (t[u].tmn < tg) t[u].tmn = tg;
  t[u].mn = tg, t[u].tmx = tg;
}

void pushdown(int u, int l, int r) {
  const int lu = u << 1, ru = u << 1 | 1, mid = (l + r) >> 1;
  if (t[u].tad)
    push_add(lu, l, mid, t[u].tad), push_add(ru, mid + 1, r, t[u].tad);
  if (t[u].tmx != -INF) push_max(lu, t[u].tmx), push_max(ru, t[u].tmx);
  if (t[u].tmn != INF) push_min(lu, t[u].tmn), push_min(ru, t[u].tmn);
  t[u].tad = 0, t[u].tmx = -INF, t[u].tmn = INF;
}

void build(int u = 1, int l = 1, int r = n) {
  t[u].tmn = INF, t[u].tmx = -INF;  // set to the extreme values
  if (l == r) {
    t[u].sum = t[u].mx = t[u].mn = a[l];
    t[u].mx2 = -INF, t[u].mn2 = INF;
    t[u].cmx = t[u].cmn = 1;
    return;
  }
  int mid = (l + r) >> 1;
  build(u << 1, l, mid), build(u << 1 | 1, mid + 1, r);
  pushup(u);
}

void add(int L, int R, int v, int u = 1, int l = 1, int r = n) {
  if (R < l || r < L) return;
  if (L <= l && r <= R) return push_add(u, l, r, v);  // !!! forgot the return
  int mid = (l + r) >> 1;
  pushdown(u, l, r);
  add(L, R, v, u << 1, l, mid), add(L, R, v, u << 1 | 1, mid + 1, r);
  pushup(u);
}

void tomin(int L, int R, int v, int u = 1, int l = 1, int r = n) {
  if (R < l || r < L || t[u].mx <= v) return;
  if (L <= l && r <= R && t[u].mx2 < v) return push_min(u, v);  // BUG: forgot to return
  int mid = (l + r) >> 1;
  pushdown(u, l, r);
  tomin(L, R, v, u << 1, l, mid), tomin(L, R, v, u << 1 | 1, mid + 1, r);
  pushup(u);
}

void tomax(int L, int R, int v, int u = 1, int l = 1, int r = n) {
  if (R < l || r < L || t[u].mn >= v) return;
  if (L <= l && r <= R && t[u].mn2 > v) return push_max(u, v);
  int mid = (l + r) >> 1;
  pushdown(u, l, r);
  tomax(L, R, v, u << 1, l, mid), tomax(L, R, v, u << 1 | 1, mid + 1, r);
  pushup(u);
}

long long qsum(int L, int R, int u = 1, int l = 1, int r = n) {
  if (R < l || r < L) return 0;
  if (L <= l && r <= R) return t[u].sum;
  int mid = (l + r) >> 1;
  pushdown(u, l, r);
  return qsum(L, R, u << 1, l, mid) + qsum(L, R, u << 1 | 1, mid + 1, r);
}

long long qmax(int L, int R, int u = 1, int l = 1, int r = n) {
  if (R < l || r < L) return -INF;
  if (L <= l && r <= R) return t[u].mx;
  int mid = (l + r) >> 1;
  pushdown(u, l, r);
  return max(qmax(L, R, u << 1, l, mid), qmax(L, R, u << 1 | 1, mid + 1, r));
}

long long qmin(int L, int R, int u = 1, int l = 1, int r = n) {
  if (R < l || r < L) return INF;
  if (L <= l && r <= R) return t[u].mn;
  int mid = (l + r) >> 1;
  pushdown(u, l, r);
  return min(qmin(L, R, u << 1, l, mid), qmin(L, R, u << 1 | 1, mid + 1, r));
}

int main() {
  cin.tie(nullptr)->sync_with_stdio(false);
  cin >> n;
  for (int i = 1; i <= n; i++) cin >> a[i];
  build();
  cin >> m;
  for (int i = 1; i <= m; i++) {
    int op, l, r, x;
    cin >> op >> l >> r;
    if (op <= 3) cin >> x;
    if (op == 1)
      add(l, r, x);
    else if (op == 2)
      tomax(l, r, x);
    else if (op == 3)
      tomin(l, r, x);
    else if (op == 4)
      cout << qsum(l, r) << '\n';
    else if (op == 5)
      cout << qmax(l, r) << '\n';
    else
      cout << qmin(l, r) << '\n';
  }
  return 0;
}

Ruyi Ji proved that this algorithm runs in \(O(m\log^2 n)\).

Mzl loves segment tree

There are two sequences \(A\) and \(B\); initially every number in \(B\) is \(0\). The operations to support are:

  1. Range \(\min\) on \(A\)
  2. Range \(\max\) on \(A\)
  3. Range addition on \(A\)
  4. Query a range sum of \(B\)

After each operation, if the value of \(A_i\) has changed, add \(1\) to \(B_i\). \(n,m\le 3\times 10^5\).

Start with the easiest operation, range addition. As long as \(x\neq 0\), every number in the range changes, so one range addition on B is enough.

For the range chmin/chmax operations, notice that applying tags and pushing them down correspond one-to-one to updates of the array \(B\). In essence you have split the numbers of the sequence into three classes, the maximum, the minimum and everything else, and you maintain each class separately (you never actually build the sets of extreme values, but that does not get in the way). So whenever you apply a tag, update the information of \(B\) along the way (note: this updates its information, it does not put a tag on \(B\)!). To answer a query, descend in \(A\) and update the information of \(B\) as you push tags down. Once you reach the nodes you need, return the information of \(B\). In effect, the information about the extreme values is handed to \(B\) to maintain. You still have to deal with overlapping sets of numbers.

CTSN loves segment tree

Maintain two sequences \(a\) and \(b\) under the following operations:

  1. 1 l r x: \(\forall l\le i\le r,~ a_i=\min(a_i,x)\).
  2. 2 l r x: \(\forall l\le i\le r,~ b_i=\min(b_i,x)\).
  3. 3 l r x: \(\forall l\le i\le r,~ a_i=a_i+x\).
  4. 4 l r x: \(\forall l\le i\le r,~ b_i=b_i+x\).
  5. 5 l r: output \(\max\limits_{i=l}^r (a_i+b_i)\).

\(n,m\le 3\times 10^5,~|a_i|,|b_i|,|x|\le 10^9\).

We split the candidate answers \(A_i+B_i\) in a range \([l,r]\) into four classes: neither \(A_i\) nor \(B_i\) is the range maximum of its sequence \(A\) or \(B\); \(A_i\) is the range maximum of \(A\) but \(B_i\) is not the range maximum of \(B\); \(A_i\) is not the range maximum of \(A\) but \(B_i\) is the range maximum of \(B\); and both \(A_i\) and \(B_i\) are the range maxima of \(A\) and \(B\). Denote them by \(C_{0,0},C_{1,0},C_{0,1},C_{1,1}\) respectively. We also maintain the range maximum and second maximum of \(A\) and \(B\) as usual. When range addition tags and \(\min\) tags are pushed down, the maxima and second maxima of \(A\) and \(B\) are handled as in the two examples above. A \(\min\) tag on \(A\) affects \(C_{1,1}\) and \(C_{1,0}\), and a tag on \(B\) affects \(C_{1,1}\) and \(C_{0,1}\). An addition on \(A\) or \(B\) affects all of \(C_{0,0},C_{1,0},C_{0,1},C_{1,1}\). Just watch for the boundary cases where \(C_{0,0},C_{1,0},C_{0,1}\) do not exist (for example, for a range \([i,i]\) only the maxima of \(A\) and \(B\) and \(C_{1,1}\) exist).

Next, how do we maintain \(C_{0,0},C_{1,0},C_{0,1},C_{1,1}\) in pushup? Once the maxima of \(A\) and \(B\) have been updated, we distinguish cases by whether the maxima of \(A\) and \(B\) at the left and right children equal those at the current node. We describe the left child; the right child is handled in the same way:

  • If the left child's maxima of \(A\) and \(B\) both equal those of the current node, the left child's \(C_{0,0},C_{1,0},C_{0,1},C_{1,1}\) contribute to the current node's \(C_{0,0},C_{1,0},C_{0,1},C_{1,1}\) respectively.
  • If the left child's maximum of \(A\) equals the current node's maximum of \(A\) but the maxima of \(B\) differ, the left child's \(C_{1,0},C_{1,1}\) contribute to this node's \(C_{1,0}\), and its \(C_{0,0},C_{0,1}\) contribute to this node's \(C_{0,0}\).
  • If the left child's maximum of \(A\) differs from the current node's maximum of \(A\) but the maxima of \(B\) are equal, the left child's \(C_{0,1},C_{1,1}\) contribute to this node's \(C_{0,1}\), and its \(C_{0,0},C_{1,0}\) contribute to this node's \(C_{0,0}\).
  • If neither of the left child's maxima of \(A\) and \(B\) equals that of the current node, the left child's \(C_{0,0},C_{1,0},C_{0,1},C_{1,1}\) contribute only to this node's \(C_{0,0}\).

The answer is \(\max(C_{0,0},C_{1,0},C_{0,1},C_{1,1})\) taken over the result of the range query.

Since range \(\min\) and range addition are maintained together, the complexity is still \(O(m\log^2 n)\).

  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
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
#include <algorithm>
#include <cstdint>
#include <iostream>
using i64 = int64_t;

constexpr int N = 300010;
constexpr i64 INF = 1145141919810114514ll;
int n, q, op, l, r;
int a[N], b[N];

int lc(int u) { return (u << 1); }

int rc(int u) { return (u << 1) | 1; }

struct node {
  i64 mx_ab[2][2];  // 0: not max A or B; 1: is max A or B

  i64 max_val() {
    return std::max({mx_ab[0][0], mx_ab[0][1], mx_ab[1][0], mx_ab[1][1]});
  }

  i64 mx1[2], mx2[2];  // 0: A; 1: B
  i64 tag_add[2], tag_mn[2];

  void clr_tag() { tag_add[0] = tag_add[1] = 0, tag_mn[0] = tag_mn[1] = INF; }

  void init(i64 a, i64 b) {
    mx1[0] = a, mx1[1] = b, mx2[0] = mx2[1] = -INF;
    mx_ab[1][1] = a + b, mx_ab[0][1] = mx_ab[1][0] = mx_ab[0][0] = -INF;
  }

  void modify_mn(i64 tg, bool id)  // id 0: A; 1: B
  {
    if (mx1[id] <= tg) return;
    mx_ab[1][1] += (mx_ab[1][1] > -INF) ? (tg - mx1[id]) : 0;
    mx_ab[!id][id] += (mx_ab[!id][id] > -INF) ? (tg - mx1[id]) : 0;
    mx1[id] = tag_mn[id] = tg;
  }

  void modify_add(i64 tg, bool id)  // id 0: A; 1: B
  {
    for (int i = 0; i < 2; ++i)
      for (int j = 0; j < 2; ++j) mx_ab[i][j] += (mx_ab[i][j] > -INF) ? tg : 0;
    mx1[id] += tg, mx2[id] += (mx2[id] > -INF) ? tg : 0;
    tag_mn[id] += (tag_mn[id] < INF) ? tg : 0, tag_add[id] += tg;
  }

  void pushup(const node& l, const node& r) {
    for (int i = 0; i < 2; ++i) {
      if (l.mx1[i] == r.mx1[i])
        mx1[i] = l.mx1[i], mx2[i] = std::max(l.mx2[i], r.mx2[i]);
      else if (l.mx1[i] > r.mx1[i])
        mx1[i] = l.mx1[i], mx2[i] = std::max(l.mx2[i], r.mx1[i]);
      else
        mx1[i] = r.mx1[i], mx2[i] = std::max(l.mx1[i], r.mx2[i]);
    }
    if (l.mx1[0] == mx1[0] && l.mx1[1] == mx1[1]) {
      mx_ab[1][1] = l.mx_ab[1][1], mx_ab[0][1] = l.mx_ab[0][1];
      mx_ab[1][0] = l.mx_ab[1][0], mx_ab[0][0] = l.mx_ab[0][0];
    } else if (l.mx1[0] == mx1[0] && l.mx1[1] != mx1[1]) {
      mx_ab[1][1] = mx_ab[0][1] = -INF;
      mx_ab[1][0] = std::max(l.mx_ab[1][1], l.mx_ab[1][0]);
      mx_ab[0][0] = std::max(l.mx_ab[0][1], l.mx_ab[0][0]);
    } else if (l.mx1[0] != mx1[0] && l.mx1[1] == mx1[1]) {
      mx_ab[1][1] = mx_ab[1][0] = -INF;
      mx_ab[0][1] = std::max(l.mx_ab[1][1], l.mx_ab[0][1]);
      mx_ab[0][0] = std::max(l.mx_ab[1][0], l.mx_ab[0][0]);
    } else {
      mx_ab[1][1] = mx_ab[0][1] = mx_ab[1][0] = -INF;
      mx_ab[0][0] = std::max(
          {l.mx_ab[0][0], l.mx_ab[0][1], l.mx_ab[1][0], l.mx_ab[1][1]});
    }

    if (r.mx1[0] == mx1[0] && r.mx1[1] == mx1[1]) {
      mx_ab[1][1] = std::max(mx_ab[1][1], r.mx_ab[1][1]);
      mx_ab[0][1] = std::max(mx_ab[0][1], r.mx_ab[0][1]);
      mx_ab[1][0] = std::max(mx_ab[1][0], r.mx_ab[1][0]);
      mx_ab[0][0] = std::max(mx_ab[0][0], r.mx_ab[0][0]);
    } else if (r.mx1[0] == mx1[0] && r.mx1[1] != mx1[1]) {
      mx_ab[1][0] = std::max({mx_ab[1][0], r.mx_ab[1][1], r.mx_ab[1][0]});
      mx_ab[0][0] = std::max({mx_ab[0][0], r.mx_ab[0][1], r.mx_ab[0][0]});
    } else if (r.mx1[0] != mx1[0] && r.mx1[1] == mx1[1]) {
      mx_ab[0][1] = std::max({mx_ab[0][1], r.mx_ab[1][1], r.mx_ab[0][1]});
      mx_ab[0][0] = std::max({mx_ab[0][0], r.mx_ab[1][0], r.mx_ab[0][0]});
    } else
      mx_ab[0][0] = std::max({mx_ab[0][0], r.mx_ab[0][0], r.mx_ab[0][1],
                              r.mx_ab[1][0], r.mx_ab[1][1]});
  }
} tr[N << 2];

void pushup(int u) { tr[u].pushup(tr[lc(u)], tr[rc(u)]); }

void pushdown(int u) {
  for (int i = 0; i < 2; ++i)
    if (tr[u].tag_add[i])
      tr[lc(u)].modify_add(tr[u].tag_add[i], i),
          tr[rc(u)].modify_add(tr[u].tag_add[i], i);
  for (int i = 0; i < 2; ++i)
    if (tr[u].tag_mn[i] < INF)
      tr[lc(u)].modify_mn(tr[u].tag_mn[i], i),
          tr[rc(u)].modify_mn(tr[u].tag_mn[i], i);
  tr[u].clr_tag();
}

void _build(int u, int L, int R) {
  tr[u].clr_tag();
  if (L == R) return tr[u].init(a[L], b[L]);
  int M = (L + R) >> 1;
  _build(lc(u), L, M), _build(rc(u), M + 1, R), pushup(u);
}

void build() { _build(1, 1, n); }

void _modify_mn(int u, int l, int r, int L, int R, int v, bool i) {
  if (L > r || R < l || tr[u].mx1[i] <= v) return;
  if (l <= L && R <= r && tr[u].mx2[i] < v) return tr[u].modify_mn(v, i);
  pushdown(u);
  int M = (L + R) >> 1;
  _modify_mn(lc(u), l, r, L, M, v, i), _modify_mn(rc(u), l, r, M + 1, R, v, i);
  pushup(u);
}

void modify_mn(int l, int r, int v, bool i) { _modify_mn(1, l, r, 1, n, v, i); }

void _modify_add(int u, int l, int r, int L, int R, int v, bool i) {
  if (L > r || R < l) return;
  if (l <= L && R <= r) return tr[u].modify_add(v, i);
  pushdown(u);
  int M = (L + R) >> 1;
  _modify_add(lc(u), l, r, L, M, v, i),
      _modify_add(rc(u), l, r, M + 1, R, v, i);
  pushup(u);
}

void modify_add(int l, int r, int v, bool i) {
  _modify_add(1, l, r, 1, n, v, i);
}

node _query(int u, int l, int r, int L, int R) {
  if (l <= L && R <= r) return tr[u];
  pushdown(u);
  int M = (L + R) >> 1;
  if (r <= M) return _query(lc(u), l, r, L, M);
  if (l > M) return _query(rc(u), l, r, M + 1, R);
  node ret;
  node _l = _query(lc(u), l, M, L, M), _r = _query(rc(u), M + 1, r, M + 1, R);
  ret.pushup(_l, _r);
  return ret;
}

node query(int l, int r) { return _query(1, l, r, 1, n); }

using std::cin;
using std::cout;

int main() {
  cin.tie(nullptr)->sync_with_stdio(false);
  cin >> n >> q;
  for (int i = 1; i <= n; ++i) cin >> a[i];
  for (int i = 1; i <= n; ++i) cin >> b[i];
  build();
  while (q--) {
    cin >> op >> l >> r;
    int x;
    switch (op) {
      case 1:
        cin >> x;
        modify_mn(l, r, x, 0);
        break;
      case 2:
        cin >> x;
        modify_mn(l, r, x, 1);
        break;
      case 3:
        cin >> x;
        modify_add(l, r, x, 0);
        break;
      case 4:
        cin >> x;
        modify_add(l, r, x, 1);
        break;
      case 5:
        cout << query(l, r).max_val() << '\n';
        break;
      default:
        break;
    }
  }
}

Summary

This section gave four examples. They showed, in turn, how to maintain the basic range chmin/chmax operations, how to prioritize several tags, the idea of splitting the numbers into classes, and how to maintain several classifications at once. At its core, handling range chmin/chmax means maintaining information about the numbers class by class and merging it efficiently. The next section looks at historical range maximum/minimum problems.

Historical maximum/minimum problems

Historical maximum/minimum is not persistence

Note that the historical maximum/minimum problems of this section are not the same thing as so-called persistent data structures. We call this special class of problems historical maximum/minimum problems. They fall into three kinds.

Historical maximum

Put simply, the historical maximum of a position is the largest number that has ever appeared at that position. Formally, we define an auxiliary array \(B\) that is initially identical to \(A\). After every operation on \(A\), we take the \(\max\) over the whole array:

\[ \forall i\in[1,n],\ B_i=\max(B_i,A_i) \]

We then call \(B_i\) the historical maximum of this position.

Historical minimum

The definition is analogous to that of the historical maximum: after every operation on \(A\), we take the \(\min\) over the whole array. We then call \(B_i\) the historical minimum of this position.

Historical sum

The auxiliary array \(B\) is initially all \(0\). After every operation, we add the whole array \(A\) to the array \(B\):

\[ \forall i\in[1,n], \ B_i=B_i+A_i \]

We call \(B_i\) the historical sum at position \(i\).

Below we discuss historical maximum/minimum problems in four classes.

Problems that tags can handle

CPU Monitor

The sequences \(A\) and \(B\) are initially identical:

  1. Range assignment of \(x\) on \(A\)
  2. Range addition of \(x\) on \(A\)
  3. Query a range \(\max\) of \(A\)
  4. Query a range \(\max\) of \(B\)

After each operation we perform the update \(\forall i\in [1,n],\ B_i=\max(B_i,A_i)\). \(n,m\le 10^5\).

Ignore operation 1 for now. The only update is then range addition, and we maintain a tag \(Add\), the amount added to the current range; this tag takes care of the range \(\max\). Now consider the historical range \(\max\). We define a tag \(Pre\) with the following meaning: the historical maximum of the \(Add\) tag during the lifetime of this tag.

This definition may be rather vague, so let us first explain the lifetime of a tag. A tag goes through the following stages:

  1. It is created at node \(u\).
  2. Node \(u\) receives a number of new tags, and the tag is merged with them (with tags of the same kind, that is).
  3. The tag of node \(u\) is pushed down to the children of \(u\), and the tag of \(u\) is cleared.

The lifetime of the tag of node \(u\) runs from step 1 until just before step 3. When two tags are merged they become a single tag, so their lifetimes merge as well (the lifetime starts at the earlier of the two creation times). Equivalently, the lifetime is the period from the last time this node's tag was pushed down until now.

Why define a lifetime? With this notion we can prove that during the lifetime of a node's tag none of its children change in any way: they stay in the state they were in before the lifetime began. The reason is simple: you push no tag down during that period.

This guarantees that the historical maximum of \(Add\) during the current tag's lifetime can be applied to the tags and information of the children, because neither changed during that time. So when we push the tag of \(u\) down to its child \(s\), we get

\[ Pre_s=\max(Pre_s,Pre_u+Add_s),Add_s=Add_u+Add_s \]

The information is updated in the same way, using the corresponding tags.

Now consider operation 1.

A range assignment makes all the numbers equal. After that, whether the range is added to, subtracted from or assigned, all its numbers remain equal (unless you end the current tag's lifetime by pushing the tag down). So we can treat every tag after the first range assignment as a range assignment tag. In other words, the lifetime of a tag splits roughly into two phases:

  1. A merge of several addition/subtraction tags; no assignment tag has been received yet.
  2. An assignment tag; there are no addition/subtraction tags as such (they are converted into assignment tags).

So we split the node's Pre tag into \((P_1,P_2)\): \(P_1\) is the maximum addition/subtraction tag of the first phase, and \(P_2\) is the maximum assignment tag of the second phase. Tags are pushed down and information is updated in a similar way. This takes \(O(m\log n)\) time (mind you, this problem has no range chmin/chmax with \(x\)!).

  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
#include <algorithm>
#include <climits>
#include <iostream>
using namespace std;
using ll = long long;

constexpr int N = 1e5 + 7;

struct Tree {
  int mx, _mx;  // range maximum, historical range maximum
  int ad, _ad;  // range addition tag, historical maximum addition tag of the phase
  int st, _st;  // range assignment value, historical maximum assignment tag of the phase
} g[N * 4];

int a[N];
int n, m;
#define ls u * 2
#define rs u * 2 + 1
#define mid (l + r) / 2

void pushup(int u) {
  g[u].mx = max(g[ls].mx, g[rs].mx);
  g[u]._mx = max(g[ls]._mx, g[rs]._mx);
}

void pushadd(int u, int v, int _v) {
  g[u]._mx = max(g[u]._mx, g[u].mx + _v), g[u].mx += v;
  if (g[u].st == INT_MIN)
    g[u]._ad = max(g[u]._ad, g[u].ad + _v), g[u].ad += v;
  else
    g[u]._st = max(g[u]._st, g[u].st + _v), g[u].st += v;
}

void pushset(int u, int v, int _v) {
  g[u]._mx = max(g[u]._mx, _v), g[u].mx = v;
  g[u]._st = max(g[u]._st, _v), g[u].st = v;
}

void pushdown(int u, int l, int r) {
  if (g[u].ad || g[u]._ad)
    pushadd(ls, g[u].ad, g[u]._ad), pushadd(rs, g[u].ad, g[u]._ad),
        g[u].ad = g[u]._ad = 0;
  if (g[u].st != INT_MIN || g[u]._st != INT_MIN)
    pushset(ls, g[u].st, g[u]._st), pushset(rs, g[u].st, g[u]._st),
        g[u].st = g[u]._st = INT_MIN;
}

void build(int u = 1, int l = 1, int r = n) {
  g[u]._st = g[u].st = INT_MIN;
  if (l == r) {
    g[u].mx = a[l];
    g[u]._mx = a[l];
    return;
  }
  build(ls, l, mid), build(rs, mid + 1, r);
  pushup(u);
}

int L, R;

void add(int v, int u = 1, int l = 1, int r = n) {
  if (R < l || r < L) return;
  if (L <= l && r <= R) return pushadd(u, v, max(v, 0));
  pushdown(u, l, r);
  add(v, ls, l, mid), add(v, rs, mid + 1, r);
  pushup(u);
}

void tset(int v, int u = 1, int l = 1, int r = n) {
  if (R < l || r < L) return;
  if (L <= l && r <= R) return pushset(u, v, v);
  pushdown(u, l, r);
  tset(v, ls, l, mid), tset(v, rs, mid + 1, r);
  pushup(u);
}

int qmax(int u = 1, int l = 1, int r = n) {
  if (R < l || r < L) return INT_MIN;
  if (L <= l && r <= R) return g[u].mx;
  pushdown(u, l, r);
  return max(qmax(ls, l, mid), qmax(rs, mid + 1, r));
}

int qmaxh(int u = 1, int l = 1, int r = n) {
  if (R < l || r < L) return INT_MIN;
  if (L <= l && r <= R) return g[u]._mx;
  pushdown(u, l, r);
  return max(qmaxh(ls, l, mid), qmaxh(rs, mid + 1, r));
}

int main() {
  cin.tie(nullptr)->sync_with_stdio(false);
  cin >> n;
  for (int i = 1; i <= n; ++i) cin >> a[i];
  build();
  int m, z;
  cin >> m;
  for (int i = 1; i <= m; ++i) {
    char op;
    cin >> op;
    while (op == ' ' || op == '\r' || op == '\n') cin >> op;
    cin >> L >> R;
    int x;
    if (op == 'Q')
      cout << qmax() << '\n';
    else if (op == 'A')
      cout << qmaxh() << '\n';
    else if (op == 'P')
      cin >> x, add(x);
    else
      cin >> x, tset(x);
  }
  return 0;
}