DELELE - Editorial

editorial
, , ,
1

PROBLEM LINK:

Practice
Contest: Division 1
Contest: Division 2
Contest: Division 3
Contest: Division 4

Author: raysh07
Tester: sushil2006
Editorialist: iceknight1093

DIFFICULTY:

TBD

PREREQUISITES:

Prefix sums, binary search

PROBLEM:

An array A is deletable if it can be reduced to size \le 2 via the following operation:

  • Choose an index i (1 \lt i \lt |A|) such that A_{i-1} + A_{i+1} \ge A_i
  • Add X to A_{i-1} and Y to A_{i+1} such that X+Y=A_i to either of its neighbors.
  • Delete A_i from the array.

Given an array A, count the number of deletable subarrays.

Here, N \le 2\cdot 10^5

EXPLANATION:

From the easy version, we know that an array is deletable if and only if it has length \ge 3, and the maximum element occurring at an index other than 1 or N doesn’t exceed half the sum of the array.

To solve this version with higher constraints, we’ll need a couple more observations.

First, rather than trying to count deletable subarrays, we’ll try to count non-deletable subarrays.

That is, subarrays which contain at least one element in their middle that’s larger than half the sum.

Observe that if a subarray contains such an element, then it can only contain exactly one such element; since multiple of them would exceed the sum of the subarray itself.

Thus, rather than work with subarrays directly, we can fix the “bad” element, and count subarrays which it makes not deletable.

Now suppose we fix the element at index i, and want to count subarrays with it as the “bad” element.

Observe then that A_i must definitely be the unique maximum element of the subarray.
So, if we define:

  • L_i \lt i as the largest index such that A_{L_i} \ge A_i.
    • If no such index exists, we say L_i = 0.
  • R_i \gt i as the smallest index such that A_{R_i} \ge A_i.
    • If no such index exists, we say R_i = N+1.

Then any valid subarray [l, r] must satisfy L_i \lt l \lt i \lt r \lt R_i.

Note that l \lt i \lt r is because we don’t want A_i to be at the endpoint of the subarray - it must be in the middle.

Among such subarrays, we want to count those whose sum is \lt 2\cdot A_i.

One easy way to do this is: fix the value of l in the range [L_i+1, i-1], and then note that the valid values of r will form a contiguous range starting at i+1, since increasing r only increases the sum.
Finding the last valid r can be done easily by binary searching over it, with the help of prefix sums to compute range sums quickly.

However, this is too slow: we do \mathcal{O}((i - L_i)\log N work with a fixed i, and the sum of i - L_i is not necessarily bounded nicely.
For example, with the array [1, 2, 3, \ldots, N], we have L_i = 0 for all i so the sum of i - L_i is quadratic.

One attempt to get around this would be to try and fix the right endpoint instead, and binary search to find the valid range of l instead.
This, however, runs into the same problem - for example on [N, N-1, \ldots, 3, 2, 1].

A further fix to this, is to just use whichever segment is smaller.
That is, if i - L_i \le R_i - i then iterate over the left endpoint; otherwise iterate over the right endpoint.

This simple-looking optimization in fact improves our time complexity a lot!
In particular, it can be shown that we iterate through \mathcal{O}(N\log N) positions this way across all i.

Proof

Define d_i = \min(i - L_i, R_i - i).
Our goal is to prove that \sum d_i is \mathcal{O}(N\log N).

Let’s fix a parameter r, and look at all i for which d_i \ge r.

The key observation is that no two such positions can be at a distance of \lt r from each other.
This is because if they were, then one of them would have its nearest larger (or equal) element be at a distance \lt r as well, contradicting d_i \ge r.

But then this tells us that the number of indices with d_i \ge r is bounded above by about \frac{N}{r}.

Let c_r denote the number of i such that d_i \ge r.

Then, \sum_i d_i = \sum_{r\ge 1} c_r, because each d_i contributes 1 each to c_1, c_2, \ldots, c_{d_i}.

However, we saw c_r \le \frac{N}{r}, so \sum_i d_i is bounded by \sum_{r\ge 1} \frac{N}{r}.
By the harmonic lemma the last summation is \mathcal{O}(N\log N), proving our bound.

This gives us a solution in \mathcal{O}(N\log^2 N), which is good enough.

TIME COMPLEXITY:

\mathcal{O}(N\log^2 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;

void solve(int test_case){
    ll n; cin >> n;
    vector<ll> a(n+5);
    rep1(i,n) cin >> a[i];

    vector<ll> lx(n+5,1), rx(n+5,n);

    {
        stack<ll> stk;
        rep1(i,n){
            while(!stk.empty() and a[i] >= a[stk.top()]){
                rx[stk.top()] = i-1;
                stk.pop();
            }

            stk.push(i);
        }
    }

    {
        stack<ll> stk;
        rev(i,n,1){
            while(!stk.empty() and a[i] > a[stk.top()]){
                lx[stk.top()] = i+1;
                stk.pop();
            }

            stk.push(i);
        }
    }

    vector<ll> pref(n+5);
    rep1(i,n) pref[i] = pref[i-1]+a[i];

    ll bad = 0;
    
    rep1(i,n){
        ll l = lx[i], r = rx[i];
        ll len_left = i-l+1, len_right = r-i+1;

        if(len_left < len_right){
            for(int lp = l; lp < i; ++lp){
                ll curr_sum = pref[i-1]-pref[lp-1];
                if(curr_sum < a[i]){
                    ll at_most = a[i]-1-curr_sum;

                    // p[r]-p[i] <= at_most
                    // p[r] <= at_most+p[i]

                    at_most += pref[i];
                    ll big_cnt = upper_bound(pref.begin()+i+1,pref.begin()+r+1,at_most)-(pref.begin()+i+1);

                    bad += big_cnt;
                }
            }
        }
        else{
            for(int rp = i+1; rp <= r; ++rp){
                ll curr_sum = pref[rp]-pref[i];
                if(curr_sum < a[i]){
                    ll at_most = a[i]-1-curr_sum;

                    // p[i-1]-p[l] <= at_most
                    // p[l] >= p[i-1]-at_most
                    ll at_least = pref[i-1]-at_most;
                    auto first_at_least = lower_bound(pref.begin()+l-1,pref.begin()+i-1,at_least);
                    ll at_least_cnt = (pref.begin()+i-1)-first_at_least;

                    bad += at_least_cnt;
                }
            }
        }
    }
    
    ll ans = n*(n+1)/2-bad;
    cout << ans << endl;
}

int main()
{
    fastio;

    int t = 1;
    cin >> t;

    rep1(i, t) {
        solve(i);
    }

    cerr << "RUN SUCCESSFUL" << endl;

    return 0;
}