PROBLEM LINK:
Practice
Contest: Division 1
Contest: Division 2
Contest: Division 3
Contest: Division 4
Author: prnv10
Tester: iceknight1093
Editorialist: iceknight1093
DIFFICULTY:
Medium
PREREQUISITES:
Dynamic programming, segment trees
PROBLEM:
You’re given two arrays A and B, both of length N.
Support Q queries and updates:
- Given X, p, q, set A_X = p and B_X = q.
- Given L and R, find the maximum possible sum obtainable by choosing one subarray from A[L, R] and one subarray from B[L, R], such that the subarrays intersect.
EXPLANATION:
To solve a single query (which was the easy version), our solution was to fix the index of the intersection and then compute the best possible subarray sum in A and B independently; and maximize this over all choices of the intersection index.
However, it’s unclear how to adapt this to point updates and range queries easily.
Instead, we look at a different solution.
Let’s understand the structure of a valid solution for a fixed A and B.
Suppose we pick the range [l_1, r_1] for A and [l_2, r_2] for B, and l_1 \le l_2 without loss of generality.
Then,
- Indices \lt l_1 and indices \gt \max(r_1, r_2) contribute nothing.
- Indices in [l_1, l_2) have a contribution of A_i.
- Indices in [l_2, \min(r_1, r_2)] have a contribution of A_i + B_i.
- Indices in (\min(r_1, r_2), \max(r_1, r_2)] have a contribution of either only A_i or only B_i, depending on whether r_1 or r_2 is larger.
Looking at this left-to-right, we can think of breaking the array into several ‘states’, where each state tells us which of A_i and/or B_i is being added to the sum for the current index.
This gives rise to a dynamic programming solution along the lines of:
Let dp(i, \text{state}) denote the best possible sum if we’ve processed the first i elements, and are currently at \text{state}.
For transitions, we can look at dp(i-1, \text{previous state}) across all states for i-1 that are ‘compatible’ with the current state (for example, we cannot jump from choosing only A_{i-1} to choosing only B_i), and update the value of dp(i, \text{state}) appropriately.
Further, we need to ensure that we go through the state of “choose both A_i and B_i” at least once, to satisfy the intersection criterion.
With this in mind, it can be seen that 7 states suffice:
- States 0, 1, 2 denoting choosing nothing, choosing only A_i, choosing only B_i.
These are for the part before the intersection. - State 3 denoting choosing both A_i and B_i.
- States 4, 5, 6 again denoting choosing nothing, choosing only A_i, choosing only B_i.
These are the the part after the intersection.
We then start with some state \le 3 and must end with some state \ge 3, which can be enforced by ensuring that no state \lt 3 can transition to a state \gt 3.
For example, from state 1 (only take A_i, before the intersection) we can only transition to states 1 or 3 (remain only A_i, or take both A_i and B_i).
This gives an answer to a single array in linear time (though perhaps with not the greatest constant factor).
One nice thing about the above dp formulation is that because it works left-to-right, it lends itself nicely to range queries using a segment tree.
Specifically, suppose we build a segment tree over the array, and want to query for the range [L, R].
The bottleneck in the query is having to combine two adjacent segments into a larger one.
So, say we want to combine the segments [l_1, r_1] and [r_1+1, r_2] into [l_1, r_2] while querying.
Observe that we then only need to know two things: the state of index r_1, and the state of index r_1+1; since the transitions operate on adjacent indices.
Thus, for each node in the segment tree, we need to care about the state of its leftmost element and its rightmost element.
So, for each node of the segment tree, let’s store a 7\times 7 array dp[\text{state}_L][\text{state}_R] denoting the answer for this segment if the leftmost element is at \text{state}_L and the rightmost is at \text{state}_R.
When combining segments, we need to compute dp[\text{state}_L][\text{state}_R] for the combined segment.
This can be done as follows:
- Fix \text{state}_L for the left node’s left border and \text{state}_R for the right node’s right border.
- Then fix the left node’s right border and the right node’s left border, and if they’re compatible, update dp[\text{state}_L][\text{state}_R] with the combined value.
At a glance, this appears to be quite slow: each query has \mathcal{O}(\log N) node merges, and each merge seems to take around 7^4 operations.
However, it’s possible to greatly improve the constant factor by noting that for any given state, it can only transition to states not smaller than it.
So, the total number of transitions we need to make is bounded by the number of 4-tuples (a, b, c, d) such that 0 \le a \le b \le c\le d \lt 7, which equals 210.
In practice the number is even smaller since not all these tuples are valid (especially for the middle, where c must be a valid transition from b). This brings the constant to about 150.
So, a single query can be answered in \mathcal{O}(C\log N) time, where C can be made 150.
It’s easy to see that point updates can be handled in the exact same complexity too, using the segment tree.
Since N, Q \le 1.5\cdot 10^5 and the time limit is 6 seconds, this is fast enough to pass.
(150 is about what one can expect from \mathcal{O}(\log^2 N) or \mathcal{O}(\sqrt N) so the running time of this is comparable to \mathcal{O}(\log^3 N) or \mathcal{O}(\sqrt N \log N) per query/update.)
TIME COMPLEXITY:
\mathcal{O}((N + Q)\cdot (150\cdot \log N)) per testcase.
CODE:
Editorialist's code (C++)
// #include <bits/allocator.h>
// #pragma GCC optimize("O3,unroll-loops")
// #pragma GCC target("avx2,bmi,bmi2,lzcnt,popcnt")
#include "bits/stdc++.h"
using namespace std;
using ll = long long int;
mt19937_64 RNG(chrono::high_resolution_clock::now().time_since_epoch().count());
/**
* Point-update Segment Tree
* Source: kactl
* Description: Iterative point-update segment tree, ranges are half-open i.e [L, R).
* f is any associative function.
* Time: O(logn) update/query
*/
const int SZ = 7;
array<array<ll, SZ>, SZ> unit;
template<class T>
struct SegTree {
vector<vector<int>> transitions = {
{0, 1, 2, 3},
{1, 3},
{2, 3},
{3, 4, 5, 6},
{4, 6},
{5, 6},
{6}
};
T f(T a, T b) {
if (a == unit) return b;
if (b == unit) return a;
T res = unit;
for (int i = 0; i < SZ; ++i) for (int j = i; j < SZ; ++j) {
for (int x : transitions[j]) for (int y = x; y < SZ; ++y) {
res[i][y] = max(res[i][y], a[i][j] + b[x][y]);
}
}
return res;
}
T create(int x, int y) {
T res = unit;
res[0][0] = res[6][6] = 0;
res[1][1] = res[4][4] = x;
res[2][2] = res[5][5] = y;
res[3][3] = x+y;
return res;
}
vector<T> s; int n;
SegTree(int _n = 0, T def = unit) : s(2*_n, def), n(_n) {}
void update(int pos, int x, int y) {
pos += n;
s[pos] = create(x, y);
while (pos /= 2) {
s[pos] = f(s[pos * 2], s[pos * 2 + 1]);
}
}
T query(int b, int e) {
T ra = unit, rb = unit;
for (b += n, e += n; b < e; b /= 2, e /= 2) {
if (b % 2) ra = f(ra, s[b++]);
if (e % 2) rb = f(s[--e], rb);
}
return f(ra, rb);
}
};
int main()
{
ios::sync_with_stdio(false); cin.tie(0);
const ll inf = -1e18;
for (int i = 0; i < SZ; ++i) for (int j = 0; j < SZ; ++j)
unit[i][j] = inf;
int t; cin >> t;
while (t--) {
int n, q; cin >> n >> q;
vector a(n, 0), b(n, 0);
for (int &x : a) cin >> x;
for (int &x : b) cin >> x;
vector<array<int, 4>> queries(q);
for (auto &[type, x, y, z] : queries) {
cin >> type >> x >> y;
if (type == 1) cin >> z;
}
SegTree<array<array<ll, SZ>, SZ>> seg(n);
vector<ll> ans(q, inf);
for (int i = 0; i < n; ++i) {
seg.update(i, a[i], b[i]);
}
int idx = 0;
for (auto [type, x, y, z] : queries) {
if (type == 1) {
seg.update(--x, y, z);
}
else {
auto res = seg.query(x-1, y);
for (int i = 0; i <= 3; ++i) for (int j = 3; j < SZ; ++j)
ans[idx] = max(ans[idx], res[i][j]);
}
++idx;
}
for (auto x : ans) {
if (x > inf) cout << x << '\n';
}
}
}
