LFIVES | Editorial by yaseenmollik

All Editorials

# Lucky Fives
[**Problem](fafasfsa):**

**We are given a sequence a₁, a₂, . . . , aₙ of non-negative integers. For each query we will be given l ≤ r.**

**We have** **to calculate the number of triples (i, j, k), such that l< i < j < k < r and aₗ > aᵢ < aⱼ > aₖ < aᵣ**

**Constraints:**

1. **1 ≤ n ≤ 2000**
2. **1 ≤ Q ≤ 100000**
3. 0 ≤ aᵢ ≤ 10⁹

**[Solution](dasdasd):**

If we observe for a moment we will notice that this is a dynamic programming problem.

So, suppose we process the sequence from **left to right**. We can break down the triplet such that **aₗ > aᵢ < aⱼ > aₖ < a**ᵣ with **l <  i < j < k < r**, in parts:

- For a fixed **r**, the number of subsequences **aₗ > aᵢ < aⱼ > aₖ < aᵣ** is the number of subsequences **aₗ > aᵢ < aⱼ > aₖ** where  **aₖ < aᵣ .**
- For a fixed **k,** the number of subsequences **aₗ > aᵢ < aⱼ > aₖ** is the number of subsequences **aₗ > aᵢ < aⱼ** where  **aⱼ > aₖ .**
- For a fixed **j**, the number of subsequences **aₗ > aᵢ < aⱼ** is the number of subsequences **aₗ > aᵢ** where **aᵢ < aⱼ .**
- The number of subsequences **aₗ > aᵢ** is the number of integers between index **l** and **r** below **aₗ** . ****

So, can build up on the smaller parts in order to find the solution for each query. We can use a binary indexed tree (BIT) to keep counts for each part.

- **BIT_k** counts how many subsequences **aₗ > aᵢ < aⱼ > aₖ** where **aₖ** is the last element of this subsequences.
- **BIT_j** counts subsequences **aₗ > aᵢ < aⱼ**
- **BIT_i** counts subsequences **aₗ > aᵢ**

This three **BIT** is enough for us. Now how we will approach?

Since there are only 2000 elements we can pre-calculate ever possible query **(l, r)** where **l ≤ r.** Then we will answer each query in **O(1)** time complexity.

**[Approach:](dadsa)**

1. For each **L** from 1 to N we calculate the answer for each **R** from **L** to **N.**
2. The required answer for current **(L, R) = BIT_k(1, a[R] - 1)**
3. Now we have to update **BIT_i,** **BIT_k** and **BIT_j.** 
4. If **a[R]** is less than **a[L]**, then we add 1 to index **a[l]** in **BIT_i.**
5. We update **BIT_j** and **BIT_k** according to upper observations.

This approach is inspired from [here](https://discuss.codechef.com/t/lfives-editorial/10602).

**[Code](dasda):**

#include <bits/stdc++.h>
    
    using namespace std;
    #define ll long long
    #define all(x) x.begin(), x.end()
    typedef vector<ll> vll;
    typedef vector<vll> vvll;
    typedef pair<ll, ll> pll;
    
    const int N = 2e3 + 10;
    const ll M = 1e9 + 7;
    
    ll B[N][3];
    
    void update(int idx, ll v, int t) {
        while (idx < N) {
            B[idx][t] += v;
            idx += idx & (-idx);
        }
    }
    
    ll q(ll idx, int t) {
        ll sm = 0;
        while (idx >= 1) {
            sm += B[idx][t];
            idx -= idx & (-idx);
        }
        return sm;
    }
    
    ll rq(int l, int r, int t) {
    
        return q(r, t) - q(l - 1, t);
    }
    ll ans[N][N];
    int main() {
        int n, q;
        cin >> n >> q;
        vll v(n);
        set<int> s;
        for (int i = 0; i < n; i++) {
            scanf("%lli", &v[i]);
            s.insert(v[i]);
        }
        int id = 1;
        unordered_map<ll, int> m;
        for (auto x : s)
            m[x] = id++;
        
        for (int i = 0; i < n; ++i) {
            memset(B, 0, sizeof(B));
            for (int j = i; j < n; ++j) {
                int idr = m[v[j]];
                ans[i][j] = rq(0, idr - 1, 2);
                if (v[j] < v[i])
                    update(idr, 1, 0);
    
                update(idr, rq(0, idr - 1, 0),
                       1); 
                update(idr, rq(idr + 1, N - 1, 1),
                       2);  
            }
        }
        while (q--) {
            int l, r;
            scanf("%d%d", &l, &r);
            printf("%lli\n", ans[l-1][r-1]);
        }
    }

LFIVES | Editorial by yaseenmollik

Download submission

All caught up!

View submission

Is your resume even shortlisted?