These are the notes for Competitive Programming episode 62. A range chmin update (a[i] = min(a[i], x) on [l, r]) cannot be a simple lazy tag: how much a block's sum drops depends on every value in it. Segment tree beats (Ji Driver's segment tree) keeps in every node the maximum, the strict second maximum and the count of the maximum: if second max < x < max, only the maxima change and the sum drops by (max − x) · count; otherwise the update goes deeper. The total work is amortised O((n + q) log n). Price Cap shows the loop (TLE), a non-strict second maximum (correct but TLE, because the stop rule never fires on equal maxima), and the accepted version. Best Streak (maximum subarray sum in a range, with point updates) shows mergeable nodes: (sum, best prefix, best suffix, best) merged in O(1); an "empty" node made of zeros prints 0 where -2 is right. Stress tests pass. Every C++ example was compiled with g++ -O2 -std=c++17 main.cpp -o main (g++ 13, the same command as the SyntaxPilot compiler); all outputs below are real.
The real-life hook
A market inspector hangs a board at the start of every lane: the top price in the lane, how many shops charge it, and the next price below it. A government cap of ₹8 arrives. If the top is ₹9 at two shops and the next price is ₹7, only those two shops change, each by ₹1: the lane total drops by 2 without walking in. A cap of ₹5 when the next price is ₹7 changes shops by different amounts, so the inspector must walk in, lane by lane.
Problem J1 · Price Cap
(Written for this course, in the style of the classic "Gorgeous Sequence" family.)
- Input: n q (n, q ≤ 5 · 10^5), prices a[1..n], then
1 l r x(a[i] = min(a[i], x) for l ≤ i ≤ r) or2 l r(print the sum).
6 5
4 9 2 9 7 1
2 1 6
1 2 5 6
2 1 6
1 1 6 3
2 2 4
Answers: 32 25 8.
The obvious attempt: loop over the range (TLE)
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
int n, q;
ll a[500001];
void cap(int l, int r, ll x) { for (int i = l; i <= r; i++) a[i] = min(a[i], x); }
ll total(int l, int r) {
ll s = 0;
for (int i = l; i <= r; i++) s += a[i];
return s;
}
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
cin >> n >> q;
for (int i = 1; i <= n; i++) cin >> a[i];
while (q--) {
int type, l, r;
cin >> type >> l >> r;
if (type == 1) {
ll x;
cin >> x;
cap(l, r, x);
} else cout << total(l, r) << "\n";
}
}
32
25
8
Worst case: prices 1..n and full-range caps n, n − 2, n − 4, … with sums in between:
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
int n, q;
ll a[500001];
void cap(int l, int r, ll x) { for (int i = l; i <= r; i++) a[i] = min(a[i], x); }
ll total(int l, int r) {
ll s = 0;
for (int i = l; i <= r; i++) s += a[i];
return s;
}
int main() {
n = q = 500000; // prices 1..n, then lower and lower caps
for (int i = 1; i <= n; i++) a[i] = i;
ll check = 0;
for (int i = 0; i < q; i++) {
if (i % 2 == 0) cap(1, n, n - i);
else check ^= total(1, n - i);
}
cout << check << "\n";
}
Time Limit Exceeded
Why a lazy tag can't do it
For "add x" a block's sum changes by x · length, whatever the values are. For "chmin x" the change is Σ max(0, a[i] − x), which depends on every value. A tag alone can't say how much the sum drops… unless only one distinct value changes: the maximum.
Segment tree beats
Every node keeps sum, mx1 (max), mx2 (strictly smaller second max, −∞ if none) and cnt (how many equal mx1). For an update with x on a node:
x ≥ mx1: nothing changes; return.- Node fully inside the range and
mx2 < x: only the maxima drop:sum −= (mx1 − x) · cnt,mx1 = x. Stop. - Otherwise push, recurse into both children, pull.
Push needs no separate tag: a child whose mx1 exceeds the parent's mx1 missed a cap, so cap it to the parent's maximum.
Why it is fast (sketch). Case 3 happens only when x ≤ mx2, i.e. at least two distinct values in the node become equal to x. Each such "extra" visit reduces the number of distinct values in some node; a potential argument bounds the total number of extra visits by O((n + q) log n).
A second max that isn't strict (correct, but TLE)
If equal maxima make mx2 = mx1, rule 2 (mx2 < x < mx1) can never fire on a node whose maximum appears in both children, so every update walks down to every shop with the maximum. The answers stay right:
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
int n, q, cnt[2000004]; // cnt[v] = how many equal mx1[v]
ll a[500001], sum[2000004], mx1[2000004], mx2[2000004]; // max, second max
void pull(int v) {
int L = 2 * v, R = 2 * v + 1;
sum[v] = sum[L] + sum[R];
if (mx1[L] == mx1[R]) {
mx1[v] = mx1[L], cnt[v] = cnt[L] + cnt[R];
mx2[v] = mx1[L]; // "second max" = the other max
} else if (mx1[L] > mx1[R]) {
mx1[v] = mx1[L], cnt[v] = cnt[L];
mx2[v] = max(mx2[L], mx1[R]);
} else {
mx1[v] = mx1[R], cnt[v] = cnt[R];
mx2[v] = max(mx1[L], mx2[R]);
}
}
void build(int v, int l, int r) {
if (l == r) { sum[v] = mx1[v] = a[l]; mx2[v] = LLONG_MIN; cnt[v] = 1; return; }
int m = (l + r) / 2;
build(2 * v, l, m);
build(2 * v + 1, m + 1, r);
pull(v);
}
void capNode(int v, ll x) { // only the maxima drop to x
if (x >= mx1[v]) return;
sum[v] -= (mx1[v] - x) * cnt[v];
mx1[v] = x;
}
void push(int v) { capNode(2 * v, mx1[v]); capNode(2 * v + 1, mx1[v]); }
void update(int v, int l, int r, int ql, int qr, ll x) {
if (qr < l || r < ql || x >= mx1[v]) return; // nothing above x here
if (ql <= l && r <= qr && x > mx2[v]) { capNode(v, x); return; } // only maxima change
push(v);
int m = (l + r) / 2;
update(2 * v, l, m, ql, qr, x);
update(2 * v + 1, m + 1, r, ql, qr, x);
pull(v);
}
ll query(int v, int l, int r, int ql, int qr) {
if (qr < l || r < ql) return 0;
if (ql <= l && r <= qr) return sum[v];
push(v);
int m = (l + r) / 2;
return query(2 * v, l, m, ql, qr) + query(2 * v + 1, m + 1, r, ql, qr);
}
void cap(int l, int r, ll x) { update(1, 1, n, l, r, x); }
ll total(int l, int r) { return query(1, 1, n, l, r); }
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
cin >> n >> q;
for (int i = 1; i <= n; i++) cin >> a[i];
build(1, 1, n);
while (q--) {
int type, l, r;
cin >> type >> l >> r;
if (type == 1) {
ll x;
cin >> x;
cap(l, r, x);
} else cout << total(l, r) << "\n";
}
}
32
25
8
…but the worst case, where thousands of shops share the top price after a few caps:
Time Limit Exceeded
The accepted version
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
int n, q, cnt[2000004]; // cnt[v] = how many equal mx1[v]
ll a[500001], sum[2000004], mx1[2000004], mx2[2000004]; // max, second max
void pull(int v) {
int L = 2 * v, R = 2 * v + 1;
sum[v] = sum[L] + sum[R];
if (mx1[L] == mx1[R]) {
mx1[v] = mx1[L], cnt[v] = cnt[L] + cnt[R];
mx2[v] = max(mx2[L], mx2[R]); // strictly below the max
} else if (mx1[L] > mx1[R]) {
mx1[v] = mx1[L], cnt[v] = cnt[L];
mx2[v] = max(mx2[L], mx1[R]);
} else {
mx1[v] = mx1[R], cnt[v] = cnt[R];
mx2[v] = max(mx1[L], mx2[R]);
}
}
void build(int v, int l, int r) {
if (l == r) { sum[v] = mx1[v] = a[l]; mx2[v] = LLONG_MIN; cnt[v] = 1; return; }
int m = (l + r) / 2;
build(2 * v, l, m);
build(2 * v + 1, m + 1, r);
pull(v);
}
void capNode(int v, ll x) { // only the maxima drop to x
if (x >= mx1[v]) return;
sum[v] -= (mx1[v] - x) * cnt[v];
mx1[v] = x;
}
void push(int v) { capNode(2 * v, mx1[v]); capNode(2 * v + 1, mx1[v]); }
void update(int v, int l, int r, int ql, int qr, ll x) {
if (qr < l || r < ql || x >= mx1[v]) return; // nothing above x here
if (ql <= l && r <= qr && x > mx2[v]) { capNode(v, x); return; } // only maxima change
push(v);
int m = (l + r) / 2;
update(2 * v, l, m, ql, qr, x);
update(2 * v + 1, m + 1, r, ql, qr, x);
pull(v);
}
ll query(int v, int l, int r, int ql, int qr) {
if (qr < l || r < ql) return 0;
if (ql <= l && r <= qr) return sum[v];
push(v);
int m = (l + r) / 2;
return query(2 * v, l, m, ql, qr) + query(2 * v + 1, m + 1, r, ql, qr);
}
void cap(int l, int r, ll x) { update(1, 1, n, l, r, x); }
ll total(int l, int r) { return query(1, 1, n, l, r); }
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
cin >> n >> q;
for (int i = 1; i <= n; i++) cin >> a[i];
build(1, 1, n);
while (q--) {
int type, l, r;
cin >> type >> l >> r;
if (type == 1) {
ll x;
cin >> x;
cap(l, r, x);
} else cout << total(l, r) << "\n";
}
}
32
25
8
One shop capped twice (8 then 2):
2
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
int n, q, cnt[2000004]; // cnt[v] = how many equal mx1[v]
ll a[500001], sum[2000004], mx1[2000004], mx2[2000004]; // max, second max
void pull(int v) {
int L = 2 * v, R = 2 * v + 1;
sum[v] = sum[L] + sum[R];
if (mx1[L] == mx1[R]) {
mx1[v] = mx1[L], cnt[v] = cnt[L] + cnt[R];
mx2[v] = max(mx2[L], mx2[R]); // strictly below the max
} else if (mx1[L] > mx1[R]) {
mx1[v] = mx1[L], cnt[v] = cnt[L];
mx2[v] = max(mx2[L], mx1[R]);
} else {
mx1[v] = mx1[R], cnt[v] = cnt[R];
mx2[v] = max(mx1[L], mx2[R]);
}
}
void build(int v, int l, int r) {
if (l == r) { sum[v] = mx1[v] = a[l]; mx2[v] = LLONG_MIN; cnt[v] = 1; return; }
int m = (l + r) / 2;
build(2 * v, l, m);
build(2 * v + 1, m + 1, r);
pull(v);
}
void capNode(int v, ll x) { // only the maxima drop to x
if (x >= mx1[v]) return;
sum[v] -= (mx1[v] - x) * cnt[v];
mx1[v] = x;
}
void push(int v) { capNode(2 * v, mx1[v]); capNode(2 * v + 1, mx1[v]); }
void update(int v, int l, int r, int ql, int qr, ll x) {
if (qr < l || r < ql || x >= mx1[v]) return; // nothing above x here
if (ql <= l && r <= qr && x > mx2[v]) { capNode(v, x); return; } // only maxima change
push(v);
int m = (l + r) / 2;
update(2 * v, l, m, ql, qr, x);
update(2 * v + 1, m + 1, r, ql, qr, x);
pull(v);
}
ll query(int v, int l, int r, int ql, int qr) {
if (qr < l || r < ql) return 0;
if (ql <= l && r <= qr) return sum[v];
push(v);
int m = (l + r) / 2;
return query(2 * v, l, m, ql, qr) + query(2 * v + 1, m + 1, r, ql, qr);
}
void cap(int l, int r, ll x) { update(1, 1, n, l, r, x); }
ll total(int l, int r) { return query(1, 1, n, l, r); }
int main() {
n = q = 500000; // prices 1..n, then lower and lower caps
for (int i = 1; i <= n; i++) a[i] = i;
build(1, 1, n);
ll check = 0;
for (int i = 0; i < q; i++) {
if (i % 2 == 0) cap(1, n, n - i);
else check ^= total(1, n - i);
}
cout << check << "\n";
}
58015411312
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
int n, q, cnt[2000004]; // cnt[v] = how many equal mx1[v]
ll a[500001], sum[2000004], mx1[2000004], mx2[2000004]; // max, second max
void pull(int v) {
int L = 2 * v, R = 2 * v + 1;
sum[v] = sum[L] + sum[R];
if (mx1[L] == mx1[R]) {
mx1[v] = mx1[L], cnt[v] = cnt[L] + cnt[R];
mx2[v] = max(mx2[L], mx2[R]); // strictly below the max
} else if (mx1[L] > mx1[R]) {
mx1[v] = mx1[L], cnt[v] = cnt[L];
mx2[v] = max(mx2[L], mx1[R]);
} else {
mx1[v] = mx1[R], cnt[v] = cnt[R];
mx2[v] = max(mx1[L], mx2[R]);
}
}
void build(int v, int l, int r) {
if (l == r) { sum[v] = mx1[v] = a[l]; mx2[v] = LLONG_MIN; cnt[v] = 1; return; }
int m = (l + r) / 2;
build(2 * v, l, m);
build(2 * v + 1, m + 1, r);
pull(v);
}
void capNode(int v, ll x) { // only the maxima drop to x
if (x >= mx1[v]) return;
sum[v] -= (mx1[v] - x) * cnt[v];
mx1[v] = x;
}
void push(int v) { capNode(2 * v, mx1[v]); capNode(2 * v + 1, mx1[v]); }
void update(int v, int l, int r, int ql, int qr, ll x) {
if (qr < l || r < ql || x >= mx1[v]) return; // nothing above x here
if (ql <= l && r <= qr && x > mx2[v]) { capNode(v, x); return; } // only maxima change
push(v);
int m = (l + r) / 2;
update(2 * v, l, m, ql, qr, x);
update(2 * v + 1, m + 1, r, ql, qr, x);
pull(v);
}
ll query(int v, int l, int r, int ql, int qr) {
if (qr < l || r < ql) return 0;
if (ql <= l && r <= qr) return sum[v];
push(v);
int m = (l + r) / 2;
return query(2 * v, l, m, ql, qr) + query(2 * v + 1, m + 1, r, ql, qr);
}
void cap(int l, int r, ll x) { update(1, 1, n, l, r, x); }
ll total(int l, int r) { return query(1, 1, n, l, r); }
int main() {
mt19937 rng(62);
for (int t = 1; t <= 500; t++) {
n = rng() % 12 + 1;
vector<ll> b(n + 1);
for (int i = 1; i <= n; i++) b[i] = a[i] = rng() % 10;
build(1, 1, n);
for (int k = 0; k < 30; k++) {
int l = rng() % n + 1, r = rng() % n + 1;
if (l > r) swap(l, r);
if (rng() % 2) {
ll x = rng() % 10;
cap(l, r, x);
for (int i = l; i <= r; i++) b[i] = min(b[i], x);
} else if (total(l, r) != accumulate(b.begin() + l, b.begin() + r + 1, 0LL)) {
cout << "mismatch on test " << t;
return 0;
}
}
}
cout << "all 500 tests passed";
}
all 500 tests passed
Problem J2 · Best Streak
(Written for this course.)
- Input: n q (n, q ≤ 2 · 10^5), profits a[1..n] (may be negative), then
1 i x(set day i to x) or2 l r(print the largest sum of a non-empty run of consecutive days inside [l, r]).
7 5
3 -5 4 -1 2 -6 1
2 1 7
2 2 3
1 4 3
2 1 7
2 5 6
Answers: 5 4 9 2.
Mergeable nodes
The best streak of a block may cross its middle, so one number per node is not enough. Store four:
| Field | Meaning | Merge of left A and right B |
|---|---|---|
| sum | total | A.sum + B.sum |
| pre | best non-empty prefix | max(A.pre, A.sum + B.pre) |
| suf | best non-empty suffix | max(B.suf, B.sum + A.suf) |
| best | best non-empty run inside | max(A.best, B.best, A.suf + B.pre) |
The merge is O(1), so point updates and range queries are O(log n). The same pattern solves "longest run of equal values", "longest increasing run", bracket matching and many more: decide what a node must remember so that two neighbours can be merged.
The bug: an empty node of zeros
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
struct Node { ll sum, pre, suf, best; }; // best prefix, best suffix, best inside
Node merge(const Node &A, const Node &B) {
return {A.sum + B.sum,
max(A.pre, A.sum + B.pre),
max(B.suf, B.sum + A.suf),
max({A.best, B.best, A.suf + B.pre})}; // or a streak across the middle
}
int n, q;
ll a[200001];
Node t[800004];
const Node EMPTY = {0, 0, 0, 0}; // nothing = all zeros?
Node leaf(ll x) { return {x, x, x, x}; }
void build(int v, int l, int r) {
if (l == r) { t[v] = leaf(a[l]); return; }
int m = (l + r) / 2;
build(2 * v, l, m);
build(2 * v + 1, m + 1, r);
t[v] = merge(t[2 * v], t[2 * v + 1]);
}
void setDay(int v, int l, int r, int i, ll x) {
if (l == r) { t[v] = leaf(x); return; }
int m = (l + r) / 2;
if (i <= m) setDay(2 * v, l, m, i, x);
else setDay(2 * v + 1, m + 1, r, i, x);
t[v] = merge(t[2 * v], t[2 * v + 1]);
}
Node query(int v, int l, int r, int ql, int qr) {
if (qr < l || r < ql) return EMPTY;
if (ql <= l && r <= qr) return t[v];
int m = (l + r) / 2;
return merge(query(2 * v, l, m, ql, qr), query(2 * v + 1, m + 1, r, ql, qr));
}
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
cin >> n >> q;
for (int i = 1; i <= n; i++) cin >> a[i];
build(1, 1, n);
while (q--) {
int type, x, y;
cin >> type >> x >> y;
if (type == 1) setDay(1, 1, n, x, y);
else cout << query(1, 1, n, x, y).best << "\n";
}
}
A shop that lost money every day:
4 3
-3 -2 -4 -6
2 1 4
2 2 4
2 1 3
-2
0
0
Parts of the query outside [l, r] return EMPTY = {0, 0, 0, 0}, which pretends to be a streak worth 0 and beats every real loss. An empty node must contribute 0 to the sum but never win a comparison:
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
struct Node { ll sum, pre, suf, best; }; // best prefix, best suffix, best inside
Node merge(const Node &A, const Node &B) {
return {A.sum + B.sum,
max(A.pre, A.sum + B.pre),
max(B.suf, B.sum + A.suf),
max({A.best, B.best, A.suf + B.pre})}; // or a streak across the middle
}
int n, q;
ll a[200001];
Node t[800004];
const Node EMPTY = {0, -(ll)4e18, -(ll)4e18, -(ll)4e18}; // nothing: never the best
Node leaf(ll x) { return {x, x, x, x}; }
void build(int v, int l, int r) {
if (l == r) { t[v] = leaf(a[l]); return; }
int m = (l + r) / 2;
build(2 * v, l, m);
build(2 * v + 1, m + 1, r);
t[v] = merge(t[2 * v], t[2 * v + 1]);
}
void setDay(int v, int l, int r, int i, ll x) {
if (l == r) { t[v] = leaf(x); return; }
int m = (l + r) / 2;
if (i <= m) setDay(2 * v, l, m, i, x);
else setDay(2 * v + 1, m + 1, r, i, x);
t[v] = merge(t[2 * v], t[2 * v + 1]);
}
Node query(int v, int l, int r, int ql, int qr) {
if (qr < l || r < ql) return EMPTY;
if (ql <= l && r <= qr) return t[v];
int m = (l + r) / 2;
return merge(query(2 * v, l, m, ql, qr), query(2 * v + 1, m + 1, r, ql, qr));
}
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
cin >> n >> q;
for (int i = 1; i <= n; i++) cin >> a[i];
build(1, 1, n);
while (q--) {
int type, x, y;
cin >> type >> x >> y;
if (type == 1) setDay(1, 1, n, x, y);
else cout << query(1, 1, n, x, y).best << "\n";
}
}
-2
-2
-2
5
4
9
2
Stress test against trying every streak
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
struct Node { ll sum, pre, suf, best; }; // best prefix, best suffix, best inside
Node merge(const Node &A, const Node &B) {
return {A.sum + B.sum,
max(A.pre, A.sum + B.pre),
max(B.suf, B.sum + A.suf),
max({A.best, B.best, A.suf + B.pre})}; // or a streak across the middle
}
int n, q;
ll a[200001];
Node t[800004];
const Node EMPTY = {0, -(ll)4e18, -(ll)4e18, -(ll)4e18}; // nothing: never the best
Node leaf(ll x) { return {x, x, x, x}; }
void build(int v, int l, int r) {
if (l == r) { t[v] = leaf(a[l]); return; }
int m = (l + r) / 2;
build(2 * v, l, m);
build(2 * v + 1, m + 1, r);
t[v] = merge(t[2 * v], t[2 * v + 1]);
}
void setDay(int v, int l, int r, int i, ll x) {
if (l == r) { t[v] = leaf(x); return; }
int m = (l + r) / 2;
if (i <= m) setDay(2 * v, l, m, i, x);
else setDay(2 * v + 1, m + 1, r, i, x);
t[v] = merge(t[2 * v], t[2 * v + 1]);
}
Node query(int v, int l, int r, int ql, int qr) {
if (qr < l || r < ql) return EMPTY;
if (ql <= l && r <= qr) return t[v];
int m = (l + r) / 2;
return merge(query(2 * v, l, m, ql, qr), query(2 * v + 1, m + 1, r, ql, qr));
}
int main() {
mt19937 rng(62);
for (int t = 1; t <= 500; t++) {
n = rng() % 12 + 1;
for (int i = 1; i <= n; i++) a[i] = (ll)(rng() % 11) - 7; // mostly losses
build(1, 1, n);
for (int k = 0; k < 30; k++) {
int l = rng() % n + 1, r = rng() % n + 1;
if (l > r) swap(l, r);
if (rng() % 2) {
ll x = (ll)(rng() % 11) - 7;
a[l] = x;
setDay(1, 1, n, l, x);
continue;
}
ll best = LLONG_MIN;
for (int i = l; i <= r; i++) {
ll s = 0;
for (int j = i; j <= r; j++) s += a[j], best = max(best, s);
}
if (query(1, 1, n, l, r).best != best) { cout << "mismatch on test " << t; return 0; }
}
}
cout << "all 500 tests passed";
}
all 500 tests passed
Complexity vs the constraints
| Method | Time | Verdict |
|---|---|---|
| J1: loop | O(n) per operation | TLE |
| J1: second max not strict | O(n) per update on equal maxima | TLE |
| J1: segment tree beats | O((n + q) log n) amortised | accepted |
| J2: Kadane per query | O(n) per query | too slow for 2 · 10^5 full queries |
| J2: mergeable nodes | O(log n) per operation | accepted |
Common mistakes (and the real outputs)
| Mistake | What you see | Why | Fix |
|---|---|---|---|
| loop over the range | Time Limit Exceeded |
O(n · q) | beats |
mx2 = mx1 when the maxima are equal |
Time Limit Exceeded |
rule 2 never fires | strict second max |
| no push in beats | wrong sums | children miss a cap | cap children to the parent max |
| rule 2 without "fully inside" | wrong sums | caps outside [l, r] | check ql ≤ l && r ≤ qr |
| empty node = zeros | 0 (expected -2) |
0 beats real losses | −∞ pre, suf, best |
| best = max(A.best, B.best) | too small | the crossing run is missed | + A.suf + B.pre |
mx2 initialised to 0 |
wrong with 0 or negatives | 0 can be a real value | LLONG_MIN |
Mini project
Implement the full "Gorgeous Sequence" tree: range chmin, range max and range sum (homework 2), then add range chmax and range add (keeping max, second max, count and the mirrored min, second min, count). Stress it with small values (0–5) so that equal values and collisions between max and min happen often.
Practice
These are the four homework problems from the episode. Every answer below came from a compiled C++ program (g++ -O2 -std=c++17); homework 3 was also checked against brute force on 150 random cases.
1. Range chmax (the mirror image). 1 l r x: a[i] = max(a[i], x); 2 l r: sum.
Solution
max(a, x) = −min(−a, −x): store −a, cap with −x, and negate the sums. (Or mirror the code with min, second min and count.) Sample: 1 5 2 8 3, chmax all with 4 → 25; chmax [2, 3] with 6 → sum of [1, 3] = 16.
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
int n, q, cnt[2000004]; // cnt[v] = how many equal mx1[v]
ll a[500001], sum[2000004], mx1[2000004], mx2[2000004]; // max, second max
void pull(int v) {
int L = 2 * v, R = 2 * v + 1;
sum[v] = sum[L] + sum[R];
if (mx1[L] == mx1[R]) {
mx1[v] = mx1[L], cnt[v] = cnt[L] + cnt[R];
mx2[v] = max(mx2[L], mx2[R]); // strictly below the max
} else if (mx1[L] > mx1[R]) {
mx1[v] = mx1[L], cnt[v] = cnt[L];
mx2[v] = max(mx2[L], mx1[R]);
} else {
mx1[v] = mx1[R], cnt[v] = cnt[R];
mx2[v] = max(mx1[L], mx2[R]);
}
}
void build(int v, int l, int r) {
if (l == r) { sum[v] = mx1[v] = a[l]; mx2[v] = LLONG_MIN; cnt[v] = 1; return; }
int m = (l + r) / 2;
build(2 * v, l, m);
build(2 * v + 1, m + 1, r);
pull(v);
}
void capNode(int v, ll x) { // only the maxima drop to x
if (x >= mx1[v]) return;
sum[v] -= (mx1[v] - x) * cnt[v];
mx1[v] = x;
}
void push(int v) { capNode(2 * v, mx1[v]); capNode(2 * v + 1, mx1[v]); }
void update(int v, int l, int r, int ql, int qr, ll x) {
if (qr < l || r < ql || x >= mx1[v]) return; // nothing above x here
if (ql <= l && r <= qr && x > mx2[v]) { capNode(v, x); return; } // only maxima change
push(v);
int m = (l + r) / 2;
update(2 * v, l, m, ql, qr, x);
update(2 * v + 1, m + 1, r, ql, qr, x);
pull(v);
}
ll query(int v, int l, int r, int ql, int qr) {
if (qr < l || r < ql) return 0;
if (ql <= l && r <= qr) return sum[v];
push(v);
int m = (l + r) / 2;
return query(2 * v, l, m, ql, qr) + query(2 * v + 1, m + 1, r, ql, qr);
}
void cap(int l, int r, ll x) { update(1, 1, n, l, r, x); }
ll total(int l, int r) { return query(1, 1, n, l, r); }
int main() {
// range chmax: a[i] = max(a[i], x). Store -a: max(a, x) = -min(-a, -x)
ios::sync_with_stdio(false);
cin.tie(nullptr);
cin >> n >> q;
for (int i = 1; i <= n; i++) cin >> a[i], a[i] = -a[i];
build(1, 1, n);
while (q--) {
int type, l, r;
cin >> type >> l >> r;
if (type == 1) {
ll x;
cin >> x;
cap(l, r, -x);
} else cout << -total(l, r) << "\n";
}
}
25
16
2. Chmin + range max + range sum. 1 l r x cap, 2 l r max, 3 l r sum.
Solution
The beats node already has mx1; a range max query just combines mx1 with pushes on the way.
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
int n, q, cnt[2000004]; // cnt[v] = how many equal mx1[v]
ll a[500001], sum[2000004], mx1[2000004], mx2[2000004]; // max, second max
void pull(int v) {
int L = 2 * v, R = 2 * v + 1;
sum[v] = sum[L] + sum[R];
if (mx1[L] == mx1[R]) {
mx1[v] = mx1[L], cnt[v] = cnt[L] + cnt[R];
mx2[v] = max(mx2[L], mx2[R]); // strictly below the max
} else if (mx1[L] > mx1[R]) {
mx1[v] = mx1[L], cnt[v] = cnt[L];
mx2[v] = max(mx2[L], mx1[R]);
} else {
mx1[v] = mx1[R], cnt[v] = cnt[R];
mx2[v] = max(mx1[L], mx2[R]);
}
}
void build(int v, int l, int r) {
if (l == r) { sum[v] = mx1[v] = a[l]; mx2[v] = LLONG_MIN; cnt[v] = 1; return; }
int m = (l + r) / 2;
build(2 * v, l, m);
build(2 * v + 1, m + 1, r);
pull(v);
}
void capNode(int v, ll x) { // only the maxima drop to x
if (x >= mx1[v]) return;
sum[v] -= (mx1[v] - x) * cnt[v];
mx1[v] = x;
}
void push(int v) { capNode(2 * v, mx1[v]); capNode(2 * v + 1, mx1[v]); }
void update(int v, int l, int r, int ql, int qr, ll x) {
if (qr < l || r < ql || x >= mx1[v]) return; // nothing above x here
if (ql <= l && r <= qr && x > mx2[v]) { capNode(v, x); return; } // only maxima change
push(v);
int m = (l + r) / 2;
update(2 * v, l, m, ql, qr, x);
update(2 * v + 1, m + 1, r, ql, qr, x);
pull(v);
}
ll query(int v, int l, int r, int ql, int qr) {
if (qr < l || r < ql) return 0;
if (ql <= l && r <= qr) return sum[v];
push(v);
int m = (l + r) / 2;
return query(2 * v, l, m, ql, qr) + query(2 * v + 1, m + 1, r, ql, qr);
}
void cap(int l, int r, ll x) { update(1, 1, n, l, r, x); }
ll total(int l, int r) { return query(1, 1, n, l, r); }
ll best(int v, int l, int r, int ql, int qr) { // range maximum: mx1 is already there
if (qr < l || r < ql) return LLONG_MIN;
if (ql <= l && r <= qr) return mx1[v];
push(v);
int m = (l + r) / 2;
return max(best(2 * v, l, m, ql, qr), best(2 * v + 1, m + 1, r, ql, qr));
}
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
cin >> n >> q;
for (int i = 1; i <= n; i++) cin >> a[i];
build(1, 1, n);
while (q--) {
int type, l, r;
cin >> type >> l >> r;
if (type == 1) { ll x; cin >> x; cap(l, r, x); }
else if (type == 2) cout << best(1, 1, n, l, r) << "\n";
else cout << total(l, r) << "\n";
}
}
9
6
25
4
3. Longest run of equal values in [l, r], with point updates.
Solution
A node keeps its length, the run at its left end, the run at its right end, the best run inside, and its leftmost and rightmost values. If A's right value equals B's left value, the runs join in the middle.
#include <bits/stdc++.h>
using namespace std;
// Longest run of equal values inside [l, r], with point updates.
struct Node { int len, pre, suf, best, lv, rv; }; // run at the left end, at the right end, best inside
Node merge(const Node &A, const Node &B) {
if (A.len == 0) return B;
if (B.len == 0) return A;
Node C{A.len + B.len, A.pre, B.suf, max(A.best, B.best), A.lv, B.rv};
if (A.rv == B.lv) { // the runs touch in the middle
C.best = max(C.best, A.suf + B.pre);
if (A.pre == A.len) C.pre = A.len + B.pre;
if (B.suf == B.len) C.suf = B.len + A.suf;
}
return C;
}
int n, q, a[200001];
Node t[800004];
const Node EMPTY{0, 0, 0, 0, 0, 0};
Node leaf(int x) { return {1, 1, 1, 1, x, x}; }
void build(int v, int l, int r) {
if (l == r) { t[v] = leaf(a[l]); return; }
int m = (l + r) / 2;
build(2 * v, l, m); build(2 * v + 1, m + 1, r);
t[v] = merge(t[2 * v], t[2 * v + 1]);
}
void setVal(int v, int l, int r, int i, int x) {
if (l == r) { t[v] = leaf(x); return; }
int m = (l + r) / 2;
if (i <= m) setVal(2 * v, l, m, i, x); else setVal(2 * v + 1, m + 1, r, i, x);
t[v] = merge(t[2 * v], t[2 * v + 1]);
}
Node query(int v, int l, int r, int ql, int qr) {
if (qr < l || r < ql) return EMPTY;
if (ql <= l && r <= qr) return t[v];
int m = (l + r) / 2;
return merge(query(2 * v, l, m, ql, qr), query(2 * v + 1, m + 1, r, ql, qr));
}
int main() {
cin >> n >> q;
for (int i = 1; i <= n; i++) cin >> a[i];
build(1, 1, n);
while (q--) {
int type, x, y;
cin >> type >> x >> y;
if (type == 1) setVal(1, 1, n, x, y);
else cout << query(1, 1, n, x, y).best << "\n";
}
}
3
2
4
4. Count streaks with a positive total (the whole array, no updates).
Solution
With prefix sums p, the run (i, j] has a positive total exactly when p[j] > p[i]. Count pairs i < j with p[i] < p[j] using coordinate compression and a Fenwick tree (episode 63): O(n log n). Sample 3 -5 4 -1 2 has 9 such streaks.
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
// Count streaks (subarrays) with a positive total = pairs i < j with p[j] > p[i] (prefix sums).
int main() {
int n;
cin >> n;
vector<ll> p(n + 1, 0);
for (int i = 1; i <= n; i++) { ll x; cin >> x; p[i] = p[i - 1] + x; }
vector<ll> vals(p); // coordinate-compress the prefix sums
sort(vals.begin(), vals.end());
vals.erase(unique(vals.begin(), vals.end()), vals.end());
int m = vals.size();
vector<int> bit(m + 1, 0);
ll count = 0;
for (int j = 0; j <= n; j++) {
int id = lower_bound(vals.begin(), vals.end(), p[j]) - vals.begin(); // # of values < p[j]
for (int i = id; i > 0; i -= i & -i) count += bit[i]; // earlier prefixes smaller than p[j]
for (int i = id + 1; i <= m; i += i & -i) bit[i]++;
}
cout << count << "\n";
}
9
Quick quiz
Merge A = (sum 2, pre 3, suf 2, best 4) with B = (sum −1, pre 5, suf 1, best 5). What is the new best?
A) 5 · B) 7 · C) 9 · D) 4
Answer
B. max(4, 5, A.suf + B.pre = 2 + 5) = 7: the best run crosses the middle.
Interview questions
- Why can't range chmin be a normal lazy tag? The change of a block's sum depends on every value in it, not just on x and the length.
- What does a segment tree beats node store? Sum, maximum, strict second maximum, count of the maximum.
- When does the update stop at a node? When x ≥ max (nothing to do), or when the node is inside the range and second max < x < max (only the maxima change).
- Why must the second maximum be strict? Otherwise equal maxima block the stop rule and every update visits all of them.
- What is the complexity? Amortised O((n + q) log n) for chmin + sum (O((n + q) log² n) with range adds too).
- How do you design a mergeable node? Decide what information about a block lets you compute the same information for the concatenation of two blocks (e.g. sum, best prefix, best suffix, best).
- What should a query return outside the range? An identity element: merging with it changes nothing, and it can never "win".
Glossary
| Term | Meaning | Example |
|---|---|---|
| Range chmin | a[i] = min(a[i], x) for i in [l, r] | a price cap |
| Range chmax | a[i] = max(a[i], x) | homework 1 |
| Segment tree beats | A segment tree that stops when only the maxima change, otherwise goes deeper | J1 |
| Strict second maximum | The largest value strictly below the maximum | 7 in 9 9 7 |
| Count of the maximum | How many values equal the maximum | 2 for 9 9 7 |
| Amortised complexity | A bound on the total work over all operations | O((n + q) log n) |
| Potential argument | Counting a quantity that only decreases to bound total work | distinct values |
| pull | Recompute a node from its children | pull(v) |
| push | Pass a pending change to the children | cap to the parent max |
| Mergeable node | Information that two neighbouring blocks can combine in O(1) | sum, pre, suf, best |
| Prefix / suffix | A run starting at the left end / ending at the right end | pre, suf |
| Maximum subarray sum | The largest total of a non-empty run | best streak |
| Kadane's algorithm | O(n) maximum subarray scan | the slow J2 query |
| Identity element | A value that changes nothing when merged | EMPTY |
| Sentinel | A special "impossible" value | −4 · 10^18 |
| Stress test | Comparing a fast solution with a slow, surely-correct one on many random inputs | all 500 tests passed |
| Time Limit Exceeded (TLE) | Too slow | the non-strict second max |
| Wrong Answer (WA) | A wrong output | 0 |
| Fenwick tree | A compact tree for prefix sums | next episode |
Summary
- A range chmin is not a simple tag; segment tree beats stores max, strict second max and count.
- Stop when second max < x < max (
sum −= (max − x) · cnt); otherwise go deeper; push caps children to the parent max. - A non-strict second max is correct but TLE.
- Mergeable nodes carry exactly what a merge needs: sum, best prefix, best suffix, best.
- The empty node must never win (
0instead of-2otherwise).
Solutions in C++, Java and Python
Problem J1 · Price Cap
C++
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
int n, q, cnt[2000004]; // cnt[v] = how many equal mx1[v]
ll a[500001], sum[2000004], mx1[2000004], mx2[2000004]; // max, second max
void pull(int v) {
int L = 2 * v, R = 2 * v + 1;
sum[v] = sum[L] + sum[R];
if (mx1[L] == mx1[R]) {
mx1[v] = mx1[L], cnt[v] = cnt[L] + cnt[R];
mx2[v] = max(mx2[L], mx2[R]); // strictly below the max
} else if (mx1[L] > mx1[R]) {
mx1[v] = mx1[L], cnt[v] = cnt[L];
mx2[v] = max(mx2[L], mx1[R]);
} else {
mx1[v] = mx1[R], cnt[v] = cnt[R];
mx2[v] = max(mx1[L], mx2[R]);
}
}
void build(int v, int l, int r) {
if (l == r) { sum[v] = mx1[v] = a[l]; mx2[v] = LLONG_MIN; cnt[v] = 1; return; }
int m = (l + r) / 2;
build(2 * v, l, m);
build(2 * v + 1, m + 1, r);
pull(v);
}
void capNode(int v, ll x) { // only the maxima drop to x
if (x >= mx1[v]) return;
sum[v] -= (mx1[v] - x) * cnt[v];
mx1[v] = x;
}
void push(int v) { capNode(2 * v, mx1[v]); capNode(2 * v + 1, mx1[v]); }
void update(int v, int l, int r, int ql, int qr, ll x) {
if (qr < l || r < ql || x >= mx1[v]) return; // nothing above x here
if (ql <= l && r <= qr && x > mx2[v]) { capNode(v, x); return; } // only maxima change
push(v);
int m = (l + r) / 2;
update(2 * v, l, m, ql, qr, x);
update(2 * v + 1, m + 1, r, ql, qr, x);
pull(v);
}
ll query(int v, int l, int r, int ql, int qr) {
if (qr < l || r < ql) return 0;
if (ql <= l && r <= qr) return sum[v];
push(v);
int m = (l + r) / 2;
return query(2 * v, l, m, ql, qr) + query(2 * v + 1, m + 1, r, ql, qr);
}
void cap(int l, int r, ll x) { update(1, 1, n, l, r, x); }
ll total(int l, int r) { return query(1, 1, n, l, r); }
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
cin >> n >> q;
for (int i = 1; i <= n; i++) cin >> a[i];
build(1, 1, n);
while (q--) {
int type, l, r;
cin >> type >> l >> r;
if (type == 1) {
ll x;
cin >> x;
cap(l, r, x);
} else cout << total(l, r) << "\n";
}
}
Java
import java.util.*;
import java.io.*;
public class Main {
static int n;
static long[] sum, mx1, mx2; // max, strict second max
static int[] cnt; // how many equal the max
static void pull(int v) {
int L = 2 * v, R = 2 * v + 1;
sum[v] = sum[L] + sum[R];
if (mx1[L] == mx1[R]) { mx1[v] = mx1[L]; cnt[v] = cnt[L] + cnt[R]; mx2[v] = Math.max(mx2[L], mx2[R]); }
else if (mx1[L] > mx1[R]) { mx1[v] = mx1[L]; cnt[v] = cnt[L]; mx2[v] = Math.max(mx2[L], mx1[R]); }
else { mx1[v] = mx1[R]; cnt[v] = cnt[R]; mx2[v] = Math.max(mx1[L], mx2[R]); }
}
static void build(int v, int l, int r, long[] a) {
if (l == r) { sum[v] = mx1[v] = a[l]; mx2[v] = Long.MIN_VALUE; cnt[v] = 1; return; }
int m = (l + r) / 2;
build(2 * v, l, m, a); build(2 * v + 1, m + 1, r, a);
pull(v);
}
static void capNode(int v, long x) { // only the maxima drop to x
if (x >= mx1[v]) return;
sum[v] -= (mx1[v] - x) * cnt[v];
mx1[v] = x;
}
static void push(int v) { capNode(2 * v, mx1[v]); capNode(2 * v + 1, mx1[v]); }
static void update(int v, int l, int r, int ql, int qr, long x) {
if (qr < l || r < ql || x >= mx1[v]) return;
if (ql <= l && r <= qr && x > mx2[v]) { capNode(v, x); return; }
push(v);
int m = (l + r) / 2;
update(2 * v, l, m, ql, qr, x); update(2 * v + 1, m + 1, r, ql, qr, x);
pull(v);
}
static long query(int v, int l, int r, int ql, int qr) {
if (qr < l || r < ql) return 0;
if (ql <= l && r <= qr) return sum[v];
push(v);
int m = (l + r) / 2;
return query(2 * v, l, m, ql, qr) + query(2 * v + 1, m + 1, r, ql, qr);
}
public static void main(String[] args) throws IOException {
StreamTokenizer in = new StreamTokenizer(new BufferedInputStream(System.in));
in.nextToken(); n = (int) in.nval; in.nextToken(); int q = (int) in.nval;
long[] a = new long[n + 1];
for (int i = 1; i <= n; i++) { in.nextToken(); a[i] = (long) in.nval; }
sum = new long[4 * n + 4]; mx1 = new long[4 * n + 4]; mx2 = new long[4 * n + 4]; cnt = new int[4 * n + 4];
build(1, 1, n, a);
StringBuilder sb = new StringBuilder();
while (q-- > 0) {
in.nextToken(); int type = (int) in.nval;
in.nextToken(); int l = (int) in.nval; in.nextToken(); int r = (int) in.nval;
if (type == 1) { in.nextToken(); update(1, 1, n, l, r, (long) in.nval); }
else sb.append(query(1, 1, n, l, r)).append('\n');
}
System.out.print(sb);
}
}
32
25
8
Python (recursive; fine for small inputs)
import sys
NEG = float("-inf")
def main():
data = sys.stdin.buffer.read().split()
n, q = int(data[0]), int(data[1])
a = [0] + [int(x) for x in data[2:n + 2]]
size = 4 * n + 4
s, m1, m2, cnt = [0] * size, [0] * size, [NEG] * size, [0] * size
def pull(v):
L, R = 2 * v, 2 * v + 1
s[v] = s[L] + s[R]
if m1[L] == m1[R]:
m1[v], cnt[v], m2[v] = m1[L], cnt[L] + cnt[R], max(m2[L], m2[R])
elif m1[L] > m1[R]:
m1[v], cnt[v], m2[v] = m1[L], cnt[L], max(m2[L], m1[R])
else:
m1[v], cnt[v], m2[v] = m1[R], cnt[R], max(m1[L], m2[R])
def build(v, l, r):
if l == r:
s[v] = m1[v] = a[l]; m2[v] = NEG; cnt[v] = 1; return
m = (l + r) // 2
build(2 * v, l, m); build(2 * v + 1, m + 1, r); pull(v)
def cap_node(v, x): # only the maxima drop to x
if x < m1[v]:
s[v] -= (m1[v] - x) * cnt[v]; m1[v] = x
def push(v):
cap_node(2 * v, m1[v]); cap_node(2 * v + 1, m1[v])
def update(v, l, r, ql, qr, x):
if qr < l or r < ql or x >= m1[v]: return
if ql <= l and r <= qr and x > m2[v]:
cap_node(v, x); return
push(v)
m = (l + r) // 2
update(2 * v, l, m, ql, qr, x); update(2 * v + 1, m + 1, r, ql, qr, x); pull(v)
def query(v, l, r, ql, qr):
if qr < l or r < ql: return 0
if ql <= l and r <= qr: return s[v]
push(v)
m = (l + r) // 2
return query(2 * v, l, m, ql, qr) + query(2 * v + 1, m + 1, r, ql, qr)
build(1, 1, n)
out, p = [], n + 2
for _ in range(q):
t, l, r = int(data[p]), int(data[p + 1]), int(data[p + 2]); p += 3
if t == 1:
update(1, 1, n, l, r, int(data[p])); p += 1
else:
out.append(query(1, 1, n, l, r))
print("\n".join(map(str, out)))
main()
32
25
8
Problem J2 · Best Streak
C++
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
struct Node { ll sum, pre, suf, best; }; // best prefix, best suffix, best inside
Node merge(const Node &A, const Node &B) {
return {A.sum + B.sum,
max(A.pre, A.sum + B.pre),
max(B.suf, B.sum + A.suf),
max({A.best, B.best, A.suf + B.pre})}; // or a streak across the middle
}
int n, q;
ll a[200001];
Node t[800004];
const Node EMPTY = {0, -(ll)4e18, -(ll)4e18, -(ll)4e18}; // nothing: never the best
Node leaf(ll x) { return {x, x, x, x}; }
void build(int v, int l, int r) {
if (l == r) { t[v] = leaf(a[l]); return; }
int m = (l + r) / 2;
build(2 * v, l, m);
build(2 * v + 1, m + 1, r);
t[v] = merge(t[2 * v], t[2 * v + 1]);
}
void setDay(int v, int l, int r, int i, ll x) {
if (l == r) { t[v] = leaf(x); return; }
int m = (l + r) / 2;
if (i <= m) setDay(2 * v, l, m, i, x);
else setDay(2 * v + 1, m + 1, r, i, x);
t[v] = merge(t[2 * v], t[2 * v + 1]);
}
Node query(int v, int l, int r, int ql, int qr) {
if (qr < l || r < ql) return EMPTY;
if (ql <= l && r <= qr) return t[v];
int m = (l + r) / 2;
return merge(query(2 * v, l, m, ql, qr), query(2 * v + 1, m + 1, r, ql, qr));
}
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
cin >> n >> q;
for (int i = 1; i <= n; i++) cin >> a[i];
build(1, 1, n);
while (q--) {
int type, x, y;
cin >> type >> x >> y;
if (type == 1) setDay(1, 1, n, x, y);
else cout << query(1, 1, n, x, y).best << "\n";
}
}
Java
import java.util.*;
import java.io.*;
public class Main {
static final long NEG = -4_000_000_000_000_000_000L;
static long[][] t; // t[v] = {sum, pre, suf, best}
static int n;
static long[] merge(long[] A, long[] B) {
return new long[]{A[0] + B[0], Math.max(A[1], A[0] + B[1]), Math.max(B[2], B[0] + A[2]),
Math.max(Math.max(A[3], B[3]), A[2] + B[1])};
}
static final long[] EMPTY = {0, NEG, NEG, NEG}; // nothing: never the best
static long[] leaf(long x) { return new long[]{x, x, x, x}; }
static void build(int v, int l, int r, long[] a) {
if (l == r) { t[v] = leaf(a[l]); return; }
int m = (l + r) / 2;
build(2 * v, l, m, a); build(2 * v + 1, m + 1, r, a);
t[v] = merge(t[2 * v], t[2 * v + 1]);
}
static void setDay(int v, int l, int r, int i, long x) {
if (l == r) { t[v] = leaf(x); return; }
int m = (l + r) / 2;
if (i <= m) setDay(2 * v, l, m, i, x); else setDay(2 * v + 1, m + 1, r, i, x);
t[v] = merge(t[2 * v], t[2 * v + 1]);
}
static long[] query(int v, int l, int r, int ql, int qr) {
if (qr < l || r < ql) return EMPTY;
if (ql <= l && r <= qr) return t[v];
int m = (l + r) / 2;
return merge(query(2 * v, l, m, ql, qr), query(2 * v + 1, m + 1, r, ql, qr));
}
public static void main(String[] args) throws IOException {
StreamTokenizer in = new StreamTokenizer(new BufferedInputStream(System.in));
in.nextToken(); n = (int) in.nval; in.nextToken(); int q = (int) in.nval;
long[] a = new long[n + 1];
for (int i = 1; i <= n; i++) { in.nextToken(); a[i] = (long) in.nval; }
t = new long[4 * n + 4][];
build(1, 1, n, a);
StringBuilder sb = new StringBuilder();
while (q-- > 0) {
in.nextToken(); int type = (int) in.nval;
in.nextToken(); int x = (int) in.nval; in.nextToken(); long y = (long) in.nval;
if (type == 1) setDay(1, 1, n, x, y);
else sb.append(query(1, 1, n, x, (int) y)[3]).append('\n');
}
System.out.print(sb);
}
}
5
4
9
2
Python
import sys
NEG = float("-inf")
EMPTY = (0, NEG, NEG, NEG) # nothing: never the best
def merge(A, B):
return (A[0] + B[0], max(A[1], A[0] + B[1]), max(B[2], B[0] + A[2]), max(A[3], B[3], A[2] + B[1]))
def main():
data = sys.stdin.buffer.read().split()
n, q = int(data[0]), int(data[1])
a = [0] + [int(x) for x in data[2:n + 2]]
t = [None] * (4 * n + 4)
def build(v, l, r):
if l == r:
t[v] = (a[l],) * 4; return
m = (l + r) // 2
build(2 * v, l, m); build(2 * v + 1, m + 1, r)
t[v] = merge(t[2 * v], t[2 * v + 1])
def set_day(v, l, r, i, x):
if l == r:
t[v] = (x,) * 4; return
m = (l + r) // 2
if i <= m: set_day(2 * v, l, m, i, x)
else: set_day(2 * v + 1, m + 1, r, i, x)
t[v] = merge(t[2 * v], t[2 * v + 1])
def query(v, l, r, ql, qr):
if qr < l or r < ql: return EMPTY
if ql <= l and r <= qr: return t[v]
m = (l + r) // 2
return merge(query(2 * v, l, m, ql, qr), query(2 * v + 1, m + 1, r, ql, qr))
build(1, 1, n)
out, p = [], n + 2
for _ in range(q):
ty, x, y = int(data[p]), int(data[p + 1]), int(data[p + 2]); p += 3
if ty == 1: set_day(1, 1, n, x, y)
else: out.append(query(1, 1, n, x, y)[3])
print("\n".join(map(str, out)))
main()
5
4
9
2