PROBLEM LINK:
Practice
Contest: Division 1
Contest: Division 2
Contest: Division 3
Contest: Division 4
Author: raysh07
Tester: sushil2006
Editorialist: iceknight1093
DIFFICULTY:
Easy
PREREQUISITES:
Segment trees
PROBLEM:
Given an array A, answer Q queries on it.
Each query gives you L and R, and asks for the maximum possible alternating sum of a subsequence of [A_L, \ldots, A_R].
EXPLANATION:
Given that we have to answer range queries, it’s natural to try and use a segment tree.
To be able to do this, we need to know two pieces of information:
- What data to store in each node of the segment tree.
- How to merge this data when merging two nodes.
For the first step: we eventually want to know the maximum alternating sum of a subsequence, so of course that’s something that must be stored.
For ease of notation, let \text{altsum}(S) denote the alternating sum of the sequence S - so we’re currently storing the maximum value of \text{altsum}(S) in each node of the segment tree.
Now, let’s look at merging.
When we merge two nodes representing ranges [L, M] and [M+1, R] into the range [L, R], any subsequence of [L, R] can be broken up into a subsequence in [L, M] followed by a subsequence in [M+1, R].
Suppose we pick the subsequence S_1 in [L, M] and the subsequence S_2 in [M+1, R], and let S = S_1S_2 denote the result of merging them into a larger subsequence.
Then, it can be seen that:
- If S_1 has even length, we have \text{altsum}(S) = \text{altsum}(S_1) + \text{altsum}(S_2).
- If S_1 has odd length instead, we have \text{altsum}(S) = \text{altsum}(S_1) - \text{altsum}(S_2).
This is because the signs of the elements in S_2 will end up being flipped because of parity.
This tells us that to obtain the maximum possible value of \text{altsum}(S) in [L, R], we have the following options:
- Choose an even-length subsequence S_1 from the left side that has the maximum possible value of \text{altsum}(S_1).
Combine this with the maximum possible value of \text{altsum}(S_2) across all choices of S_2 on the right side. - Choose an odd-length subsequence S_1 from the left side that has the maximum possible value of \text{altsum}(S_1).
Combine this with the maximum possible value of (-\text{altsum}(S_2)) across all choices of S_2 on the right side.
This, in turn, tells us exactly what information we care about: for each parity (even/odd), we want to know both the maximum possible alternating sum, as well as the maximum possible negated alternating sum.
This makes 4 pieces of information for each node.
Suppose we maintain this information for each node.
It’s now not hard to merge the information from two adjacent nodes - the length parity of the merged subsequence can be obtained from the base length parities, and the information about whether the sum is negated or not allows us to reconstruct the actual sum (and then later negate it if needed.)
The transitions can be manually typed out with casework if you want to, but it’s much nicer to just let indexing do the work.
For instance, in each node store ans[x][y] where
- x = 0 or 1 denoting the parity of the subsequence.
- y = 0 or 1 denoting whether it’s storing the maximum alternating sum, or maximum negated alternating sum.
Then, when merging state (x_1, y_1) from the left and (x_2, y_2) from the right, say with values v_1, v_2 respectively,
- The parity of the merged state is given by (x_1 + x_2) \bmod 2
- The alternating sum contribution of the left side is either v_1 or -v_1 depending on whether y_1 = 0 or 1, respectively.
- The alternating sum contribution of the right side is either v_2 or -v_2 depending on whether x_1 = y_2 or not (because each of x_1 and y_2 being 1 requires a negation in the sum; so if both are true they’ll just cancel out).
- After knowing the alternating sum, update the resulting state appropriately.
For exact details on the transitions, you may check the attached code.
Once the node data and transitions are set, answering a query (L, R) is trivial.
Simply query the segment tree to get the result corresponding to this range in \mathcal{O}(\log N) time, and output the answer (which will be the maximum of the even-length and odd-length answers.)
TIME COMPLEXITY:
\mathcal{O}((N + Q)\log N) per testcase.
CODE:
Editorialist's code (C++)
// #include <bits/allocator.h>
// #pragma GCC optimize("Ofast,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());
const ll inf = 1e18;
using T = array<array<ll, 2>, 2>; // [parity][negated or not]
T unit = {-inf, -inf, -inf, -inf};
struct SegTree {
T f(T a, T b) {
if (a == unit) return b;
if (b == unit) return a;
T res = unit;
for (int i : {0, 1}) for (int j : {0, 1}) {
for (int p : {0, 1}) for (int q : {0, 1}) {
int par = (i ^ p); // parity of merged subsequence
// j=1 -> left side is negated
// i=1 or q=1 -> right side is negated
// sm stores the actual (not negated) alternating sum of combining these two parts
ll sm = (1 - 2*j)*a[i][j] + (1 - 2*i)*(1 - 2*q)*b[p][q];
res[par][0] = max(res[par][0], sm); // update with actual sum
res[par][1] = max(res[par][1], -sm); // update with negated sum
}
}
return res;
}
vector<T> s; int n;
SegTree(int _n = 0, T def = unit) : s(2*_n, def), n(_n) {}
void update(int pos, T val) {
for (s[pos += n] = val; 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);
int n, q; cin >> n >> q;
vector a(n, 0);
for (int &x : a) cin >> x;
SegTree seg(n);
for (int i = 0; i < n; ++i) {
T val = { {0, 0, -a[i], a[i]} };
seg.update(i, val);
}
while (q--) {
int l, r; cin >> l >> r;
auto res = seg.query(l-1, r);
cout << max(res[0][0], res[1][0]) << '\n';
}
}