PROBLEM LINK:
Practice
Contest: Division 1
Contest: Division 2
Contest: Division 3
Contest: Division 4
Author: iceknight1093
Preparation: sushil2006
Tester: sushil2006
Editorialist: iceknight1093
DIFFICULTY:
Easy
PREREQUISITES:
Segment trees/fenwick trees
PROBLEM:
For two arrays A and B, and integer K, \text{score}(A, B, K) is defined as follows:
- For each i in [1, N] in order:
- If A_i + K \lt B_i, swap A and B.
- Then, add A_i to the score.
You’re given the arrays A and B, and integer K.
Process Q point updates to the arrays. After each update, report \text{score}(A, B, K).
EXPLANATION:
The key idea here is of course figuring out how to compute the score of two arrays quickly, and keep it updated as the arrays change.
To do this, we’ll rewrite the score in a way that doesn’t require array swaps.
Let’s call an index i “important”, if |A_i - B_i| \gt K.
We can rewrite the score computation using important indices as follows:
- Let C denote the current array.
Initially, C = A. - Iterate i from 1 to N.
- If i is an important index,
- If A_i + K \lt B_i, set C = B
- Otherwise, we’ll have B_i + K \lt A_i, so set C = A.
- If i is not an important index, C doesn’t change.
- Finally, add C_i to the score.
In particular, observe that if i_1 and i_2 are two important indices with no other important index between them, for each i_1 \leq j \lt i_2, the decision of whether to add A_j or B_j to the score is dependent entirely on whether A_{i_1} \lt B_{i_1} or not (since i_1 is important, knowing whether A_{i_1} + K \lt B_{i_1} or the opposite inequality is true, is equivalent to knowing whether A_{i_1} \lt B_{i_1}.)
The above observation in fact allows us to handle point updates quite easily.
Suppose we update index i, and it’s now an important index.
Then,
- Let L \lt i be the previous important index, and R \gt i be the next important index.
- Then, for all L \leq j \lt R, we know that before this, the choice of whether to add A_j or B_j to the answer was determined entirely by whether A_L \gt B_L or not.
- In particular, the contribution of the segment [L, R-1] is either the sum A_L + A_{L+1} + \ldots + A_{R-1}, or the sum B_L + \ldots + B_{R-1}.
- In either case, it’s a range sum.
- Then, i is made important. This does two things:
- The contribution of the range [L, i-1] is determined by whether A_L \gt B_L or not.
This is a range sum of either the A or the B array,. - The contribution of the range [i, R-1] is determined by whether A_i \gt B_i or not.
Again, this is a range sum over the appropriate array.
- The contribution of the range [L, i-1] is determined by whether A_L \gt B_L or not.
If index i is updated and is no longer an important index, the change in answer can be computed similarly: look at the important indices just before/after i, and compute the contribution of the segment between them with a range sum.
To perform this quickly, we thus need to be able to do two things:
- Store the important indices in such a way that it’s possible to find the nearest one to the left/right quickly.
This is easily done using, for example, a set. - Compute the sums of certain ranges of A and B, with point updates.
This can be handled by a segment tree or fenwick tree.
For convenience of implementation, it’s nice to treat indices 0 and N+1 as being important, to avoid any casework when dealing with the next/previous indices.
TIME COMPLEXITY:
\mathcal{O}((N + Q)\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());
template<class T, T unit = T()>
struct SegTree {
T f(T a, T b) { return a+b; }
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 t; cin >> t;
while (t--) {
int n, k; cin >> n >> k;
vector a(n, 0), b(n, 0);
for (int &x : a) cin >> x;
for (int &x : b) cin >> x;
a.insert(a.begin(), 0);
b.insert(b.begin(), -k-1);
SegTree<ll> sa(n+1), sb(n+1);
for (int i = 0; i <= n; ++i) {
sa.update(i, a[i]);
sb.update(i, b[i]);
}
ll ans = accumulate(begin(a), end(a), 0ll);
set<int> parts = {0, n+1};
auto ins = [&] (int i) {
parts.insert(i);
auto it = parts.find(i);
int L = *prev(it), R = *next(it);
if (a[L] > b[L]) ans += sa.query(L, i) - sa.query(L, R);
else ans += sb.query(L, i) - sb.query(L, R);
if (a[i] > b[i]) ans += sa.query(i, R);
else ans += sb.query(i, R);
};
auto del = [&] (int i) {
auto it = parts.find(i);
int L = *prev(it), R = *next(it);
if (a[L] > b[L]) ans -= sa.query(L, i) - sa.query(L, R);
else ans -= sb.query(L, i) - sb.query(L, R);
if (a[i] > b[i]) ans -= sa.query(i, R);
else ans -= sb.query(i, R);
parts.erase(i);
};
for (int i = n; i >= 1; --i) {
if (abs(a[i] - b[i]) > k) {
ins(i);
}
}
int q; cin >> q;
while (q--) {
int type, i, x; cin >> type >> i >> x;
if (abs(a[i] - b[i]) > k) del(i);
if (type == 1) {
int j = *prev(parts.upper_bound(i));
if (a[j] > b[j]) ans += x - a[i];
a[i] = x, sa.update(i, x);
}
else {
int j = *prev(parts.upper_bound(i));
if (a[j] < b[j]) ans += x - b[i];
b[i] = x, sb.update(i, x);
}
if (abs(a[i] - b[i]) > k) ins(i);
cout << ans << '\n';
}
}
}