597C-Subsequences

2022-03-13 题解

题目大意：给出一个数列，每个数不重复。问长度为k+1的上升子序列一共有多少个。

令f[i][j]表示长度为i，且末尾元素为j的上升子序列的个数。由于数列中的各个数不重复，按照输入的顺序处理各个数，当处理到第j个数（a[j]）时，有

f[i][a[j]]=\sum_{x=1}^{a[j]-1}f[i-1][x]

这其实就相当于求f[i-1]的前缀和。由于在操作中，前缀和时刻都有可能改变，需要使用树状数组来维护。

#include <bits/stdc++.h>
using namespace std;
long long bit[15][100005];
int n;
int lowbit(int x)
{
    return x & -x;
}
void add(int i, int num, long long x)
{
    while (num <= n)
    {
        bit[i][num] += x;
        num += lowbit(num);
    }
}
long long dp(int i, int x)//求长度为i，末尾元素值不超过x的上升子序列个数
{
    long long ret = 0;
    while (x > 0)
    {
        ret += bit[i][x];
        x -= lowbit(x);
    }
    return ret;
}
int main()
{
    int k, i, j, a;
    scanf("%d%d", &n, &k);
    long long res = 0;
    for (i = 1; i <= n; i++)
    {
        scanf("%d", &a);
        res += dp(k, a);
        for (j = k; j > 1; j--)
            add(j, a, dp(j - 1, a));
        add(1, a, 1);
    }
    if (k == 0) //边界未处理，需特判
        res = n;
    printf("%lld", res);
    return 0;
}