COUNT K LENGTH INCREASING SUBSEQUENCES

https://www.pepcoding.com/resources/data-structures-and-algorithms-in-java-interview-prep/segment-tree/k-increasing-subsequence2-official/ojquestion

For the given sequence A with n elements find the number of strictly increasing subsequences with k elements.

Input Format
First line contains two integer n and k
following n lines contains elements of sequence
A[1]
A[2]
.
.
A[n]

Output Format
Print one number the answer to question

Constraints
1. 1 <= n <= 10^5
2. 1 <= k <= 11
3. 1 <= A[i] <= 10^9
5. A can contain duplicates
6. Output may not fit in 32 bit signed integer

Sample Input
5 2
1
1
3
8
2
Sample Output
7
Explaination-
The 7 increasing subsequences are [1,3], [1,3], [1,8], [1,8], [1,2], [1,2], [3,8]

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

BRUTE FORCE (TLE)

#include<bits/stdc++.h>
using namespace std;

int main(){
    int K,n;
    cin>>n>>K;
    vector<long long> arr(n);
    for(int i=0;i<n;i++){
        cin>>arr[i];
    }
/* ELEMENTS ARE TOO BIG, SO WE ARE ASSIGNING RANK TO THEM, WELL IF AN ARRAY IS [10,2,5], ASSIGNING THEM [3,1,2] IS THE SAME, THIS WOULD NOT AFFECT THE COUNT OF SUBSEQUENCES, SINCE YOU CAN SEE RELATIVE ORDERING IN BOTH ARE SAME, WE JUST ASSIGNED SMALLER VALUES TO THEM TO REDUCE TIME COMPLEXITY OF SEGMENT TREE */
    vector<long long> temp=arr;
    sort(temp.begin(),temp.end());
    unordered_map<long long,long long> mpp;
    long long m=1;
    for(int i=0;i<n;i++){
        if(mpp.find(temp[i])==mpp.end()){
            mpp[temp[i]]=m;
            m++;
        }
    }
    for(int i=0;i<n;i++){
        arr[i]=mpp[arr[i]];
    }

    long long dp[n][K+1];
    memset(dp,0,sizeof(dp));
    for(int i=0;i<n;i++){
        dp[i][1]=1;
    }
    for(int end=1;end<n;end++){
        for(int start=0;start<end;start++){
            if(arr[end]>arr[start]){
                for(int k=2;k<=K;k++){
                         /* IT IS QUITE EASY TO IMAGINE. You are gonna add arr[end] to elements in arr[start] to achieve length k.
                            Now, to achieve k length, you need to add k-1 elements. WHY? Because you are obviously adding arr[end] so
                            adding 1 more, hence achieving k length in total. So, you can say, a subsequence of length 3 at arr[start]
                            becomes a subsequence of length 4 at arr[end] because arr[end] gets added to it. So, in general,
                            dp[end][k]+=dp[start][k-1], for k>=2. As if k=2, at dp[end][2]+=dp[start][1], all subsequences of length
                            k=1 at start will become 2 anyways when appended arr[end] to it, so we just add their count
                        */
                    dp[end][k]+=dp[start][k-1];
                }
            }
        }
    }
    long long res=0;
    for(int i=0;i<n;i++){
        res+=dp[i][K];  // ADD ALL SUBSEQUENCES WITH LENGTH K FROM EACH INDEX
    }
    cout<<res;
    return 0;
}

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

SEGMENT TREE (AC)

#include<bits/stdc++.h>
using namespace std;

vector<vector<long long>> tree;

vector<long long> summation(vector<long long> &left, vector<long long> &right, int k){
    vector<long long> res(k+1,0);
    for(int i=1;i<=k;i++){
        res[i]=left[i]+right[i];
    }
    return res;
}

vector<long long> query(int start, int end, int parent, int qstart, int qend, int k){
    if(end<qstart || qend<start){
        return vector<long long>(k+1,0);
    }
    if(qstart<=start && qend>=end){
        return tree[parent];
    }
    int mid=(start+end)/2;
    auto left=query(start,mid,2*parent+1,qstart,qend,k);
    auto right=query(mid+1,end,2*parent+2,qstart,qend,k);
    return summation(left,right,k);
}

void update(int start, int end, int parent, int index, vector<long long> &updateThis, int k){
    if(index<start || index>end){
        return;
    }
    if(start==end){
        tree[parent]=summation(updateThis,tree[parent],k);
        return;
    }
    int mid=(start+end)/2;
    if(index>mid){
        update(mid+1,end,2*parent+2,index,updateThis,k);
    }
    else{
        update(start,mid,2*parent+1,index,updateThis,k);
    }
    auto left=tree[2*parent+1];
    auto right=tree[2*parent+2];
    tree[parent]=summation(left,right,k);
    return;
}

int main(){
    int k,n;
    cin>>n>>k;
    vector<int> arr(n);
    for(int i=0;i<n;i++){
        cin>>arr[i];
    }
    vector<int> temp=arr;
    sort(temp.begin(),temp.end());
    unordered_map<int,int> mpp;
    int m=1;
/* ELEMENTS ARE TOO BIG, SO WE ARE ASSIGNING RANK TO THEM, WELL IF AN ARRAY IS [10,2,5], ASSIGNING THEM [3,1,2] IS THE SAME, THIS WOULD NOT AFFECT THE COUNT OF SUBSEQUENCES, SINCE YOU CAN SEE RELATIVE ORDERING IN BOTH ARE SAME, WE JUST ASSIGNED SMALLER VALUES TO THEM TO REDUCE TIME COMPLEXITY OF SEGMENT TREE */
    for(int i=0;i<n;i++){
        if(mpp.find(temp[i])==mpp.end()){
            mpp[temp[i]]=m;
            m++;
        }
    }
    for(int i=0;i<n;i++){
        arr[i]=mpp[arr[i]];
    }
    tree.resize(4*m+1,vector<long long>(k+1,0));
    for(int i=0;i<n;i++){
        vector<long long> Karray(k+1,0);
        Karray[1]=1;
        if(arr[i]!=1){ // because if arr[i]==1, we would not find arr[i]-1 that is 0 anywhere cuz every element in array has value > 0
            vector<long long> KBest=query(1,m,0,1,arr[i]-1,k);
           /* find the total Karray for range 1 to (arr[i]-1), as arr[i] can be appended to all elements in this range */
            for(int len=2;len<=k;len++){ // same explanation, all subseq with len-1 in Kbest will be the subseq of len in Karray
                Karray[len]=KBest[len-1];
            }
        }
        update(1,m,0,arr[i],Karray,k);
    }
    cout<<tree[0][k]; // this tells me the count of subseq with len k
    return 0;
}