Count Special Increasing Quadruplets (HARD PROBLEM) LEETCODE

https://leetcode.com/problems/count-increasing-quadruplets/

Given a 0-indexed integer array nums of size n containing all numbers from 1 to n, return the number of increasing quadruplets.

A quadruplet (i, j, k, l) is increasing if:

0 <= i < j < k < l < n, and
nums[i] < nums[k] < nums[j] < nums[l].


Example 1:
Input: nums = [1,3,2,4,5]
Output: 2

Explanation:
- When i = 0, j = 1, k = 2, and l = 3, nums[i] < nums[k] < nums[j] < nums[l].
- When i = 0, j = 1, k = 2, and l = 4, nums[i] < nums[k] < nums[j] < nums[l].
There are no other quadruplets, so we return 2.

Example 2:
Input: nums = [1,2,3,4]
Output: 0

Explanation: There exists only one quadruplet with i = 0, j = 1, k = 2, l = 3, but since nums[j] < nums[k], we return 0.


Constraints:

4 <= nums.length <= 4000
1 <= nums[i] <= nums.length
All the integers of nums are unique. nums is a permutation.

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

class Solution {
public:
    long long countQuadruplets(vector<int>& nums) {
        int n=nums.size();
        vector<vector<long long>> prefix(n+1,vector<long long>(n,0)); // finding count of elements greater than nums[i] from (i+1)->(n-1)
        vector<vector<long long>> suffix(n+1,vector<long long>(n,0)); // finding count of elements smaller than nums[i] from 0->(i-1)


        for(int i=0;i<n;i++){
            int x=nums[i];
            for(int j=i+1;j<n;j++){
                if(x<nums[j]){
                    prefix[x][j]=1;
                }
                prefix[x][j]+=prefix[x][j-1];
            }
        }

        for(int i=n-1;i>=0;i--){
            int x=nums[i];
            for(int j=i-1;j>=0;j--){
                if(x>nums[j]){
                    suffix[x][j]=1;
                }
                suffix[x][j]+=suffix[x][j+1];
            }
        }

        long long res=0;

        // here index variable i,j,k,l have exactly the same meaning as the question
        for(int j=1;j<n-2;j++){
            for(int k=j+1;k<n-1;k++){
                if(nums[k]<nums[j]){
                    long long i=suffix[nums[k]][0]-suffix[nums[k]][j]; // finding count of elements smaller than nums[k] in index range (0,j-1)
                    long long l=prefix[nums[j]][n-1]-prefix[nums[j]][k]; // finding count of elements greater than nums[j] in index range (k+1,n-1)
                    res+=i*l;
                }
            }
        }
        return res;
    }
};


/*
class Solution {
private:
    int tree[4*4000+10];
public:
    void update(int low, int high, int parent, int index){
        if(low==high){
            tree[parent]=1;
            return;
        }
        int mid=(low+high)/2;
        if(index<=mid){
            update(low,mid,2*parent+1,index);
        }
        else{
            update(mid+1,high,2*parent+2,index);
        }
        tree[parent]=tree[2*parent+1]+tree[2*parent+2];
    }

    int query(int low, int high, int parent, int lowerR, int higherR){
        if(low>higherR || high<lowerR){
            return 0;
        }
        if(low>=lowerR && high<=higherR){
            return tree[parent];
        }
        int mid=(low+high)/2;
        return query(low,mid,2*parent+1,lowerR,higherR)+query(mid+1,high,2*parent+2,lowerR,higherR);
    }

    long long countQuadruplets(vector<int>& nums) {
        long long res=0;
        int n=nums.size();
        vector<vector<int>> precompute(n+1,vector<int>(n,0));
        vector<vector<int>> smallerThan(n+1);

        for(int i=0;i<n;i++){
            int x=nums[i];
            for(int j=i+1;j<n;j++){
                if(x<nums[j]){
                    precompute[x][j]=1;
                }
                if(x>nums[j] && j<n-1){
                    smallerThan[x].push_back(j);
                }
                precompute[x][j]+=precompute[x][j-1];
            }
        }

        for(int j=0;j<n-2;j++){
            int x=nums[j];
            vector<int> K=smallerThan[x];
            for(auto k: K){
                long long lessThank=query(0,n-1,0,0,nums[k]-1);
                long long greaterThanX=precompute[x][n-1]-precompute[x][k];
                res+=greaterThanX*lessThank;
            }
            update(0,n-1,0,x);
        }
        return res;
    }
};
*/ // segment tree but kinda useless actually. I OVER-thought it and its really not that useful