AIOJ

This page discusses the segment-tree treatment of historical range-extremum queries mentioned by Ji in the 2016 National Training Team Paper Collection.

Range Extremum Operations

Broadly speaking, a range-extremum operation applies to every number in the interval $[l,r]$ , using $x$ to take $\max$ or $\min$ ; that is, $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:

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

There are multiple test cases, with $T\le 100,~\sum n,\sum m\le 10^6$ .

Taking the range $\min$ means that only numbers greater than $t$ change. Thus, the operation acts not on the entire interval but on “the numbers in this interval greater than $t$ .” We can therefore use the following idea: each node maintains the maximum $Max$ , second maximum $Se$ , range sum $Sum$ , and count of maximum values $Cnt$ for its interval. We now consider applying $t$ to $\min$ on an interval.

If $Max\le t$ , then $t$ is clearly ineffective, so return immediately.
If $Se<t < Max$ , then $t$ can update the maximum of the current interval. Add $Cnt(t-Max)$ to the range sum, update $Max$ to $t$ , and set a tag.
If $t\le Se$ , we do not know how many numbers need to be updated. We therefore recurse downward by brute force and then pull the information back up.

What is the complexity of this algorithm? A potential-function analysis gives complexity $O(m\log n)$ . The detailed analysis appears in the paper.

#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 the information upward
  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) {  // Apply the tag directly without recursively searching
  if (mx[u] <= tg) return;
  sum[u] += (1ll * tg - mx[u]) * cn[u];
  mx[u] = tag[u] = tg;
}

void pushdown(int u) {  // Push the tag downward
  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 extrema
  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 the 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() {  // Follow the 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 Contestant

Maintain a sequence $a$ and perform the following operations:

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

$n,m\le 5\times 10^5,~|a_i|\le 10^8$ . For all type- $1$ operations, $|x|\le 10^3$ ; the other operations satisfy $|x|\le10^8$ .

By the same method, maintain the maximum, second maximum, count of maximum values, minimum, second minimum, count of minimum values, and range sum. In addition, maintain tags for the range $\max$ , range $\min$ , and range addition. Compared with the previous problem, this introduces an ordering issue when pushing tags down. We use the following strategy:

The range-add tag has highest priority; the other two tags have equal status.
When a node receives a tag $v$ , use $v$ to update the satellite information and the node's range-add tag, and also use v to update the range- $\max$ and range- $\min$ tags.
When applying the value $v$ with operation $\min$ to a node (ignoring the brute-force process and assuming the tag conditions hold), update the satellite information and compare with the range- $\max$ tag. If $v$ is less than the range- $\max$ tag, all values will ultimately become v, so change the range- $\max$ tag to $v$ ; otherwise, do nothing.
Applying range v- $\max$ is analogous.

When maintaining the information, value sets may overlap for a segment containing only one or two numbers. For example, a value may be both the maximum and the second minimum, so this case must be handled specially.

#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) {
  // Note the comparison 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 range-$\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 the sentinel 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 to 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;
}

Ji proved that this algorithm has complexity $O(m\log^2 n)$ .

Mzl loves segment tree

Maintain two sequences $A,B$ ; initially every value in $B$ is $0$ . The operations are:

Apply a range operation to $A$ , taking $\min$ .
Apply a range operation to $A$ , taking $\max$ .
Add on a range of $A$ .
Query the range sum of $B$ .

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

First consider the easiest operation, range addition. If $x\neq 0$ , every value in the interval changes, so we can perform one range addition on B.

For range-extremum operations, observe that applying and pushing tags corresponds one-to-one with the array $B$ . Essentially, divide the sequence values into three classes: maximum values, minimum values, and non-extremal values, and maintain each class separately (although the actual extremal sets are not constructed, this does not prevent the maintenance). Thus, update $B$ while applying a tag (note: do not apply a tag to $B$ ; update its information). When querying, query $A$ , and update $B$ while pushing a tag. Once the needed node is found, return the information of $B$ . In essence, this transfers the extremal information to $B$ for maintenance. The issue of duplicate values must still be handled.

CTSN loves segment tree

Maintain two sequences $a,b$ and perform the following operations:

1 l r x $\forall l\le i\le r,~ a_i=\min(a_i,x)$ .
2 l r x $\forall l\le i\le r,~ b_i=\min(b_i,x)$ .
3 l r x $\forall l\le i\le r,~ a_i=a_i+x$ .
4 l r x $\forall l\le i\le r,~ b_i=b_i+x$ .
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$ .

In the interval $[l,r]$ , divide the candidate answers $A_i+B_i$ into four classes: $A_i,B_i$ are 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 $B$ ; $A_i$ is not the interval maximum of $A$ but $B_i$ is the interval maximum of $B$ ; and $A_i,B_i$ are the interval maxima of $A,B$ . Denote these four classes by $C_{0,0},C_{1,0},C_{0,1},C_{1,1}$ , respectively. We also maintain the interval maximum and second maximum of $A,B$ . When pushing range-add and $\min$ tags, handle the maxima and second maxima of $A,B$ as in the preceding two examples. A tag on $A$ , namely a $\min$ tag, affects $C_{1,1}$ and $C_{1,0}$ ; a tag on $B$ affects $C_{1,1}$ and $C_{0,1}$ . Addition on $A,B$ affects all of $C_{0,0},C_{1,0},C_{0,1},C_{1,1}$ . Only the boundary cases where $C_{0,0},C_{1,0},C_{0,1}$ do not exist require attention (for example, on interval $[i,i]$ only the maximum of $A,B$ and $C_{1,1}$ exists).

We next consider how to maintain $C_{0,0},C_{1,0},C_{0,1},C_{1,1}$ during pushup. After updating the maxima of $A,B$ , consider whether the $A,B$ maxima of the left and right children equal the $A,B$ maxima of the current node. We explain using the left child; the right child is analogous:

If the left child's $A,B$ maxima equal the current node's $A,B$ maxima, the left child's $C_{0,0},C_{1,0},C_{0,1},C_{1,1}$ contribute respectively to the current node's $C_{0,0},C_{1,0},C_{0,1},C_{1,1}$ .
If the left child's $A$ maximum equals the current node's $A$ maximum but the $B$ maximum differs, the left child's $C_{1,0},C_{1,1}$ contribute to the node's $C_{1,0}$ , while $C_{0,0},C_{0,1}$ contribute to the node's $C_{0,0}$ .
If the left child's $A$ maximum differs from the current node's $A$ maximum but the $B$ maximum is equal, the left child's $C_{0,1},C_{1,1}$ contribute to the node's $C_{0,1}$ , while $C_{0,0},C_{1,0}$ contribute to the node's $C_{0,0}$ .
If the left child's $A,B$ maxima both differ from the current node's $A,B$ maxima, the left child's $C_{0,0},C_{1,0},C_{0,1},C_{1,1}$ contribute only to the node's $C_{0,0}$ .

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

Because range $\min$ and range addition must be maintained simultaneously, the complexity remains $O(m\log^2 n)$ .

#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 chapter presented four examples covering maintenance of basic range-extremum operations, priority handling for multiple tags, classification of value sets, and maintenance of multiple classifications. At its core, range-extremum processing is the classification and efficient merging of value-set information. The next chapter discusses historical range extrema.

Historical Extremum Problems

Historical Extrema Are Not Persistence

Note that the historical-extremum problems in this chapter are different from persistent data structures. We call these special problems historical-extremum problems. They can be divided into three types.

Historical Maximum

In simple terms, the historical maximum at a position is the maximum among all values that have appeared at that position. Formally, define an auxiliary array $B$ , initially identical to $A$ . After every operation on $A$ , take the $\max$ of the entire array:

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

We call $B_i$ the historical maximum at that position.

Historical Minimum

The definition is analogous to the historical maximum. After every operation on $A$ , take the $\min$ of the entire array. We then call $B_i$ the historical minimum at that position.

Historical Version Sum

The auxiliary array $B$ is initially all $0$ . After each operation, add the entire $A$ array to 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$ .

We next discuss four types of historical-extremum problem.

Problems Solvable with Tags

CPU Monitoring

The sequences $A,B$ are initially identical:

Apply a range assignment to $A$ , setting it to $x$ .
Add on a range of $A$ the amount $x$ .
Query the range maximum of $A$ , namely $\max$ .
Query the range maximum of $B$ , namely $\max$ .

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

First ignore operation 1. With only range additions, maintain a tag $Add$ representing the value added to the current interval; this tag handles range $\max$ queries. Now consider the historical range $\max$ . Define a tag $Pre$ , whose meaning is the historical maximum of the $Add$ tag during the tag's lifetime.

This definition may be unclear, so first explain a tag's lifetime. A tag undergoes the following process:

It is created at node $u$ .
At node $u$ , it is merged with several new tags as they are received (meaning tags of the same type).
The tag at node $u$ is pushed to $u$ 's children, and $u$ 's tag is cleared.

We regard the period from step 1 until just before step 3 as the lifetime of the tag at node $u$ . When two tags merge into one, their lifetimes merge as well (the earlier creation time becomes the start of the lifetime). Equivalently, this is the interval from the last time the node's tag was pushed down to the current time.

Why define a lifetime? Using this concept, we can prove that during the lifetime of a node's tag, its children do not change and retain their state from before that lifetime. The reason is simple: no tag is pushed down during this period.

Therefore, the historical maximum of $Add$ during the current tag lifetime can be propagated to the children's tags and information, because their tags and information have not changed during this period. When we push the tag of $u$ to its child $s$ , we obtain

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

The information is updated similarly, using the corresponding tags.

Now consider operation 1.

A range assignment makes all values equal. Afterward, regardless of whether we add, subtract, or assign, all values in the interval remain equal (unless the current tag lifetime ends and the tag is pushed down). Thus, all tags after the first range assignment can be regarded as range-assignment tags. In other words, a tag lifetime is roughly divided into two phases:

Merging several add/subtract operation tags, without ever receiving an assignment tag.
The assignment tag, with no separate add/subtract tag (the add/subtract tag is converted into an assignment tag).

We therefore split the node's Pre tag into $(P_1,P_2)$ . $P_1$ is the maximum add/subtract tag in the first phase; $P_2$ is the maximum assignment tag in the second phase. Similar methods handle tag propagation and information updates. The time complexity is $O(m\log n)$ (this problem has no operation that takes an interval's $x$ with respect to x).

#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-add tag; historical maximum range-add tag for the phase
  int st, _st;  // Range-assignment value; historical maximum assignment tag for 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;
}