PROBLEM LINK:
Practice
Contest: Division 1
Contest: Division 2
Contest: Division 3
Contest: Division 4
Author: iceknight1093
Tester: sushil2006
Editorialist: iceknight1093
DIFFICULTY:
Medium
PREREQUISITES:
Segment trees, stacks
PROBLEM:
There are N boxes in a row, each with a distinct value in [1, N].
Initially, all boxes are red.
You can color some of the boxes blue, then do the following:
- Choose two blue boxes. Move the later blue box to just before the earlier one.
Find the minimum number of boxes that need to be colored blue, so that it’s possible to sort the values on the boxes.
Sum this up across all contiguous subarrays.
EXPLANATION:
From the easy version, the solution for a single sequence P is as follows:
- We want to maximize the number of red boxes.
- A box can be red only if it’s a prefix maximum.
- Two adjacent boxes can be red only if they contain consecutive values.
(Of course, both must be prefix maximums as well.) - The first box can be red only if its value is 1.
- These conditions are sufficient, after which a simple left-to-right greedy algorithm will tell us which boxes can be left red.
This now needs to be adapted to summing up across all contiguous segments.
When applied to an arbitrary segment of boxes, most of the above criteria remain the same.
The only differences are:
- The first box in a range can be red only if it contains the minimum value in the range (and not specifically 1); and
- the notion of “consecutive values” changes slightly.
In particular, if we’re looking at the subarray [L, R], and the prefix maximums P_i and P_{i+1} within it - then these two values are “consecutive” if and only if there doesn’t exist any element P_i \lt x \lt P_{i+1} such that x appears in P[L, R].
One important observation here is that because P_i is a prefix maximum of this subarray, if such a value does exist, it must appear only after index i+1.
This is because everything in P[L, i-1] is strictly smaller than P_i.
We now try to compute the sum of answers across all segments.
To simplify things, let’s compute the sum of counts of boxes that remain red - this can be subtracted from the total at the end.
As for counting red boxes, we’ll use contribution.
That is, fix a box i, and we’ll try to count the number of ranges [L, R] for which it will remain red, as per our greedy algorithm.
First, this box must definitely be a prefix maximum.
So, if lt_i denotes the index of the nearest element to the left that’s \gt P_i, then certainly any range [L, R] must satisfy lt_i \lt L \le i \le R for P_i to be a prefix maximum at all.
(All the values of lt_i can be found using a monotonic stack, this is standard.)
Using this, we can easily find all ranges that have P_i as a prefix maximum.
(Note that for L = i we also need to ensure that P_i is the minimum element of the range; which gives an upper bound on R. This can also be found using a stack and some precomputation.)
However, our greedy algorithm doesn’t always mark P_i red - so let’s try to identify cases where it doesn’t.
We call index i bad for the range [L, R], if P_i and P_{i+1} are both prefix maximums of the range, but they’re not consecutive elements within the range.
Observe that the only possible time when P_i is not added to the answer is the following:
- Let j \le i be the smallest index such that j, j+1, \ldots, i are all bad with respect to [L, R].
- Then, P_i is not added to the answer iff (i-j) is odd.
Now, P_i being bad for [L, R] actually depends only on R.
In particular, if we define rt_i to be the smallest index \gt i+1 that contains a value between P_i and P_{i+1} (of course, under the assumption that P_i \lt P_{i+1}), then P_i can be bad if and only if R \ge rt_i.
Finding all the values of rt_i is an exercise in using a segment tree, and left to the reader. It is doable in \mathcal{O}(N\log N).
Using this information, we can first count all subarrays for which P_i is not bad. In these, it will definitely be taken by our greedy algorithm.
Then, we have to consider the subarrays where it’s bad.
The contribution of P_i across all ranges where it’s bad can be found using inclusion-exclusion as follows:
- Add all ranges such that i is bad.
- Subtract all ranges such that i and i-1 are bad.
- Add all ranges such that i, i-1, i-2 are bad.
- Subtract all ranges such that i, i-1, i-2, i-3 are bad.
\vdots
Now, in general, for j \le i, finding the number of ranges where all of j, \ldots, i are bad is not hard:
- P_j must be a prefix maximum, which limits the left endpoint to being larger than lt_j.
This automatically makes everything else a prefix maximum.
(We’re working under the assumption that P_j \lt\ldots\lt P_i) - All the indices j, \ldots, i must be bad.
This gives us several lower bounds on the right endpoint of the range (since each index has its own lower bound), and we’re limited by the largest of them.
Specifically, we must have R \ge \max(rt_j, \ldots, rt_i).
Thus, there are (j - lt_j) \cdot (N - \max(rt_j, \ldots, rt_i) + 1) ranges here, with a multiplier of either +1 or -1 depending on the parity of i-j.
Specifically the multiplier is (-1)^{i-j}.
We would like to sum this up across all j \le i that belong to the same increasing segment.
This can be done in subquadratic time by conditioning on the value of \max(rt_j, \ldots, rt_i) which fixes one term of the product and gives ranges of i, j.
The remaining term depends purely on j, so range sums built on (j - lt_j) will allow us to compute the appropriate contributions.
To deal with the (-1)^{i-j} multiplier, handle even and odd j separately.
Note that you will also have to handle separately the cases of L = j, since that gives an additional constraint on j being the overall min so the same algebra doesn’t quite work.
However, it’s not so different and can be dealt with similarly.
TIME COMPLEXITY:
\mathcal{O}(N\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 a;
};
data neutral = {inf2};
data merge(data &left, data &right) {
data curr;
curr.a = min(left.a,right.a);
return curr;
}
void create(int i, T v) {
}
void modify(int i, T v) {
tr[i].a = 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; cin >> n;
vector<ll> a(n+5);
rep1(i,n) cin >> a[i];
// find range on left for which max
vector<ll> lx_max_range(n+5,1);
{
stack<ll> stk;
rev(i,n,1){
while(!stk.empty() and a[i] > a[stk.top()]){
lx_max_range[stk.top()] = i+1;
stk.pop();
}
stk.push(i);
}
}
// find the range on the right for which val is min
vector<ll> rx_min_range(n+5,n);
{
stack<ll> stk;
rep1(i,n){
while(!stk.empty() and a[i] < a[stk.top()]){
rx_min_range[stk.top()] = i-1;
stk.pop();
}
stk.push(i);
}
}
// for every adjacent pair where a[i] < a[i+1], find the first position j >= i+2 whose val is in between (a[i],a[i+1])
// reverse sweepline on indices, maintain min segtree
segtree<ll> st(n+5);
vector<ll> first_between(n+5,n+1);
rev(i,n,1){
if(i < n and a[i] < a[i+1]){
ll val = st.query(a[i]+1,a[i+1]-1).a;
first_between[i] = min(val,n+1);
}
st.pupd(a[i],i);
}
// goal: find sum of untouched over all ranges
// fix a sub-block [i..j] and add contrib
ll tot_sum = 0;
deque<array<ll,3>> dq; // (i,val,suffix_sum)
dq.pb({n+1,inf2,0});
auto get_sum = [&](ll i, ll s){
// find first pos with val >= s
ll lo = 0, hi = sz(dq)-1;
ll first_pos = -1;
while(lo <= hi){
ll mid = (lo+hi)>>1;
if(dq[mid][1] >= s){
first_pos = mid;
hi = mid-1;
}
else{
lo = mid+1;
}
}
ll mxr = dq[first_pos][0];
ll sub_sum = dq[0][2]-dq[first_pos][2];
ll add_sum = 0;
ll len = mxr-i;
if(len&1){
if(mxr&1) add_sum = -s;
else add_sum = s;
}
// spl case: i = j
ll c = 1;
if(i&1) c = -1;
ll singular = c*max(s-i,0ll);;
ll res = add_sum-sub_sum+singular;
return res;
};
rev(i,n,1){
// insert i into prefix max dq
ll vali = first_between[i];
while(vali > dq[0][1]){
dq.pop_front();
}
{
auto [j,valj,suffj] = dq[0];
ll len = j-i;
if(len&1){
// if even, suffj will remain same (-1 and +1 will cancel out)
// otherwise, suffj will change
if(j&1){
// addl guy is -
suffj -= vali;
}
else{
// addl guy is +
suffj += vali;
}
}
dq.push_front({i,vali,suffj});
}
ll lx = lx_max_range[i]; // [lx..i] --> i is max val, so any left endpoint starting here is fine
ll rx = rx_min_range[i]; // [i..rx] --> i is min val, so any right endpoint inside this range is fine
ll l_ways = i-lx; // lx <= left < i
ll c = 1;
if(i&1) c = -1;
ll ways1 = l_ways*get_sum(i,n+1);
ll ways2 = get_sum(i,rx+1);
ll ways = ways1+ways2;
tot_sum += ways*c;
}
// find sum of all lengths, to find sum of touched over all subarrays
ll tot_len = 0;
rep1(len,n){
tot_len += len*(n-len+1);
}
ll ans = tot_len-tot_sum;
cout << ans << endl;
}
int main()
{
fastio;
int t = 1;
cin >> t;
rep1(i, t) {
solve(i);
}
cerr << "RUN SUCCESSFUL" << endl;
return 0;
}