Skip to content

Range Min/Max Operations & Range Historical Extremum

This article explains the problem of handling historical interval maximum/minimum values using segment trees, as mentioned by Ji (Jiyuan) in the 2016 National Training Team paper.

Interval Maximum/Minimum Operations

Broadly speaking, interval maximum/minimum operations refer to taking the \(\max\) or \(\min\) of all numbers in the interval \([l,r]\) with respect to \(x\), i.e., \(a_i=\max(a_i,x)\) or \(a_i=\min(a_i,x)\).

HDU5306 Gorgeous Sequence

Maintain a sequence \(a\) and perform 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\).

Multiple test cases, guaranteed \(T\le 100,~\sum n,\sum m\le 10^6\).

Taking the \(\min\) over an interval means only numbers greater than \(t\) are changed. Therefore, the target of this operation is no longer the entire interval, but "the numbers in this interval that are greater than \(t\)". Thus, we can adopt the following approach: each node maintains the maximum value \(Max\) of the interval, the second maximum value \(Se\), the interval sum \(Sum\), and the count \(Cnt\) of maximum values. Next, we consider the operation of taking the \(\min\) with \(t\) over the interval.

  1. If \(Max\le t\), clearly \(t\) is meaningless, return directly.
  2. If \(Se<t < Max\), then this \(t\) can update the current interval's maximum. So we add \(Cnt(t-Max)\) to the interval sum, update \(Max\) to \(t\), and set a lazy tag.
  3. If \(t\le Se\), then we don't know how many numbers are involved in the update. Our strategy is to recursively operate downward. Then push up the information.

What is the complexity of this algorithm? Using potential analysis, the complexity is \(O(m\log n)\). For detailed analysis, refer to the paper.

  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) {  // Update upwards
  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) {  // Simply apply tag, no exhaustive 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 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 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 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) {  // Query sum
  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() {  // Process according to problem statement
  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 Most Fake Female Contestant

Maintain a sequence \(a\) and perform 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\). All type 1 operations have \(|x|\le 10^3\), other operations satisfy \(|x|\le10^8\).

Using the same method, we maintain the maximum, second maximum, count of maximums, minimum, second minimum, count of minimums, and interval sum. Besides this information, we also need to maintain lazy tags for interval \(\max\), interval \(\min\), and interval addition. Compared to the previous problem, this involves the order of tag propagation. We adopt the following strategy:

  1. We consider the interval addition tag as the highest priority, and the other two tags as equal.
  2. When adding a \(v\) tag to a node, besides updating the satellite information and the current node's interval addition tag with \(v\), we also use \(v\) to update the interval \(\max\) and interval \(\min\) tags.
  3. When taking the \(\min\) with \(v\) for a node (ignoring the brute-force search process here, assuming the tag meets the addition condition), besides updating satellite information, we compare it with the interval \(\max\) tag. If \(v\) is less than the interval \(\max\) tag, then all numbers will eventually become \(v\), so we change the interval \(\max\) tag to \(v\). Otherwise, do nothing.
  4. Taking the \(\max\) with \(v\) over an interval is similar.

When maintaining information, number set overlap may occur when there is only one or two numbers, e.g., a number being both the maximum and the second minimum, which requires special handling.

  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
```cpp
#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) {
  // Update min and max tags while updating the addition tag
  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) {
  // Note: 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 take-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 limits
  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 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;
}

  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
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
Ji proved that the complexity of this algorithm is $O(m\log^2 n)$.

???+ note "Mzl loves segment tree"
    Two sequences $A,B$, initially all numbers in $B$ are $0$. The operations are:

    1.  Interval $\min$ on $A$.
    2.  Interval $\max$ on $A$.
    3.  Interval addition on $A$.
    4.  Query the interval sum of $B$.

    After each operation, if the value of $A_i$ changes, add $1$ to $B_i$. $n,m\le 3\times 10^5$.

First, consider the easiest operation: interval addition. As long as $x\neq 0$, all numbers in the interval change, so perform an interval addition on $B$.

For interval maximum/minimum operations, you find that setting tags and propagating tags correspond one-to-one with the $B$ array. Essentially, you divide the numbers in the sequence into three categories: maximums, minimums, and non-extremes, and maintain them separately (though you don't explicitly build the extreme sets, this doesn't hinder the maintenance operations). Therefore, when setting tags, you can simultaneously update information for $B$ (note: not setting tags on $B$, but updating information!). When querying, you query on $A$, and when propagating tags, you simultaneously update information for $B$. After finding the required node, return the information of $B$. This operation essentially delegates the maintenance of extreme value information to $B$. Additionally, number set overlap still needs to be handled.

???+ note "[CTSN loves segment tree](https://www.luogu.com.cn/problem/U180387)"
    Maintain two sequences $a,b$, and perform 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 divide the candidate answers $A_i+B_i$ in the interval $[l,r]$ into four categories: $A_i,B_i$ are both not the interval maximum of sequences $A,B$; $A_i$ is the interval maximum of sequence $A$ but $B_i$ is not the interval maximum of sequence $B$; $A_i$ is not the interval maximum of sequence $A$ but $B_i$ is the interval maximum of sequence $B$; $A_i,B_i$ are both the interval maximums of sequences $A,B$. We denote them as $C_{0,0},C_{1,0},C_{0,1},C_{1,1}$, respectively. Additionally, we normally maintain the interval maximum and second maximum of sequences $A$ and $B$. When propagating interval addition tags and $\min$ tags, the handling of the maximum and second maximum of $A,B$ is consistent with the two examples above. The $\min$ tag on $A$ affects $C_{1,1}$ and $C_{1,0}$; the tag on $B$ affects $C_{1,1}$ and $C_{0,1}$. Addition on $A,B$ affects $C_{0,0},C_{1,0},C_{0,1},C_{1,1}$. Just be mindful of boundary cases where $C_{0,0},C_{1,0},C_{0,1}$ might not exist (e.g., for interval $[i,i]$, only the maximums of $A,B$ and $C_{1,1}$ exist).

Next, consider how to maintain $C_{0,0},C_{1,0},C_{0,1},C_{1,1}$ during pushup. After updating the maximums of $A,B$, we can discuss whether the $A,B$ maximums of the left and right children are equal to the current node's $A,B$ maximums. We explain using the left child as an example; the right child is handled similarly:

-   When the left child's $A,B$ maximums are both equal to the current node's $A,B$ maximums, 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.
-   When the left child's $A$ maximum equals the current node's $A$ maximum, but the $B$ maximums are not equal, the left child's $C_{1,0},C_{1,1}$ contribute to the node's $C_{1,0}$, and $C_{0,0},C_{0,1}$ contribute to the node's $C_{0,0}$.
-   When the left child's $A$ maximum is not equal to the current node's $A$ maximum, but the $B$ maximums are equal, the left child's $C_{0,1},C_{1,1}$ contribute to the node's $C_{0,1}$, and $C_{0,0},C_{1,0}$ contribute to the node's $C_{0,0}$.
-   When the left child's $A,B$ maximums are both not equal to the current node's $A,B$ maximums, the left child's $C_{0,0},C_{1,0},C_{0,1},C_{1,1}$ only contribute to the node's $C_{0,0}$.

The $\max(C_{0,0},C_{1,0},C_{0,1},C_{1,1})$ from the interval query result is the answer.

Since we need to maintain both interval $\min$ and interval addition, the complexity remains $O(m\log^2 n)$.

```cpp
#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

In this chapter, we presented four example problems, explaining the maintenance of basic interval maximum/minimum operations, priority handling of multiple tags, the idea of number set classification, and maintenance of multiple categories. Essentially, the basic idea for handling interval maximum/minimum operations is the classification and efficient merging of number set information. In the next chapter, we will explore problems related to historical interval maximum/minimum values.

Historical Maximum/Minimum Problems

Historical Maximum/Minimum is Not Persistence

Note that the historical maximum/minimum problems discussed in this chapter are different from so-called persistent data structures. We refer to these special problems as historical maximum/minimum problems. Historical maximum/minimum problems can be divided into three categories.

Historical Maximum

Simply put, the historical maximum of a position is the maximum value that has ever appeared at that position. Formally, we define an auxiliary array \(B\), initially identical to \(A\). After each operation on \(A\), we take the \(\max\) over the entire array:

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

Then, we call \(B_i\) the historical maximum of this position.

Historical Minimum

The definition is similar to historical maximum. After each operation on \(A\), we take the \(\min\) over the entire array. Then, we call \(B_i\) the historical minimum of this position.

Historical Version Sum

The auxiliary array \(B\) is initially all \(0\). After each operation, we accumulate the entire \(A\) array onto the \(B\) array:

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

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

Next, we discuss historical maximum/minimum problems divided into four categories.

Problems Solvable with Tags

CPU Monitoring

Sequences \(A,B\) are initially the same:

  1. Interval assignment \(x\) on \(A\).
  2. Interval addition \(x\) on \(A\).
  3. Query the interval \(\max\) of \(A\).
  4. Query the interval \(\max\) of \(B\).

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

First, ignore operation 1. Then we only have interval addition operations. We maintain a tag \(Add\) representing the value added to the current interval; this tag can solve the interval \(\max\) problem. Next, consider the historical interval \(\max\). We define a tag \(Pre\), whose meaning is: during the lifetime of this tag, the historical maximum of the \(Add\) tag.

This definition might be vague. Therefore, we first explain the lifetime of a tag. A tag goes through the following process:

  1. Created at node \(u\).
  2. While receiving several new tags at node \(u\), merged with the new tags (for tags of the same type).
  3. The tag at node \(u\) is propagated to \(u\)'s children, and \(u\)'s tag is cleared.

We consider that during this process, from step 1 to before step 3, is the lifetime of the tag at node \(u\). After two tags merge, they become the same tag, and their lifetimes also merge (i.e., take the earlier creation time as the start of the lifetime). An equivalent statement is: the time period from the last moment this node's tag was propagated to the current moment.

Why define lifetime? Using this concept, we can prove: during the lifetime of a node's tag, its child nodes do not undergo any changes and retain the state before this lifetime. The reason is simple: because during this period, you did not propagate tags.

Thus, you can ensure that the historical maximum \(Add\) during the current tag's lifetime can be updated to the child nodes' tags and information. Because the child nodes' tags and information have not changed during this time period. So we propagate \(u\)'s tag to its child \(s\), and it's not hard to see:

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

Similarly, information updates are done using the corresponding tags.

Next, consider operation 1.

The interval assignment operation turns all numbers into one number. After that, whether it's interval addition/subtraction or assignment, all numbers in the interval remain the same (unless you end the current tag's lifetime and propagate tags). Therefore, we can treat all tags after the first interval assignment as interval assignment tags. That is, a tag's lifetime is roughly divided into two stages:

  1. Merging of several addition/subtraction operation tags, without receiving any assignment tag.
  2. Assignment operation tags, without any addition/subtraction tags (addition/subtraction tags are converted to assignment tags).

So we split the node's Pre tag into \((P_1,P_2)\). \(P_1\) represents the maximum addition/subtraction tag in the first stage; \(P_2\) represents the maximum assignment tag in the second stage. Using a similar method, we can perform tag propagation and information updates. The time complexity is \(O(m\log n)\) (note: this problem does not have interval \(\max\)/\(\min\) operations 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
115
```cpp
#include <algorithm>
#include <climits>
#include <iostream>
using namespace std;
using ll = long long;

constexpr int N = 1e5 + 7;

struct Tree {
  int mx, _mx;  // interval maximum value, interval historical maximum value
  int ad, _ad;  // interval addition tag, interval stage historical maximum addition tag
  int st, _st;  // interval modification value, interval stage historical maximum modification tag
} 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;
}
```

本页面最近更新：，更新历史
发现错误？想一起完善？ 在 GitHub 上编辑此页！
本页面贡献者：OI-wiki
本页面的全部内容在 CC BY-SA 4.0 和 SATA 协议之条款下提供，附加条款亦可能应用