跳转至

树状数组优化 DP

树状数组可以在小常数（均摊 \(\frac12\)）\(O(\log n)\) 的时间复杂度内实现以下操作：

  • 区修 + 区查；
  • 单修（取 max 或 min，并非赋值） + 前/后缀 最值；

卡常技巧

对于最值查询，我们提供一种卡常技巧：

1
2
3
4
5
6
inline void modify(cint p, cint v) {
    for(int i = p; i < N; i += lowbit(i)) {
        if(mx[i] >= v) break;
        mx[i] = v;
    }
}

因为我们发现，在 modify() 函数里，对于遍历到的任意两个 \(i\) 的值 \(i_1,i_2\)，若 \(i_1<i_2\)，则总有 \((i_1-lowbit(i_1),i_1]\subset (i_2-lowbit(i_2),i_2]\)（即较小的 \(i\) 所代表的区间总被较大的 \(i\) 所代表的区间所包含）。

因此，如果 \(v\) 在一个较小的区间里都不能产生贡献，则在更大的区间则一定不能。此种技巧在随机数据下能进一步减小常数。

可以说，树状数组能做的事，线段树都能以相同的渐进复杂度实现。因树状数组的码量、常数较小，首选树状数组。

言归正传，对于 DP，如果我们发现其状态转移方程需要快速查询前、后缀最值，则考虑使用树状数组。

B3637 最长上升子序列

设 \(f_i\) 表示以数字 \(i\) 为结尾，最长上升子序列的长度。状态转移方程：

\[ f_{a_i}=\max_{j<a_i}\{f_j\}+1 \]

注意到这是一个求前缀最大值的转移形式，可以使用树状数组优化。

代码 
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
#include<iostream>
using namespace std;
const int N = 5010;
const int V = 1E6 + 10;

namespace BIT {
    int mx[V];
    inline int lowbit(int x) { return x & -x; }
    inline void modify(int p, int v) {
        for(int i = p + 1; i < V; i += lowbit(i)) {
            if(v <= mx[i]) break;
            mx[i] = v;
        }
    }
    inline int query(int p) {
        int res = 0;
        for(int i = p + 1; i > 0; i -= lowbit(i)) {
            res = max(res, mx[i]);
        }
        return res;
    }
}

int n;
int a[N];

int main() {

    cin >> n;
    for(int i = 1; i <= n; i++) {
        cin >> a[i];
    }

    for(int i = 1; i <= n; i++) {
        int tmp = BIT::query(a[i] - 1) + 1;
        BIT::modify(a[i], tmp);
    }

    cout << BIT::query(V - 5) << endl;

    return 0;
}

P3287 [SCOI2014] 方伯伯的玉米田

题目大意

给定一个长度为 \(n\) 的序列，你可以进行不超过 \(m\) 次如下的操作，最大化最终得到的序列的最长不降子序列长度。

  • 选定一个区间 \([l,r]\)，进行区间 '+1'；

我们发现，对一个区间 \([l,r]\) 操作，对 \([1,l)\rightarrow [l,r]\) 的单调性是有利的，但会使 \([l,r]\rightarrow (r,n]\) 更劣，而对 \([l,r]\) 内部的数字没有本质的作用。我们希望使每次操作更优，因此将 \(r\) 取为 \(n\) 总是不劣的。因为不会产生任何副作用，且能最大化 \([1,l)\rightarrow[l,r]\) 的影响范围。

考虑一个朴素的 DP，设 \(f_{j,k}\) 表示当前区间 \([1,i]\) 范围内，以数字 \(j\) 为结尾，使用了 \(k\) 次操作，最长上升子序列的长度是多少。写出状态转移方程：

\[ f'_{j,k}= \begin{cases} \max(\max_{p\le j}\{f_{p,k}\},\max_{q>0}\{f_{j+q,k-q}\})+1,&j=a_i\\ f_{j,k},&j\ne a_i \end{cases} \]

我们可以使用两个数组套树状数组分别维护上面提到的两个前缀最值。

对于第一个 \(\max\)，我们将 \(k\) 作为数组的下标，\(p\) 作为 BIT 的下标；对于第 \(2\) 个 \(\max\)，我们将 \(j+k\) 作为数组的下标，\(k\) 作为 BIT 的下标。计算得到 \(f'_{a_i,k}\) 之后，分别在两个树状数组上 modify 即可。

总时间复杂度 \(O(nk\log V)\)。

代码 
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
#include<iostream>
#define int short int
using namespace std;
const int N = 1E4 + 10;
const int K = 510;
const int V = 5010;

int n, k;
int a[N];

namespace BIT {
    int tr1[K][V], tr2[K + V][K];
    inline int lowbit(int x) { return x & -x; }
    inline void modify1(int id, int p, int v) {
        for(int i = p + 3; i < V; i += lowbit(i)) {
            if(tr1[id][i] >= v) break;
            tr1[id][i] = v;
        }
    }
    inline void modify2(int id, int p, int v) {
        for(int i = p + 3; i < K; i += lowbit(i)) {
            if(tr2[id][i] >= v) break;
            tr2[id][i] = v;
        }
    }
    inline int query1(int id, int p) {
        int res = 0;
        for(int i = p + 3; i > 0; i -= lowbit(i)) {
            res = max(res, tr1[id][i]);
        }
        return res;
    }
    inline int query2(int id, int p) {
        int res = 0;
        for(int i = p + 3; i > 0; i -= lowbit(i)) {
            res = max(res, tr2[id][i]);
        }
        return res;
    }
}

signed main() {

    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);

    cin >> n >> k;
    for(int i = 1; i <= n; i++) {
        cin >> a[i];
    }

    for(int i = 1; i <= n; i++) {
        for(int kk = 0; kk <= k; kk++) {
            int tmp = max(BIT::query1(kk, a[i]), BIT::query2(kk + a[i], kk)) + 1;
            BIT::modify1(kk, a[i], tmp);
            BIT::modify2(kk + a[i], kk, tmp);
        }
    }

    int ans = 0;
    for(int i = 0; i <= k; i++) {
        ans = max(ans, BIT::query1(i, 5000));
    }

    cout << ans << endl;

    return 0;
}

P7302 [NOI1998] 免费的馅饼

见二维数点。