【例题 \(1\) 】 递增子序列
考虑 \(dp.\)
\(dp[i][j]\) 表示以元素 \(i\) 为结尾，长度为 \(k\) 的方案数。
那么显而易见就有一个转移方程：
\[dp[i][j]=\sum_{a[k]<a[i] ,\ k<i} dp[k][j-1] \]先抛去第二维度的 \(j\) ，这是可以做一个关于 \(a[i]\) 值的大小，数值是 \(dp\) 的树状数组的。
维护两个操作：单点修改，区间查询。
当然因为 \(a[i]\) 实在是太大了，所以离散化。
如果加上第二层维度那就建立 \(k\) 个树状数组就好了。
#include <bits/stdc++.h>
#define int long long
#define ls (u << 1)
#define rs (u << 1 | 1)
#define lson ls, l, mid
#define rson rs, mid + 1, r
#define mid ((l + r) >> 1)
const int inf = 1e18;
const int N = 1e4 + 10;
const int mod = 123456789;
using namespace std;
int n, m;
struct ta {
int tree[N];
inline int lowbit(int x) { return x & -x; }
inline void update(int x, int k) {
while (x <= N) (tree[x] += k) %= mod, x += lowbit(x);
}
inline int query(int x) {
int res = 0;
while (x) (res += tree[x]) %= mod, x -= lowbit(x);
return res;
}
} t[105];
int tmp, val[N], b[N];
signed main() {
while (~scanf("%lld%lld", &n, &m)) {
for (int i = 1; i <= m; ++i) memset(t[i].tree, 0, sizeof t[i].tree);
memset(val, 0, sizeof val), memset(b, 0, sizeof b);
tmp = 0;
for (int i = 1; i <= n; ++i) scanf("%lld", &val[i]), b[i] = val[i];
stable_sort(b + 1, b + n + 1);
int len = unique(b + 1, b + n + 1) - b - 1;
for (int i = 1; i <= n; ++i) val[i] = lower_bound(b + 1, b + len + 1, val[i]) - b;
for (int i = 1; i <= n; ++i) {
t[1].update(val[i], 1);
for (int j = 1; j < m; ++j) {
tmp = t[j].query(val[i] - 1);
if (!tmp)
break;
t[j + 1].update(val[i], tmp);
}
}
printf("%lld\n", t[m].query(n) % mod);
}
return 0;
}