PROBLEM LINK:
Practice
Contest: Division 1
Contest: Division 2
Contest: Division 3
Contest: Division 4
Author: raysh07
Tester: sushil2006
Editorialist: iceknight1093
DIFFICULTY:
Easy
PREREQUISITES:
Sorting, segment trees
PROBLEM:
You’re given an array A.
Define f(A) as the minimum possible value of \text{sum}(A) after performing the following operation finitely many times:
- Choose an index i such that 1 \lt i \lt N, and replace A_i with A_{i-1} + A_{i+1} - A_i.
There are Q point updates to the array.
After each update, report f(A).
EXPLANATION:
We begin by computing f(A) for a fixed array A.
It’s not immediately clear what the minimum sum can possibly be, or what sort of operation would be optimal.
In situations like this, it’s often helpful to try and work with some transformation of the array instead - the most common ones are either prefix sums or adjacent differences.
In this case, looking at adjacent differences is helpful.
Let’s define D_i = A_i - A_{i-1} to be the i-th adjacent difference of the array elements.
We also say D_1 = A_1 to obtain a well-defined array of length N.
Now, suppose we perform the given operation at index i.
Observe that only the values D_i and D_{i+1} will change.
In particular,
- The new value of D_i will be
(A_{i-1} + A_{i+1} - A_i) - A_{i-1} = A_{i+1} - A_i - The new value of D_{i+1} will be
A_{i+1} - (A_{i-1} + A_{i+1} - A_i) = A_i - A_{i-1}
Observe that this is equivalent to just swapping the differences at these two indices!
So, since we’re allowed to swap any two adjacent differences via our operation (except for D_1, which must remain in place because we cannot modify A_1), we can basically freely permute the values D_2, \ldots, D_N among positions 2, \ldots, N.
Choosing a permutation of differences will just give us back the original array by simply taking prefix sums, i.e. we have
The next question is, how do we rearrange the differences in order to minimize the sum of A?
Well, if R denotes a rearrangement of the differences, then observe that the overall sum of elements will equal
because R_1 will appear in the expression for every element, R_2 will appear in every element except the first, and so on.
We thus have the multipliers N-1, N-2, \ldots, 1 available to us, and we can freely decide which ones must be matched to each of the values D_2, \ldots, D_N; because D_1 has the fixed multiplier of N.
By the rearrangement inequality, the optimal matching in order to minimize the overall sum is to pair the largest element with the smallest multiplier, the second-larger element with the second-smallest multiplier, and so on.
Thus, essentially we want to sort the values D_2, \ldots, D_N in ascending order among positions 2, \ldots, N.
This gives us a simple way to compute f(A) in \mathcal{O}(N\log N) time: compute all adjacent differences, sort D_2, \ldots, D_N in ascending order to positions 2, \ldots, N, and then after sorting, compute
Now that computing f(A) is known, let’s figure out how to deal with point updates.
Suppose the value at index i is changed.
Then, observe that only the values D_i and D_{i+1} will change.
So, we need to be able to handle point updates to the array D, while also knowing the value of \sum_{i=1}^N (N+1-i)\cdot D_i after sorting D_2, \ldots, D_N.
One way to handle this quickly is to use a segment tree.
First, let’s create a list of all possible differences that we’ll ever see.
Note that there are (at most) N+2Q such values: the initial N differences, and then each update creates (at most) two more (updating A_N creates only one new difference, not two - hence at most.)
Let S be a sorted list that stores all these precomputed differences.
For each of the N+2Q possible differences, remember its position in S.
Now, build a segment tree over the array S.
In each node of the segment tree, store the following information:
- The sum of all active differences in this range.
- The count of all active differences in this range.
- The weighted sum of all active differences in this range - where the largest active difference gets weight 1, the second larger active difference gets weight 2, and so on.
Here, we call a difference active if it currently occurs as one of the elements D_2, \ldots, D_{N-1}.
So, there are exactly N-1 active differences at any point of time.
Note that our eventual goal is to compute the weighted sum corresponding to the whole range; since just that plus N times D_1 will give us our final answer.
To complete the segment tree, we need to know how to merge adjacent nodes.
That can be done as follows:
- The sum of active differences and count of active differences of both nodes can just be added up to obtain the corresponding value for the merged node.
- For the weighted sum: observe that the contribution of all active differences in the right node will remain the same; while the contribution of all active differences in the left side will increase by exactly the number of active differences in the right.
So, the total increase in weighted sum (after adding together the weighted sums) equals the product of the sum of the left and the count of the right.
This is why we needed to maintain those two quantities in the first place.
With merges handled, we are basically done.
Each update to the array de-activates two elements of S and actives two other elements - so we do up to 4 point updates.
Since we’ve already defined the states and merges, each update takes \mathcal{O}(\log(N+Q)) time and so is clearly fast enough - so we’re done.
TIME COMPLEXITY:
\mathcal{O}((N+Q)\log (N+Q)) per testcase.
CODE:
Tester'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 = 1e5 + 5;
const int inf1 = int(1e9) + 5;
const ll inf2 = ll(1e18) + 5;
template<typename T>
struct segtree {
// https://codeforces.com/blog/entry/18051
/*=======================================================*/
struct data {
ll val,sum,cnt;
};
data neutral = {0,0,0};
data merge(data &left, data &right) {
data curr;
curr.val = left.val + right.val + left.sum*right.cnt;
curr.sum = left.sum + right.sum;
curr.cnt = left.cnt + right.cnt;
return curr;
}
void create(int i, T v) {
}
void modify(int i, T v) {
tr[i].val = v.ff;
tr[i].sum = v.ff;
tr[i].cnt = v.ss;
}
/*=======================================================*/
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];
auto b = a;
vector<ll> diffs;
diffs.pb(-inf2);
for(int i = 2; i <= n; ++i){
diffs.pb(a[i]-a[i-1]);
}
vector<pll> queries(q+5);
rep1(id,q){
ll i,x; cin >> i >> x;
queries[id] = {i,x};
b[i] = x;
if(i > 1){
diffs.pb(b[i]-b[i-1]);
}
if(i < n){
diffs.pb(b[i+1]-b[i]);
}
}
sort(all(diffs));
map<ll,ll> mp;
ll siz = sz(diffs)-1;
rep1(i,siz){
if(diffs[i] != diffs[i-1]){
mp[diffs[i]] = i;
}
}
segtree<pll> st(siz+5);
vector<ll> idx(n+5);
for(int i = 2; i <= n; ++i){
ll d = a[i]-a[i-1];
idx[i] = mp[d]++;
st.pupd(idx[i],{d,1});
}
rep1(id,q){
auto [i,x] = queries[id];
// remove contribution
if(i > 1){
st.pupd(idx[i],{0,0});
}
if(i < n){
st.pupd(idx[i+1],{0,0});
}
// add contribution
a[i] = x;
if(i > 1){
ll d = a[i]-a[i-1];
idx[i] = mp[d]++;
st.pupd(idx[i],{d,1});
}
if(i < n){
ll d = a[i+1]-a[i];
idx[i+1] = mp[d]++;
st.pupd(idx[i+1],{d,1});
}
// get ans
ll ans = a[1]*n + st.query(1,siz).val;
cout << ans << endl;
}
}
int main()
{
fastio;
int t = 1;
cin >> t;
rep1(i, t) {
solve(i);
}
cerr << "RUN SUCCESSFUL" << endl;
return 0;
}