Almost sorted interval - Hacker Rank Solution

Shik loves sorted intervals. But currently he does not have enough time to sort all the numbers. So he decided to use Almost sorted intervals. An Almost sorted interval is a consecutive subsequence in a sequence which satisfies the following property:

1. The first number is the smallest.
2. The last number is the largest.

Please help him count the number of almost sorted intervals in this permutation.

Note: Two intervals are different if at least one of the starting or ending indices are different.

Input Format
The first line contains an integer N.
The second line contains a permutation from 1 to N.

Output Format
Output the number of almost sorted intervals.

Constraints
1 ≤ N ≤ 106

Sample Input

5
3 1 2 5 4

Sample Output

8

Explanation
The subsequences [3], [1], [1 2], [1 2 5], [2], [2 5], [5], [4] are almost sorted intervals.

---------------------------------------------------------------------------------------------

Almost sorted interval - Hacker Rank Solution

1

For an interval aL, aL+1, ..., aR, if it is almost sorted, it must have:

1. aL < ak for all k ∈ [L+1, R]
2. aR > ak for all k ∈ [L, R-1]

Therefore, to count how many such intervals are there, we maintain the arrays below:

1. left[i]: the first position left to i and with value larger than a[i].
2. right[i]: the first position right to i and with value smaller than a[i].

Once we have the value, we can write down the formula of answer:

{ Number of (L, R) pairs such that right[L] > R and left[R] < L }

We can use a stack to find these two arrays in O(N) time.

2

Now imagine that we have a set of intervals, and enumerate the variable L from N downto 1. Inserting an intervalI=[left[R], R] whenever L equals to R, and remove the same interval when L reaches left[R]. For each L now we can ask "How many intervals are still in the set with R < right[L]?"

This can be done using Binary Index Tree or interval trees, and this problem can be solved in O(NlgN).

Problem Setter's code :

#include <cstdio>
#include <cstring>
#include <cmath>
#include <algorithm>
#include <vector>
using namespace std;

#define FOR(it, c) for(__typeof((c).begin()) it = (c).begin(); it != (c).end(); it++)
#define SZ(c) ((int)(c).size())
typedef long long LL;

const int N = 1000005;
int stack[N], top=0;
int left[N], right[N];
int a[N], n;
vector<int> r[N];
int bit[N];

void add(int x, int v) {
  while(x<=n) { bit[x] += v; x += (x&-x); }
}
int ask(int x) {
  int ret=0;
  while(x) { ret += bit[x]; x -= (x&-x); }
  return ret;
}

int main(void) {
  scanf("%d", &n);
  for(int i=1;i<=n;i++) scanf("%d", &a[i]);
  for(int i=1;i<=n;i++) {
    while(top>0 && a[i] > a[stack[top-1]]) --top;
    left[i] = top? stack[top-1] : 0;
    stack[top++] = i;
  }
  top = 0;
  for(int i=n;i>=1;i--) {
    while(top>0 && a[i] < a[stack[top-1]]) --top;
    right[i] = top? stack[top-1] : n+1;
    stack[top++] = i;
  }
  LL ans = 0;
  for(int L=n;L>=1;L--) {
    FOR(it, r[L]) add(*it, -1);
    add(L, 1);
    r[left[L]].push_back(L);
    ans += ask(right[L]-1);
  }
  printf("%lld\n", ans);
  return 0;
}

 Tested by gera1d

Problem Tester's code :

#ifdef ssu1
#define _GLIBCXX_DEBUG
#endif
#undef NDEBUG

#include <algorithm>
#include <functional>
#include <numeric>
#include <iostream>
#include <cstdio>
#include <cmath>
#include <cstdlib>
#include <ctime>
#include <cstring>
#include <cassert>
#include <vector>
#include <list>
#include <map>
#include <set>
#include <deque>
#include <queue>
#include <bitset>
#include <sstream>

using namespace std;

#define fore(i, l, r) for(int i = (l); i < (r); ++i)
#define forn(i, n) fore(i, 0, n)
#define fori(i, l, r) fore(i, l, (r) + 1)
#define sz(v) int((v).size())
#define all(v) (v).begin(), (v).end()
#define pb push_back
#define mp make_pair
#define X first
#define Y second

#if ( _WIN32 || __WIN32__ )
    #define LLD "%I64d"
#else
    #define LLD "%lld"
#endif

typedef long long li;
typedef long double ld;
typedef pair<int, int> pt;

template<typename T> T abs(T a) { return a < 0 ? -a : a; }
template<typename T> T sqr(T a) { return a*a; }

const int INF = (int)1e9;
const ld EPS = 1e-9;
const ld PI = 3.1415926535897932384626433832795;

int readInt(int l, int r){
    int x;
    if(scanf("%d", &x) != 1){
        fprintf(stderr, "Expected int in range [%d, %d], but haven't found!", l, r);
        throw;
    }
    if(!(l <= x && x <= r)){
        fprintf(stderr, "Expected int in range [%d, %d], but found %d!", l, r, x);
        throw;
    }
    return x;
}

const int NMAX = 1001000;
int t[NMAX], n;
vector<int> rv[NMAX];

inline int sum(int r){
    int ans = 0;
    for(; r >= 0; r = (r & (r + 1)) - 1)
        ans += t[r];
    return ans;
}

inline int sum(int l, int r){
    return sum(r) - sum(l - 1);
}

inline void upd(int i, int dx){
    for(; i < n; i = (i | (i + 1))){
        t[i] += dx;
    }
}

li solve(const vector<int>& a){
    vector<int> lf(sz(a)), rg(sz(a)), st;
    for(int i = sz(a) - 1; i >= 0; --i){
        while(!st.empty() && a[st.back()] >= a[i])
            st.pop_back();
        lf[i] = (st.empty() ? sz(a) : st.back());
        st.pb(i);
    }
    st.clear();
    forn(i, sz(a)){
        while(!st.empty() && a[st.back()] <= a[i])
            st.pop_back();
        rg[i] = (st.empty() ? -1 : st.back());
        st.pb(i);
    }

    forn(i, sz(rg)){
        rv[rg[i] + 1].pb(i);
    }

    li ans = 0;
    forn(i, sz(a)){
        forn(j, sz(rv[i])){
            upd(rv[i][j], 1);
        }
        ans += sum(i, lf[i] - 1);
    }
    return ans;
}

int main(){
#ifdef ssu1
    assert(freopen("input.txt", "rt", stdin));
    //assert(freopen("output.txt", "wt", stdout));
#endif

    n = readInt(1, 1000000);
    vector<int> a(n);
    forn(i, n){
        a[i] = readInt(1, n) - 1;
    }
    cout << solve(a) << endl;
    return 0;
}