当前位置: 代码迷 >> 综合 >> Codeforces 597C Subsequences (二维树状数组+DP)*
  详细解决方案

Codeforces 597C Subsequences (二维树状数组+DP)*

热度:18   发布时间:2023-11-15 16:32:12.0

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
#include<iostream>
#include<algorithm>
#include<string>
#include<map>//int dx[4]={0,0,-1,1};int dy[4]={-1,1,0,0};
#include<set>//int gcd(int a,int b){return b?gcd(b,a%b):a;}
#include<vector>
#include<cmath>
#include<stack>
#include<string.h>
#include<stdlib.h>
#include<cstdio>
#define mod 1e9+7
#define ll long long
#define MAX 1000000000
#define ms memset
using namespace std;
const int maxn=1e5+5;ll n,k,seq[maxn];
ll dp[20][maxn<<1];
ll tree[20][maxn<<1];
/*
题目大意:计数递增长度为k+1的递增子序列。树状数组二维,
思路是看了别人的才会的。
首先对于每个数,都有k的长度数组来保存dp[i][k]结果,
那么长度等于k+1的计算方法就是用两个前缀相减即可。这次add更新的是dp值本身,当遇到子情况时add值为1.*/int  lowbit(int x){ return x&(-x); }void add(ll x,ll y,ll d)
{ll tmp=x;while(y<=15){for(;x<=n;tree[y][x]+=d, x+=lowbit(x));x=tmp;y+=lowbit(y);}
}ll sum(ll x,ll y)
{ll tmp=x;ll res=0;while(y){for(x=tmp;x>0;res+=tree[y][x],x-=lowbit(x));y-=lowbit(y);}return res;
}int main()
{scanf("%lld%lld",&n,&k);k++;for(ll i=1;i<=n;i++) scanf("%lld",&seq[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[j][i] += dp[j][i-1];else if(j==1){dp[j][i]=1;add(seq[i],j,1);}continue;}///处理子情况if(j==0) dp[j][i]+=dp[j][i-1];else{if(j==1) dp[j][i]+=dp[j-1][i-1];if(j>=2)  dp[j][i]+=sum(seq[i]-1,j-1)-sum(seq[i]-1,j-2);///其前缀性质首先在k上比较好理解add(seq[i],j,dp[j][i]);}}ll output=0;for(ll i=1;i<=n;i++) output+=dp[k][i];printf("%lld\n",output);return 0;
}