CodeForces - 597C：Subsequences （主席树+DP）

For the given sequence with n different elements find the number of increasing subsequences with k + 1 elements. It is guaranteed that the answer is not greater than 8·10¹⁸.

Input

First line contain two integer values n and k (1 ≤ n ≤ 10⁵, 0 ≤ k ≤ 10) — the length of sequence and the number of elements in increasing subsequences.

Next n lines contains one integer a_i (1 ≤ a_i ≤ n) each — elements of sequence. All values a_i are different.

Output

Print one integer — the answer to the problem.

Examples

Input

Output

题意：求多少个LIS，其长度为K+1。

思路：用dp[k][x]表示以x结尾的长度为k的LIS。那么暴力的DP复杂度是O（N^2）。

建立k棵线段树，每棵树N个叶子节点，第i棵树的第j个叶子节点表示以j为结尾的长度为i的LIS个数。那么Tree[i][j]+=Tree[i-1][1到j-1]。

(直接写线段树也可以，这里练习一下主席树。当然最好写的还是树状数组！

相比的话，主席树应该还是好写的。

#include<bits/stdc++.h>

typedef long long ll;

using namespace std;

const int maxn=;

int rt[maxn],cnt; ll ans;

struct node

{

    int l,r; ll val;

    node(){ l=r=;val=;}

    node(int L,int R,ll V):l(L),r(R),val(V){}

}s[maxn*];

ll query(int Now,int L,int R,int l,int r)

{

    if(l<=L&&r>=R) return s[Now].val;

    ll res=; int Mid=(L+R)>>;

    if(l<=Mid) res+=query(s[Now].l,L,Mid,l,r);

    if(r>Mid) res+=query(s[Now].r,Mid+,R,l,r);

    return res;

}

void update(int &Now,int L,int R,int pos,ll val)

{

    if(Now==) Now=++cnt;

    s[Now].val+=val;

    if(L==R) return ; int Mid=(L+R)>>;

    if(pos<=Mid) update(s[Now].l,L,Mid,pos,val);

    else update(s[Now].r,Mid+,R,pos,val);

}

int main()

{

    int N,K,i,j,x;

    scanf("%d%d",&N,&K);

    for(i=;i<=N;i++){

        scanf("%d",&x); x+=;

        update(rt[],,N+,x,);

        for(j=;j<=K;j++) {

            ll tmp=query(rt[j],,N+,,x-);

            update(rt[j+],,N+,x,tmp);

        }

    }

    ans=query(rt[K+],,N+,,N+);

    printf("%I64d\n",ans);

    return ;

}

巴特西

CodeForces - 597C：Subsequences （主席树+DP）

最新文章

热门文章