PROBLEM LINK
Setter, Editorialist: dedsec_29
PREREQUISITES
Segment tree
PROBLEM
Handle point updates, and maximum subarray sum queries in the given range after performing an arbitrary number of cyclic right shifts.
QUICK EXPLANATION
Use a segment tree that supports maximum subsegment sum range queries and point updates, to find the maximum circular subarray sum in a given range.
EXPLANATION
If we take c=0, the answer is just the maximum subarray sum in that range. If we have a better answer which can be obtained by taking c\neq0, then the elements of that shifted subarray will wrap around the unshifted array.
For example, consider the following array:
A = [2, -2, -2, 2]
With c = 0, max subarray sum is 2. But a better choice, in this case, would be to choose ans = A[0] + A[3] = 4, which “wraps” around the array. We can do so because we can choose some arbitrary c for which the wrapped around sequence turns into a contiguous sequence after shifts (c=1 in this case).
In other words, the problem is the same as finding the maximum subarray sum in a cyclic array in a given range.
What can be the maximum sum of such wrapped around sequence? We can observe that the sum consists of a prefix of A and a suffix of A. We need to maximize prefix_sum[i] + suffix_sum[j] such that i < j. This means that we should leave out a contiguous part from the middle, and take the left and right parts (left being the prefix, right being the suffix).
Now, what should we leave in the middle to maximize the answer? Of course, we should leave the part corresponding to the minimum subarray sum.
Therefore, ans = max(maximum subarray sum, sum - minimum subarray sum)
where sum is the sum of subarray corresponding to the given range.
It only remains to show how to query maximum subarray sum and minimum subarray sum in a given range [L,R] with point updates. This is a standard problem that can be solved using segment tree, which uses the idea of maintaining and combining answer at each nodes along with the best prefix sum, suffix sum, and the sum of the segment.
Note: The mentioned standard problem uses terms subarray and subsegment interchangably.
Once we know how to use segment tree to find subsegments with maximal sum, we can apply the same knowledge to find subsegments with minimal sums. We construct a segment tree on the array obtained after negating every element of the array, i.e. A[i] = -A[i] \hspace{1cm} \forall 1\leq i \leq n
To find minimum subsegment sum in given range, we can query for the maximum subsegment sum on this segment tree instead. Suppose the res is the result we get making this query, then we can update answer as:
ans = max(maximum subarray sum, sum - res)
Setter's solution
#include <bits/stdc++.h>
using namespace std;
//#pragma GCC optimize "trapv"
#define int long long
struct segment_tree {
struct data {
int sum, pref, suff, ans;
};
vector<int> a;
vector<data> t;
segment_tree(vector<int>& arr) {
int n = arr.size();
a = arr;
t.resize(4*n+1);
}
data combine(data l,data r) {
data res;
res.sum = l.sum + r.sum;
res.pref = max(l.pref, l.sum + r.pref);
res.suff = max(r.suff, r.sum + l.suff);
res.ans = max(max(l.ans, r.ans), l.suff + r.pref);
return res;
}
data make_data(int val) {
data res;
res.sum = val;
res.pref = res.suff = res.ans = max(val, 0ll);
return res;
}
void build(int v,int tl,int tr) {
if (tl == tr)
t[v] = make_data(a[tl]);
else {
int tm = (tl + tr) / 2;
build(v*2, tl, tm);
build(v*2+1, tm+1, tr);
t[v] = combine(t[v*2], t[v*2+1]);
}
}
void update(int v, int tl, int tr, int pos, int new_val) {
if (tl == tr) {
t[v] = make_data(new_val);
} else {
int tm = (tl + tr) / 2;
if (pos <= tm)
update(v*2, tl, tm, pos, new_val);
else
update(v*2+1, tm+1, tr, pos, new_val);
t[v] = combine(t[v*2], t[v*2+1]);
}
}
data query(int v,int tl,int tr,int l,int r) {
if (l > r)
return make_data(0);
if (l == tl && r == tr)
return t[v];
int tm = (tl + tr) / 2;
return combine(query(v*2, tl, tm, l, min(r, tm)), query(v*2+1, tm+1, tr, max(l, tm+1), r));
}
};
void solve() {
int n,q; cin >> n >> q;
vector<int> arr(n);
for (int i = 0; i < n; i++) cin >> arr[i];
segment_tree t = segment_tree(arr);
t.build(1,0,n-1);
for (int& i: arr)
i = -i;
segment_tree inv = segment_tree(arr);
inv.build(1,0,n-1);
while (q--) {
int type; cin >> type;
if (type == 1) {
int l,r; cin >> l >> r; l--, r--;
auto data = t.query(1,0,n-1,l,r);
int ans1 = data.ans;
if (r-l+1 <= 2)
cout << ans1 << "\n";
else {
int sum = data.sum;
int ans2 = inv.query(1,0,n-1,l+1,r-1).ans;
cout << max({0ll, ans1, sum + ans2}) << "\n";
}
}
else {
int idx, val; cin >> idx >> val; --idx;
t.update(1,0,n-1,idx,val);
inv.update(1,0,n-1,idx,-val);
}
}
}
int32_t main() {
ios_base::sync_with_stdio(false);
cin.tie(NULL);
solve();
return 0;
}