Codeforces 597C Subsequences【Dp+二維樹狀數組】

C. Subsequences time limit per test 1 second memory limit per test 256 megabytes input standard input output standard output

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·1018.

Input

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

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

Output

Print one integer — the answer to the problem.

Examples Input

5 2
1
2
3
5
4
      

Output

7      

題目大意：

一共有N個數，讓你找一個長度為K+1的嚴格遞增子序列（沒必要連續），問一共有多少個子序列滿足條件。

思路：

很老套路的題了。

我們需要維護k+1棵樹狀數組，用來求一個字首和。

設定Dp【i】【j】表示到位子i，以a【i】結尾的序列，已經找到了嚴格遞增的j個數的滿足條件的個數。

那麼有：

dp【i】【j】+=dp【k】【j-1】（k<i&&a[k]<a[i]）；

直接暴力轉移肯定要逾時，是以維護K+1個樹狀數組求一個Dp字首和即可。

Ac代碼：

#include<stdio.h>
#include<string.h>
using namespace std;
#define ll __int64
ll tree[15][150000];
ll dp[150000][15];
ll a[150000];
ll lowbit(ll x)
{
    return x&(-x);
}
void update(ll x,ll y,ll d)
{
    ll temp=y;
    while(x<=11)
    {
        y=temp;
        while(y<=100000)
        {
            tree[x][y]+=d;
            y=y+lowbit(y);
        }
        x=x+lowbit(x);

    }

}
ll getsum(ll x,ll y)
{
    ll sum=0;
    ll temp=y;
    while(x>0)
    {
        y=temp;
        while(y>0)
        {
            sum=sum+tree[x][y];
            y=y-lowbit(y);
        }
        x=x-lowbit(x);
    }
    return sum;
}
int main()
{
    ll n,k;
    while(~scanf("%I64d%I64d",&n,&k))
    {
        k++;
        memset(tree,0,sizeof(tree));
        memset(dp,0,sizeof(dp));
        for(ll i=1;i<=n;i++)scanf("%I64d",&a[i]);
        dp[0][0]=1;
        for(ll i=1;i<=n;i++)
        {
            for(ll j=0;j<=k&&j<=i;j++)
            {
                if(i==1)
                {
                    if(j==0)dp[i][j]+=dp[i-1][j];
                    else if(j==1)
                    {
                        dp[i][j]=1;
                        update(j,a[i],1);
                    }
                    continue;
                }
                if(j==0)dp[i][j]+=dp[i-1][j];
                else
                {
                    if(j==1)dp[i][j]+=dp[i-1][j-1];
                    if(j>=2)dp[i][j]+=getsum(j-1,a[i]-1)-getsum(j-2,a[i]-1);
                    update(j,a[i],dp[i][j]);
                }
            }
        }
        ll output=0;
        for(ll i=1;i<=n;i++)output+=dp[i][k];
        printf("%I64d\n",output);
        //prllf("%I64d\n",dp[n][k]);
    }
}