PROBLEM LINK:
Practice
Contest: Division 1
Contest: Division 2
Contest: Division 3
Contest: Division 4
Author: iceknight1093
Tester: sushil2006
Editorialist: iceknight1093
DIFFICULTY:
Easy-Medium
PREREQUISITES:
Segment trees
PROBLEM:
You’re given an array A of length N, and K.
You can choose upto K indices and increment the elements at each of their positions by 1.
There are Q point updates to A.
After each update, find the minimum number of operations needed to ensure that the elements of A are pairwise distinct.
EXPLANATION:
To recap solving for a single array,
- Sort the elements of A, so that A_1 \le\ldots\le A_N.
- Define a new array B such that:
- B_1 = A_1
- B_i = \max(B_{i-1}+1, A_i) for each 2 \le i \le N
- Let d_i = B_i - A_i, and define M = \max(d_i), S = \text{sum}(d_i).
- The answer was then \max(M, \text{ceil}\left(\frac{S}{K}\right)).
We need to process updates to the array A now.
Since the answer depends purely on M and S, we only really need to maintain their values.
Let’s figure out how to do that.
We’ll solve for each quantity separately.
In either case though, it’s more helpful to work with values rather than indices.
First, let’s look at maintaining M.
Define p_x to be the number of elements that are initially \le x, but need to have final values \gt x.
Observe that if we’re able to maintain the values of p_x, then we simply have M = \max_x(p_x).
This is because:
- If x \not\in A then p_x \le p_{x-1}.
- If x \in A then p_x will denote the largest amount that some copy of x must be incremented by.
Naturally, this lends itself to M = \max_x(p_x).
Writing M in terms of p_x is nice, because there’s a fairly straightforward recurrence to compute p_x:
where f_x denotes the frequency of x in the array.
This is because:
- If p_{x-1} = 0 then nothing carries over to \ge x.
So, one copy of x will remain at x, and the other f_x-1 of them must go to higher values.
Thus, p_x = f_x - 1 here (or p_x = 0, if f_x = 0.) - If p_{x-1} \gt 0 then one copy of a smaller value will end up at x, forcing all copies of x to go higher.
Thus, p_{x-1} + f_x - 1 higher values in total.
This recurrence should look rather familiar: it’s the same recurrence used to compute the maximum subarray sum!
Specifically, this is the expression used for the maximum subarray sum ending at x, where the value at x is f_x - 1.
Thus, M is simply the maximum subarray sum of the values f_x - 1.
Each update to the array changes at most two values of f_x.
Maintaining the maximum subarray sum with point updates is a standard exercise in using a segment tree - see CSES for example (with a solution here.)
So, M is able to be kept updated in \mathcal{O}(\log N) per update.
Next, let’s look at S.
Recall that S = \sum_{i=1}^N B_i - A_i.
This can be split up as \sum B_i - \sum A_i.
Keeping \sum A_i updated is trivial, so we focus on keeping \sum B_i updated.
To do this, we’ll treat each point update to the array as a two-stage process: first an element is deleted from the array, and then an element is inserted.
First, we look at insertion.
Suppose a copy of x is inserted into A.
Then, the change to B is simple: let y \ge x be the smallest integer that’s not already in B; then y gets inserted into B.
This is easy to verify by the greedy process of how B was constructed in the first place.
Finding such a y is also straightforward: for example, keep a set of all elements in the range [1, 3N] that are not present in B, and just binary search on this set.
We use the range [1, 3N] because 1 \le A_i \le 2N.
Thus, this part can be done in \mathcal{O}(\log N) time.
Finally, we need to deal with deletions.
Suppose x is deleted from A.
Then, it can be verified that the element y that needs to be removed from B, is the smallest value y \ge x such that p_y = 0.
Here, p_y is the value defined in the above section about maintaining M, i.e. p_y is the number of values that are \le y but end up \gt y.
This is because p_y = 0 represents the end of a “chain” of values that continually push upwards, and so only the end of that chain can be removed.
Thus, we need to find the first y\ge x such that p_y = 0.
Recall that p_y can be thought of as essentially the largest subarray sum of (frequency - 1) ending at y.
To find such a y quickly, we’ll use the help of prefix sums.
Define P_i = (f_i - 1) + P_{i-1} to be the prefix sum of the (f_i - 1) values till i.
Then, we have p_y = P_y - \min_{i \le y} P_i.
This is still rather hard to deal with, but we can make a further observation: till the end of the chain containing copies of x, all values \ge x will be taken care of by positions \ge x anyway - which means that in particular, their overall contribution of (f_i - 1) can’t be negative.
This means the minimum prefix sum of (f_i - 1) must come from a value that’s \lt x in the first place!
Thus, we’re really looking for the smallest y \ge x such that P_y - \min_{i \lt x} P_i \le 0.
This is now a quantity that a segment tree can help us find: by maintaining the prefix sums, both \min_{i \lt x} P_i and the first time after x that contains a value not larger than this value are findable quickly - in fact you can just modify the segment tree we’re already using to find them.
The query can be done in \mathcal{O}(\log^2 N) with direct binary search, or \mathcal{O}(\log N) by walking down the segment tree.
The constraints and time limit are lenient enough to let even (a reasonable implementation of) the former pass.
TIME COMPLEXITY:
\mathcal{O}((N+Q)\log N) 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 mnp,mxp,mxs,sum,mxsubsum;
};
data neutral = {0,0,0,0,0};
data merge(data &left, data &right) {
data curr;
curr.mnp = min(left.mnp,left.sum+right.mnp);
curr.mxp = max(left.mxp,left.sum+right.mxp);
curr.mxs = max(right.mxs,right.sum+left.mxs);
curr.sum = left.sum+right.sum;
curr.mxsubsum = max({left.mxsubsum,right.mxsubsum,left.mxs+right.mxp});
return curr;
}
void create(int i, T v) {
tr[i] = neutral;
auto &curr = tr[i];
curr.mnp = min(v,0ll);
curr.mxp = curr.mxp = curr.mxsubsum = max(v,0ll);
curr.sum = v;
}
void modify(int i, T v) {
tr[i] = neutral;
auto &curr = tr[i];
curr.mnp = min(v,0ll);
curr.mxp = curr.mxp = curr.mxsubsum = max(v,0ll);
curr.sum = v;
}
/*=======================================================*/
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,k,q; cin >> n >> k >> q;
vector<ll> a(n+5);
rep1(i,n) cin >> a[i];
vector<ll> cnt(3*n+5,-1);
rep1(i,n) cnt[a[i]]++;
set<pll> st;
ll sumb = 0;
auto set_ins = [&](ll x){
sumb += x;
auto it = st.lower_bound({x+1,-1});
ll l = x, r = x;
vector<pll> to_erase;
if(it != st.end() and it->ff == x+1){
r = it->ss;
to_erase.pb(*it);
}
if(it != st.begin() and prev(it)->ss == x-1){
l = prev(it)->ff;
to_erase.pb(*prev(it));
}
trav(px,to_erase){
st.erase(px);
}
st.insert({l,r});
};
auto ins = [&](ll x){
auto it = st.lower_bound({x+1,-1});
ll to_ins = x;
if(it != st.begin()){
auto [l,r] = *prev(it);
if(x <= r){
// need to insert r+1
to_ins = r+1;
}
}
set_ins(to_ins);
};
auto del = [&](ll x){
auto it = st.lower_bound({x+1,-1});
assert(it != st.begin());
it--;
auto [l,r] = *it;
assert(l <= x and x <= r);
st.erase(it);
if(l < x){
st.insert({l,x-1});
}
if(x < r){
st.insert({x+1,r});
}
sumb -= x;
};
rep1(i,n){
ins(a[i]);
}
segtree<ll> seg(3*n+5);
seg.build(cnt,3*n+1);
ll suma = 0;
rep1(i,n) suma += a[i];
ll I = 0;
while(q--){
ll i,v; cin >> i >> v;
ll x = a[i];
// find guy who will be deleted
ll mx_suff = seg.query(1,x).mxs;
// find first 0 position
ll first_pos = -1;
if(mx_suff == 0){
first_pos = x;
}
else{
ll lo = x+1, hi = 3*n+3;
while(lo <= hi){
ll mid = (lo+hi)>>1;
if(mx_suff+seg.query(x+1,mid).mnp <= 0){
first_pos = mid;
hi = mid-1;
}
else{
lo = mid+1;
}
}
}
// first_pos will be removed from b
del(first_pos);
cnt[x]--;
seg.pupd(x,cnt[x]);
suma -= x;
// insert v
a[i] = v;
ins(v);
suma += v;
cnt[v]++;
seg.pupd(v,cnt[v]);
ll m = seg.query(1,3*n+3).mxsubsum;
ll s = sumb-suma;
ll ans = max(ceil2(s,k),m);
cout << ans << endl;
}
}
int main()
{
fastio;
int t = 1;
cin >> t;
rep1(i, t) {
solve(i);
}
cerr << "RUN SUCCESSFUL" << endl;
return 0;
}