[CF597C Subsequences] 题解

[CF597C Subsequences]

前言

这是一道数据结构优化 $dp$ 的入门题，但是也很有意思。

前置知识：线段树维护前缀和（区间加法，单点求值）

题解正文

题目大意：

给定一个长度为 $n$ 的序列 $A$ 以及一个数 $k$ ，求其长度为 $k + 1$ 的上升子序列的数量。

$n <= 10^5,1 <= A_i <= n,0 <= k <= 10$

思路:

首先我们看到本题，不难想到经典问题：最长上升子序列。（但是其实关系不大）

在解最长上升子序列的时候我们一般用的是 $nlogn$ 的算法，但是实际上还存在一种被不屑的 $n^2$ 求最长上升子序列的方法。

对于 $n^2$ 的方法稍加魔改变形就可以得到本题的 $n^2$ 做法。

$n ^ 2$ $dp$ :

设置状态:

$dp[i][j]$ 表示前 $i$ 个数中，以 $i$ 结尾的长度为 $j$ 的上升子序列的数量。

转移方程:

$dp[i][j] = \sum_{l = 1}^{l = min(i,k+1)}{dp[l][j - 1](if:A[i] > A[l])}$

边界设置:

$dp[i][1] = 1$

最终答案即: $\sum_{i = 1}^{i = n}{dp[i][k + 1]}$

上面这个方法我们需要枚举 $i$ ，以及子序列长度 $j$ ，还有枚举 $i$ 前面的所有 $dp[l][j - 1]$ ，总复杂度是 O $(n^2k)$ 的，这是显然过不了本题的。

思考如何优化。

不难发现 $dp[i][j]$ 只与 $dp[l < i][j - 1]$ 有关，可以类似于前缀和处理，但是前缀和每次修改需要 O $(n)$ 的复杂度，行不通。

于是考虑用 线段树/树状数组 优化这个过程。

将 $A[i]$ 看作是前缀和的下标，然后前缀和对应的值就是 $dp[i][j]$ ，然后线段树维护前缀和即可。

因为是按照 $1$ ~ $n$ 的顺序进行 $dp$ 的，我们很容易边 $dp$ 转移状态边修改，从而满足 $l < i$ ，于是就可以大胆的采用 $11$ 棵线段树维护整个 $dp$ 过程，从而使得整个过程都满足 $A[l] < A[i]$ 。

此题完结。

细节可见代码：

Code

#include <bits/stdc++.h>
using namespace std;
char buf[1 << 22] , *p1 = buf , * p2 = buf;(kaui)
#define int long long
#define mid ((L[x] + R[x]) >> 1)
#define getchar() (p1 == p2 && (p2 = (p1 = buf) + fread(buf , 1 , 1 << 21 , stdin) , p1 == p2) ? EOF : *p1++)
const int MAXN = 1e5 + 50;
int n,k,A[MAXN];
long long dp[MAXN][15],Ans;

inline int read() {
    int x = 0 , flag = 1;
    char ch = getchar();
    for( ; ch > '9' || ch < '0' ; ch = getchar()) if(ch == '-') flag = -1;
    for( ; ch >= '0' && ch <= '9' ; ch = getchar()) x = (x << 3) + (x << 1) + ch - '0';
    return x * flag;
}

struct SegmentTree {//11棵线段树都写一遍不现实，用结构体就可以封装了
    int L[MAXN * 4],R[MAXN * 4],sum[MAXN * 4],laz[MAXN * 4];

    void build(int x,int l,int r) {//建树
        L[x] = l , R[x] = r; 
        laz[x] = sum[x] = 0;
        if(l == r) return ;
        build(x << 1 , l , mid);
        build(x << 1 | 1  , mid + 1 , r);
    }

    void ad(int x,int k) {//修改 
        laz[x] += k , sum[x] += k; 
        return ;
    }

    void pushdown(int x) {//下传标记
        if(laz[x] == 0) return ;
        ad(x << 1 , laz[x]);
        ad(x << 1 | 1 , laz[x]);
        laz[x] = 0;
        return ;
    }

    int Get(int x,int pos) {//单点求值
        if(L[x] == pos && R[x] == pos) return sum[x];
        pushdown(x);
        if(pos <= mid) return Get(x << 1 , pos);
        else return Get(x << 1 | 1, pos);
    }

    void change(int x,int l,int r,int k) {//区间修改
        if(L[x] >= l && R[x] <= r) {ad(x,k) ; return ;}
        if(l <= mid) change(x << 1 , l , r , k);
        if(r  > mid) change(x << 1 | 1 , l , r , k);
        return ;
    }
} T[12];

signed main() {
    n = read() , k = read();
    for(int i = 1 ; i <= n ; i ++) A[i] = read(),dp[i][1] = 1;
    if(k == 0) { cout << n ; return 0;}
    for(int i = 1 ; i <= k + 1 ; i ++) T[i].build(1, 1, n);
    for(int i = 1 ; i <= n ; i ++) {
        for(int j = 2 ; j <= min(i, k + 1) ; j ++)
        dp[i][j] += T[j - 1].Get(1,A[i]) ;//获得答案
        for(int j = 1 ; j <= min(i, k + 1) ; j ++)
        T[j].change(1,A[i] + 1 , n , dp[i][j]);//每次都修改
        Ans += dp[i][k + 1];//统计答案
    }
    cout << Ans;
    return 0;
}