PROBLEM LINK:
Practice
Contest: Division 1
Contest: Division 2
Contest: Division 3
Contest: Division 4
Author: Jeevan Jyot Singh
Tester: Hriday
Editorialist: Nishank Suresh
DIFFICULTY:
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.
Subtask 1
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.
Subtask 2
\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';
}
}
}