PROBLEM LINK:
Practice
Contest: Division 1
Contest: Division 2
Contest: Division 3
Contest: Division 4
Author: sushil2006
Tester: sushil2006
Editorialist: iceknight1093
DIFFICULTY:
Medium
PREREQUISITES:
Segment trees
PROBLEM:
For an array A of length N, f(A) is defined as follows:
- Start with X = 0 and S = 0.
- For each i = 1, 2, \ldots, N in order, you can:
- Do nothing, or
- Choose a positive integer y such that i\cdot y \le N, add |X - A_{i\cdot y}| to S, and then set X = A_{i\cdot y}.
- f(A) is the maximum possible final value of S.
You’re given an array A, as well as Q point updates to it.
Find f(A) after every update.
Importantly, the index for each point update is randomly generated.
EXPLANATION:
Let’s understand how to compute f(A) for a fixed array A.
We start with X_0 = 0, and then we’ll update the value of X several times as we go.
Suppose we update it to X_1, X_2, \ldots, X_k in order.
The score is then |X_0 - X_1| + |X_1 - X_2| + \ldots + |X_{k-1} - X_k|.
First, observe that there will always exist an optimal solution where we never “skip” the update to X at any point.
That is, for each i, we’ll always update X to some A_{i\cdot y}.
This is just because of the triangle inequality: |X-Z| + |Z-Y| \ge |X-Y| so it’s never worse to just insert some value in the middle of the X_i sequence.
This means we can always assume an update sequence of X_1, X_2, \ldots, X_N.
Now, let’s look at each X_i itself.
It’s not hard to see that it’s always ideal for X_i to be either as small or as large as possible - this can be proved by changing X_i by \pm 1 and looking at how it affects the overall sum of differences, depending on how it compares to its neighbors.
So, let’s define mn_i to be the minimum value among all indices that are multiples of i, and similarly mx_i to be the maximum value among all indices that are multiples of i.
Then, each X_i must be either mn_i or mx_i.
This now gives us a fairly straightforward \mathcal{O}(N) dynamic programming solution to compute f(A).
Let’s define dp_{i, 0} to be the maximum possible score if we’ve processed the first i elements and ended at mn_i, and similarly dp_{i, 1} to be the best score if we end at mx_i instead.
We then have dp_{i, 0} = \max(dp_{i-1, 0} + |mn_{i-1} - mn_i|, dp_{i-1, 1} + |mx_{i-1} - mn_i|).
dp_{i, 1} can be computed similarly.
The answer is \max(dp_{N, 0}, dp_{N, 1}).
Now let’s take one step further: what if there were point updates to the arrays mn and/or mx?
(Note that the actual problem we want to solve is point updates to A, but we’ll get to that later.)
Very often, DPs like this can be stored in a segment tree, as long as border information is maintained properly for merging purposes.
That is, suppose we build a segment tree, where for the segment [l, r] we store the result of the DP run on this segment.
To merge it with an adjacent segment, we only need to know two bits of information: whether we chose mn_l or mx_l, and whether we chose mn_r or mx_r.
Internal choices don’t matter for merging it with another segment.
So, for each segment, we can store four values: the best possible scores depending on whether we start/end with the minimum/maximum.
Merging adjacent segments can now be done easily too: there are 4 choices for the left segment and four choices for the right segment, for 16 choices total; the merged value and new state for each one can be computed quite easily.
This segment tree allows us to handle point updates to the mn and mx arrays in \mathcal{O}(16\log N) time.
Finally, let’s move to handling point updates to the array A.
Suppose we update A_i. Then, the values of mn_j and mx_j can change only for those j that are divisors of i - everything else will be unchanged.
So, using the same segment tree as earlier, we have a complexity of \mathcal{O}(d(i)\cdot 16\log N), where d(i) denotes the number of divisors of i.
Now, d(i) can be quite large - but this is where we bring in the constraint that the update indices are random.
Since update indices are random, the expected number of divisors we need to update equals the expected number of divisors of an integer in [1, N].
The total number of divisors of all integers in [1, N] is known to be \mathcal{O}(N\log N) via the harmonic summation, so the expected number of divisors of an integer in [1, N] is simply \mathcal{O}(\log N).
Thus, each point update to a random index of A has a complexity of \mathcal{O}(16\log^2 N) on average.
Since the time limit at 6 seconds is quite large, this should have no issue passing.
TIME COMPLEXITY:
Expected \mathcal{O}(N\log N + Q\cdot 16 \log^2 N) per testcase.
CODE:
Author's code (C++)
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace std;
using namespace __gnu_pbds;
template<typename T> using Tree = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;
typedef long long int ll;
typedef long double ld;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;
#define fastio ios_base::sync_with_stdio(false); cin.tie(NULL)
#define pb push_back
#define endl '\n'
#define sz(a) (int)a.size()
#define setbits(x) __builtin_popcountll(x)
#define ff first
#define ss second
#define conts continue
#define ceil2(x,y) ((x+y-1)/(y))
#define all(a) a.begin(), a.end()
#define rall(a) a.rbegin(), a.rend()
#define yes cout << "Yes" << endl
#define no cout << "No" << endl
#define rep(i,n) for(int i = 0; i < n; ++i)
#define rep1(i,n) for(int i = 1; i <= n; ++i)
#define rev(i,s,e) for(int i = s; i >= e; --i)
#define trav(i,a) for(auto &i : a)
template<typename T>
void amin(T &a, T b) {
a = min(a,b);
}
template<typename T>
void amax(T &a, T b) {
a = max(a,b);
}
#ifdef LOCAL
#include "debug.h"
#else
#define debug(...) 42
#endif
/*
*/
const int MOD = 1e9 + 7;
const int N = 2e5 + 5;
const int inf1 = int(1e9) + 5;
const ll inf2 = ll(1e18) + 5;
vector<int> divs[N];
void precalc(){
rep1(i,N-1){
for(int j = i; j < N; j += i){
divs[j].pb(i);
}
}
}
template<typename T>
struct segtree {
// https://codeforces.com/blog/entry/18051
/*=======================================================*/
struct data {
ll a[2][2];
bool active = false;
data(){
a[0][0] = a[0][1] = a[1][0] = a[1][1] = -inf2;
}
};
data neutral = data();
data merge(data &left, data &right) {
if(!left.active) return right;
if(!right.active) return left;
data curr;
rep(x,2){
rep(y,2){
rep(z,2){
amax(curr.a[x][z],left.a[x][y]+right.a[y^1][z]);
}
}
}
curr.active = true;
return curr;
}
void create(int i, T v) {
tr[i].a[0][0] = -2*v.ff;
tr[i].a[0][1] = tr[i].a[1][0] = 0;
tr[i].a[1][1] = 2*v.ss;
tr[i].active = true;
}
void modify(int i, T v) {
tr[i].a[0][0] = -2*v.ff;
tr[i].a[0][1] = tr[i].a[1][0] = 0;
tr[i].a[1][1] = 2*v.ss;
tr[i].active = true;
}
/*=======================================================*/
int n;
vector<data> tr;
segtree() {
}
segtree(int siz) {
init(siz);
}
void init(int siz) {
n = siz;
tr.assign(2 * n, neutral);
}
void build(vector<T> &a, int siz) {
rep(i, siz) create(i + n, a[i]);
rev(i, n - 1, 1) tr[i] = merge(tr[i << 1], tr[i << 1 | 1]);
}
void pupd(int i, T v) {
modify(i + n, v);
for (i = (i + n) >> 1; i; i >>= 1) tr[i] = merge(tr[i << 1], tr[i << 1 | 1]);
}
data query(int l, int r) {
data resl = neutral, resr = neutral;
for (l += n, r += n; l <= r; l >>= 1, r >>= 1) {
if (l & 1) resl = merge(resl, tr[l++]);
if (!(r & 1)) resr = merge(tr[r--], resr);
}
return merge(resl, resr);
}
};
void solve(int test_case){
ll n,q; cin >> n >> q;
vector<ll> a(n+5);
rep1(i,n) cin >> a[i];
multiset<int> ms[n+5];
rep1(i,n){
for(int j = i; j <= n; j += i){
ms[i].insert(a[j]);
}
}
segtree<pll> st(n+5);
vector<pll> b(n+5);
rep1(i,n){
ll mn = *ms[i].begin(), mx = *ms[i].rbegin();
b[i] = {mn,mx};
}
st.build(b,n+1);
while(q--){
ll i,x; cin >> i >> x;
trav(d,divs[i]){
ms[d].erase(ms[d].find(a[i]));
}
a[i] = x;
trav(d,divs[i]){
ms[d].insert(a[i]);
ll mn = *ms[d].begin(), mx = *ms[d].rbegin();
st.pupd(d,{mn,mx});
}
auto res = st.query(0,n);
ll f = a[n];
ll ans = max({res.a[0][0]+f,res.a[0][1]-f,res.a[1][0]+f,res.a[1][1]-f});
cout << ans << endl;
}
}
int main()
{
precalc();
fastio;
int t = 1;
cin >> t;
rep1(i, t) {
solve(i);
}
return 0;
}