Author: Jeevan Jyot Singh
Tester: Hriday
Editorialist: Nishank Suresh

2155

# PREREQUISITES:

Multisets (or a similar data structure)

# PROBLEM:

You are given an array A consisting of N integers, on which you need to process Q point-set updates.

After each update, find the minimum number of moves to make the array non-decreasing using the following operation:

• Pick 1 \leq L \leq R \leq N, and add i to A_{L+i-1} for each 1 \leq i \leq R-L+1.

# EXPLANATION:

We’ll look at a way to solve a single query first, and then later how to process many of them.

The first subtask has \leq 5 queries, so solving each one in \mathcal{O}(N) or similar is good enough.

This gives us a subproblem: given an array, what is the minimum number of aforementioned moves required to make it non-decreasing?

It turns out the answer is quite simple: it is simply the maximum value of (A_i - A_{i+1}) across all 1 \leq i \lt N (and 0 if this maximum is negative).

Proof

Let’s look at the difference array of A. This is the array D of size N-1 such that D_i = A_{i+1} - A_i.
Note that A is non-decreasing if and only if every element of D is \geq 0, so our aim is to achieve this.

Consider making a move on the subarray [L, R]. You can see that this changes D as follows:

• Each of D_{L-1}, D_L, D_{L+1}, \ldots, D_{R-1} increases by exactly 1.
• D_R (if it exists) decreases by R-L+1.

Note that our objective is to make all of D non-negative, so the first part is great but the second is not desirable since we’d like to not decrease elements if possible.
However, by simply choosing R = N when performing the operation, we can get rid of this demerit entirely since D_N doesn’t exist!

So, our operations essentially add 1 to some suffix of D. We might as well add 1 to all of D when doing this, so the minimum number of moves to make something in D non-negative is simply the magnitude of the most negative element of D.

That is, if the smallest element of D is m, then the answer is 0 (if m \geq 0) and -m otherwise.

The smallest value of D is the smallest value of A_i - A_{i-1}, which in turn is (the negative of) the largest value of A_{i+1} - A_i, and hence our initial claim holds.

So, we now know how to solve a single query in \mathcal{O}(N). This solves the first subtask.

\mathcal{O}(N) per query won’t be fast enough here, we need to do better.

Recall that our solution depends only on the adjacent differences of A. Changing a single element affects at most two of these differences.

So, simply maintain a (multi)set of current differences. When performing an update at position i, remove the differences corresponding to (i-1, i) and (i, i+1) from the multiset, update the element, then add the new differences for those pairs back in. The answer is then the largest element of the multiset. Each update is processed in \mathcal{O}(\log N).

# TIME COMPLEXITY

\mathcal{O}((N+Q)\log N) per test case.

# CODE:

Editorialist's code (C++)
#include "bits/stdc++.h"
// # GCC optimize("O3,unroll-loops")
// #pragma GCC target("avx2,bmi,bmi2,lzcnt,popcnt")
using namespace std;
using ll = long long int;
mt19937_64 rng(chrono::high_resolution_clock::now().time_since_epoch().count());

int main()
{
ios::sync_with_stdio(false); cin.tie(0);

int t; cin >> t;
while (t--) {
int n, q; cin >> n >> q;
vector<int> a(n);
for (int &x : a) cin >> x;
multiset<int> ms;
for (int i = 0; i+1 < n; ++i) ms.insert(a[i] - a[i+1]);
auto erase = [&] (int pos) {
if (pos) ms.erase(ms.find(a[pos-1] - a[pos]));
if (pos+1 < n) ms.erase(ms.find(a[pos] - a[pos+1]));
};
auto insert = [&] (int pos) {
if (pos) ms.insert(a[pos-1] - a[pos]);
if (pos+1 < n) ms.insert(a[pos] - a[pos+1]);
};
auto upd = [&] (int pos, int val) {
erase(pos);
a[pos] = val;
insert(pos);
};
while (q--) {
int pos, val; cin >> pos >> val; --pos;
upd(pos, val);
cout << max(0, *ms.rbegin()) << '\n';
}
}
}

3 Likes

I solved it using Segment Tree (similar to Range Minimum Query).
I maintained a list B of adjacent differences of A.
And with Segment Tree I was able to find max of B in log(N).
But it seems that it can be done using multisets.
My code:

#include <bits/stdc++.h>
#define ll long long
#define llinf LLONG_MAX
#define llminf LLONG_MIN
#define inf INT_MAX
#define minf INT_MIN
unsigned long int M = 1000000007;

using namespace std;

int t[400001];

void build(int a[], int v, int tl, int tr) {
if (tl == tr) {
t[v] = a[tl];
} else {
int tm = (tl + tr) / 2;
build(a, v*2, tl, tm);
build(a, v*2+1, tm+1, tr);
t[v] = min(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] = 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] = min(t[v*2],t[v*2+1]);
}
}

int main() {
ios_base::sync_with_stdio(false);
cin.tie(NULL);
cout.tie(NULL);
int T,n,q;
cin >> T;
while (T--) {
cin >> n >> q;
int v[n];
for (int i = 0;i<n;i++) {
cin >> v[i];
}
int res[n-1];
for (int i = 0;i<n-1;i++) {
res[i]=v[i+1]-v[i];
}

build(res,1,0,n-2);
for (int i = 0;i<q;i++) {
int ind,value;
cin >> ind >> value;
ind--;
if (ind == 0) {
res[0]=v[1]-value;
v[0]=value;
update(1,0,n-2,0,res[0]);
}
else if (ind == n-1) {
res[n-2]=value-v[n-2];
v[n-1]=value;
update(1,0,n-2,n-2,res[n-2]);
}
else {
res[ind-1]=value-v[ind-1];
res[ind]=v[ind+1]-value;
v[ind]=value;
update(1,0,n-2,ind-1,res[ind-1]);
update(1,0,n-2,ind,res[ind]);
}
if (t[1]>=0) {
cout << 0 << endl;
}
else {
cout << abs(t[1]) << endl;
}
}
}
}

2 Likes

this is quite an intuitive solution.

Hey can we include sortedcontainers in python? I see it is available in other coding platforms and in problems like these a sorted list is pretty similar to a multiset in C++.

Can’t we just keep a goodness variable and keep updating it for the given point for each query, why do we need a multiset or a SGTree?

I tried to implement the same approach explained above, but I am getting WA for few cases.
Please explain what kind of a test-case I am missing.

I used only map for this question.
Below is the link of detailed explanation with comments of my approach.
https://www.codechef.com/viewsolution/75173497

2 Likes

suppose for some case number of operations needed at each index is as follows:
[1, 0, 3, 2, 2, 0] before update answer is 3(max value).

After update array of number of operations becomes [1, 0, 1, 2, 2, 0] now as max values has changed, how will you know the current max values which is 2 by only keeping one variable.

1 Like

Oh my bad! Such a dumb mind…I got this…tysm!!

Thanks a lot bro, super helpful!!

1 Like