Count K 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.

Note: This question is same as K Increasing Subsequence, but this time array can have numbers from 1 to 10^9 and can have duplicates.

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

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

/*
#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];
    }
    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++){
                    dp[end][k]+=dp[start][k-1];
                }
            }
        }
    }
    long long res=0;
    for(int i=0;i<n;i++){
        res+=dp[i][K];
    }
    cout<<res;
    return 0;
}*/ // TLE O(n*n*k)



#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;
    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                           elemnent in array has value > 0
            vector<long long> sum=query(1,m,0,1,arr[i]-1,k); /* find the max value in range
                                                                1 to arr[i]-1 */
            for(int j=2;j<=k;j++){
                Karray[j]=sum[j-1];
            }
        }
        update(1,m,0,arr[i],Karray,k);
    }
    cout<<tree[0][k];
    return 0;
}