跳转至

區間最值操作 & 區間歷史最值

本文講解吉老師在 2016 年國家集訓隊論文中提到的線段樹處理歷史區間最值的問題。

區間最值

籠統地説，區間最值操作指，將區間 \([l,r]\) 的數全部對 \(x\) 取 \(\max\) 或 \(\min\)，即 \(a_i=\max(a_i,x)\) 或者 \(a_i=\min(a_i,x)\)。給一道例題吧。

HDU5306 Gorgeous Sequence

維護一個序列 \(a\)：

  1. 0 l r t \(\forall l\le i\le r,\ a_i=\min(a_i,t)\)。
  2. 1 l r 輸出區間 \([l,r]\) 中的最大值。
  3. 2 l r 輸出區間和。

多組數據，\(T\le 100,n\le 10^6,\sum m\le 10^6\)。

區間取 min，意味着只對那些大於 \(t\) 的數有更改。因此這個操作的對象不再是整個區間，而是「這個區間中大於 \(t\) 的數」。於是我們可以有這樣的思路：每個結點維護該區間的最大值 \(Max\)、次大值 \(Se\)、區間和 \(Sum\) 以及最大值的個數 \(Cnt\)。接下來我們考慮區間對 \(t\) 取 \(\min\) 的操作。

  1. 如果 \(Max\le t\)，顯然這個 \(t\) 是沒有意義的，直接返回；
  2. 如果 \(Se<t\le Max\)，那麼這個 \(t\) 就能更新當前區間中的最大值。於是我們讓區間和加上 \(Cnt(t-Max)\)，然後更新 \(Max\) 為 \(t\)，並打一個標記。
  3. 如果 \(t\le Se\)，那麼這時你發現你不知道有多少個數涉及到更新的問題。於是我們的策略就是，暴力遞歸向下操作。然後上傳信息。

這個算法的複雜度如何？使用勢能分析法可以得到複雜度是 \(O(m\log 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
#include <algorithm>
#include <cctype>
#include <cstdio>
using namespace std;
const int N = 1e6 + 6;

char nc() {
  static char buf[1000000], *p = buf, *q = buf;
  return p == q && (q = (p = buf) + fread(buf, 1, 1000000, stdin), p == q)
             ? EOF
             : *p++;
}

int rd() {
  int res = 0;
  char c = nc();
  while (!isdigit(c)) c = nc();
  while (isdigit(c)) res = res * 10 + c - '0', c = nc();
  return res;
}

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) {  // 向上更新标记
  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) {  // 单纯地打标记，不暴搜
  if (mx[u] <= tg) return;
  sum[u] += (1ll * tg - mx[u]) * cn[u];
  mx[u] = tag[u] = tg;
}

void pushdown(int u) {  // 下传标记
  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) {  // 建树
  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) {  // 查询最值
  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) {  // 数值
  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() {  // 根据题意
  n = rd(), m = rd();
  for (int i = 1; i <= n; i++) a[i] = rd();
  build();
  for (int i = 1; i <= m; i++) {
    int op, x, y, z;
    op = rd(), x = rd(), y = rd();
    if (op == 0)
      z = rd(), modify_min(x, y, z);
    else if (op == 1)
      printf("%d\n", query_max(x, y));
    else
      printf("%lld\n", query_sum(x, y));
  }
}

signed main() {
  t = rd();
  while (t--) go();
  return 0;
}

BZOJ4695 最假女選手

長度為 \(n\) 的序列，支持區間加 \(x\)/區間對 \(x\) 取 \(\max\)/區間對 \(x\) 取 \(\min\)/求區間和/求區間最大值/求區間最小值。

\(N,M\le 5\times 10^5,|A_i|\le 10^8\)。

同樣的方法，我們維護最大、次大、最大個數、最小、次小、最小個數、區間和。除了這些信息，我們還需要維護區間 \(\max\)、區間 \(\min\)、區間加的標記。相比上一道題，這就涉及到標記下傳的順序問題了。我們採用這樣的策略：

  1. 我們認為區間加的標記是最優先的，其餘兩種標記地位平等。
  2. 對一個結點加上一個 \(v\) 標記，除了用 \(v\) 更新衞星信息和當前結點的區間加標記外，我們用這個 v 更新區間 \(\max\) 和區間 \(\min\) 的標記。
  3. 對一個結點取 \(v\) 的 \(\min\)（這裏忽略暴搜的過程，假定標記滿足添加的條件），除了更新衞星信息，我們要與區間 \(\max\) 的標記做比較。如果 \(v\) 小於區間 \(\max\) 的標記，則所有的數最後都會變成 v，那麼把區間 \(\max\) 的標記也變成 \(v\)。否則不管。
  4. 區間取 v 的 \(\max\) 同理。

另外，BZOJ 這道題卡常……多數組線段樹的常數比結構體線段樹的常數大……在維護信息的時侯，當只有一兩個數的時侯可能發生數集重合，比如一個數既是最大值又是次小值。這種要特判。

  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
#include <cstdio>
#include <iostream>
using namespace std;

int rd() {
  char act = 0;
  int f = 1, x = 0;
  while (act = getchar(), act < '0' && act != '-')
    ;
  if (act == '-') f = -1, act = getchar();
  x = act - '0';
  while (act = getchar(), act >= '0') x = x * 10 + act - '0';
  return x * f;
}

const 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) {
  // 更新加法标记的同时，更新 $\min$ 和 $\max$ 标记
  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) {
  // 注意比较 $\max$ 标记
  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;        // 更新取 $\max$ 标记
  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;  // 取极限
  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);  // !!! 忘 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: 忘了返回
  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() {
  n = rd();
  for (int i = 1; i <= n; i++) a[i] = rd();
  build();
  m = rd();
  for (int i = 1; i <= m; i++) {
    int op, l, r, x;
    op = rd(), l = rd(), r = rd();
    if (op <= 3) x = rd();  // scanf("%d",&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)
      printf("%lld\n", qsum(l, r));
    else if (op == 5)
      printf("%lld\n", qmax(l, r));
    else
      printf("%lld\n", qmin(l, r));
  }
  return 0;
}

吉老師證出來這個算法的複雜度是 \(O(m\log^2 n)\) 的。

Mzl loves segment tree

兩個序列 \(A,B\)，一開始 \(B\) 中的數都是 \(0\)。維護的操作是：

  1. 對 \(A\) 做區間取 \(\min\)
  2. 對 \(A\) 做區間取 \(\max\)
  3. 對 \(A\) 做區間加
  4. 詢問 \(B\) 的區間和

每次操作完後，如果 \(A_i\) 的值發生變化，就給 \(B_i\) 加 \(1\)。\(n,m\le 3\times 10^5\)。

先考慮最容易的區間加操作。只要 \(x\neq 0\) 那麼整個區間的數都變化，所以給 B 作一次區間加即可。

對於區間取最值的操作，你發現你打標記與下傳標記是與 \(B\) 數組一一對應的。本質上你將序列的數分成三類：最大值、最小值、非最值。並分別維護（只不過你沒有建出具體的最值集合而已，但這並不妨礙維護的操作）。因此在打標記的時侯順便給 \(B\) 更新信息即可（注意不是給 \(B\) 打標記！是更新信息！）。查詢的時侯，你在 \(A\) 上查詢，下傳標記的時侯順便給 \(B\) 更新信息。找到需要的結點後，返回 \(B\) 的信息即可。這種操作本質上就是把最值的信息拿給 \(B\) 去維護了。另外仍要處理數集的重複問題。

CTSN loves segment tree

兩個序列 \(A,B\)：

  1. 對 \(A\) 做區間取 \(\min\)
  2. 對 \(B\) 做區間取 \(\min\)
  3. 對 \(A\) 做區間加
  4. 對 \(B\) 做區間加

  5. 詢問區間的 \(A_i+B_i\) 的最大值

    \(n,m\le 3\times 10^5\)。

我們把區間中的 位置 分成四類：在 \(A,B\) 中同是區間最大值的位置、在 \(A\) 中是區間最大值在 \(B\) 中不是的位置、在 \(B\) 中是區間最大值在 \(A\) 中不是的位置、在 \(A,B\) 中都不是區間最大值的位置。對這四類數分別維護 答案 和 標記 即可。舉個例子，我們維護 \(C_{1\sim 4},M_{1\sim 4},A_{\max},B_{\max}\) 分別表示當前區間中四類數的個數，四類數的答案的最大值，\(A\) 序列的最大值、\(B\) 序列的最大值。然後合併信息該怎麼合併就怎麼合併了。

複雜度仍是 \(O(m\log^2 n)\)。

小結

在第本章節中我們給出了四道例題，分別講解了基本區間最值操作的維護、多個標記的優先級處理、數集分類的思想以及多個分類的維護。本質上處理區間最值的基本思想就是數集信息的分類維護與高效合併。在下一章節中，我們將探討歷史區間最值的相關問題。

歷史最值問題

歷史最值不等於可持久化

注意，本章所講到的歷史最值問題不同於所謂的可持久化數據結構。這類特殊的問題我們將其稱為歷史最值問題。歷史最值的問題可以分為三類。

歷史最大值

簡單地説，一個位置的歷史最大值就是當前位置下曾經出現過的數的最大值。形式化地定義，我們定義一個輔助數組 \(B\)，一開始與 \(A\) 完全相同。在 \(A\) 的每次操作後，我們對整個數組取 \(\max\)：

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

這時，我們將 \(B_i\) 稱作這個位置的歷史最大值，

歷史最小值

定義與歷史最大值類似，在 \(A\) 的每次操作後，我們對整個數組取 \(\min\)。這時，我們將 \(B_i\) 稱作這個位置的歷史最小值，

歷史版本和

輔助數組 \(B\) 一開始全部是 \(0\)。在每一次操作後，我們把整個 \(A\) 數組累加到 \(B\) 數組上

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

我們稱 \(B_i\) 為 \(i\) 這個位置上的歷史版本和。

接下來，我們將歷史最值問題分成四類討論。

可以用標記處理的問題

CPU 監控

序列 \(A,B\) 一開始相同：

  1. 對 \(A\) 做區間覆蓋 \(x\)
  2. 對 \(A\) 做區間加 \(x\)
  3. 詢問 \(A\) 的區間 \(\max\)
  4. 詢問 \(B\) 的區間 \(\max\)

每次操作後，我們都進行一次更新，\(\forall i\in [1,n],\ B_i=\max(B_i,A_i)\)。\(n,m\le 10^5\)。

我們先不考慮操作 1。那麼只有區間加的操作，我們維護標記 \(Add\) 表示當前區間增加的值，這個標記可以解決區間 \(\max\) 的問題。接下來考慮歷史區間 \(\max\)。我們定義標記 \(Pre\)，該標記的含義是：在該標記的生存週期內，\(Add\) 標記的歷史最大值。

這個定義可能比較模糊。因此我們先解釋一下標記的生存週期。一個標記會經歷這樣的過程：

  1. 在結點 \(u\) 被建立。
  2. 在結點 \(u\) 接受若干個新的標記的同時，與新的標記合併（指同類標記）
  3. 結點 \(u\) 的標記下傳給 \(u\) 的兒子，\(u\) 的標記清空

我們認為在這個過程中，從 1 開始到 3 之前，都是結點 \(u\) 的標記的生存週期。兩個標記合併後，成為同一個標記，那麼他們的生存週期也會合並（即取建立時間較早的那個做為生存週期的開始）。一個與之等價的説法是，從上次把這個結點的標記下傳的時刻到當前時刻這一時間段。

為什麼要定義生存週期？利用這個概念，我們可以證明：在一個結點標記的生存週期內，其子結點均不會發生任何變化，並保留在這個生存週期之前的狀態。道理很簡單，因為在這個期間你是沒有下傳標記的。

於是，你就可以保證，在當前標記生存週期內的歷史 \(Add\) 的最大值是可以更新到子結點的標記和信息上的。因為子結點的標記和信息在這個時間段內都沒有變過。於是我們把 \(u\) 的標記下傳給它的兒子 \(s\)，不難發現

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

那麼信息的更新也是類似的，拿對應的標記更新即可。

接下來，我們考慮操作 1。

區間覆蓋操作，會把所有的數變成一個數。在這之後，無論是區間加減還是覆蓋，整個區間的數仍是同一個（除非你結束當前標記的生存週期，下傳標記）。因此我們可以把第一次區間覆蓋後的所有標記都看成區間覆蓋標記。也就是説一個標記的生存週期被大致分成兩個階段：

  1. 若干個加減操作標記的合併，沒有接收過覆蓋標記。
  2. 覆蓋操作的標記，沒有所謂的加減標記（加減標記轉化為覆蓋標記）

於是我們把這個結點的 Pre 標記拆成 \((P_1,P_2)\)。\(P_1\) 表示第一階段的最大加減標記；\(P_2\) 表示第二階段的最大覆蓋標記。利用相似的方法，我們可以對這個做標記下傳和信息更新。時間複雜度是 \(O(m\log n)\) 的（這個問題並沒有區間對 \(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
116
117
118
119
120
121
122
123
124
125
126
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;

char nc() {
  static char buf[1000000], *p = buf, *q = buf;
  return p == q && (q = (p = buf) + fread(buf, 1, 1000000, stdin), p == q)
             ? EOF
             : *p++;
}

ll rd() {  // LLONG_MIN LMAX=9,223,372,036,854,775,807
  ll s = 0, w = 1;
  char ch = nc();
  while (ch < '0' || ch > '9') {
    if (ch == '-') w = -1;
    ch = nc();
  }
  while (ch >= '0' && ch <= '9') s = s * 10 + ch - '0', ch = nc();
  return s * w;
}

const int N = 1e5 + 7;

struct Tree {
  int mx, _mx;  // 区间最大值 区间历史最大值
  int ad, _ad;  // 区间加标记 区间阶段历史最大加标记
  int st, _st;  // 区间修改值 区间阶段历史最大修改标记
} 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() {
  n = rd();
  for (int i = 1; i <= n; ++i) a[i] = rd();
  build();
  int m = rd(), z;
  for (int i = 1; i <= m; ++i) {
    char op = nc();
    while (op == ' ' || op == '\r' || op == '\n') op = nc();
    L = rd(), R = rd();
    if (op == 'Q')
      printf("%d\n", qmax());
    else if (op == 'A')
      printf("%d\n", qmaxh());
    else if (op == 'P')
      add(rd());
    else
      tset(rd());
  }
  return 0;
}
本页面最近更新：，更新历史
发现错误？想一起完善？ 在 GitHub 上编辑此页！
本页面贡献者：OI-wiki
本页面的全部内容在 CC BY-SA 4.0 和 SATA 协议之条款下提供，附加条款亦可能应用