题目
题目描述
小魂的数列一共有n个元素，第i个数为Ai。
他发现，这个数列的一些子序列中的元素是严格递增的。
他想知道，这个数列一共有多少个长度为K的子序列是严格递增的。
对于100%的数据，1≤ n ≤ 500,000,2≤ K ≤ 10,1≤ Ai ≤ 109。
输入描述
第二行包含n个整数，表示小魂的数列。
输出描述
示例1
输入
5 3
2 3 3 5 1
输出
2
说明
2 3 3 5 1 和 2 3 3 5 1 。
题解
知识点：树状数组，枚举，线性dp。
- 改变状态，设 \(f_i\ 为长度为 \(i\ 的上升子序列的最小结尾数字，其有单调递增的性质，因此每次新增数字，二分查找最后一个小于自己数字的位置即可。但是，这个显然不适合用来优化这道题的状态。
- 优化查找，用数据结构维护前缀权值最大值，即以数字作为下标维护每个数字结尾的最大长度。这个方法是可以考虑的，我们将维护最大长度改为各个长度的上升子序列个数即可。
- 排序+优化查找，将数字顺序改为从小到大输入，用数据结构维护前缀最大值，即在原本的区间上维护每个位置结尾的最大长度，输入顺序保证了每次询问的答案一定都是比自己小的数字构成的答案，都是可以接上的。这个方法同样也是可以考虑的，我们将维护最大长度改为各个长度的上升子序列个数即可。
第二种方法需要先离散化，我们这里使用的是第三种方法，先排序后优化查找，复杂度上是没有区别的。
时间复杂度 \(O(nk \log n\
空间复杂度 \(O(nk\
代码
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
const int P = 998244353;
template<class T>
class Fenwick {
int n;
vector<T> node;
public:
Fenwick(int _n = 0 { init(_n; }
void init(int _n {
n = _n;
node.assign(n + 1, T(;
}
void update(int x, T val { for (int i = x;i <= n;i += i & -i node[i] += val; }
T query(int x {
T ans = T(;
for (int i = x;i;i -= i & -i ans += node[i];
return ans;
}
};
int k;
struct T {
array<int, 17> f = {};
T &operator+=(const T &x {
for (int i = 1;i <= k;i++ (f[i] += x.f[i] %= P;
return *this;
}
};
pair<int, int> a[500007];
int main( {
std::ios::sync_with_stdio(0, cin.tie(0, cout.tie(0;
int n;
cin >> n >> k;
for (int i = 1;i <= n;i++ {
int x;
cin >> x;
a[i] = { x,i };
}
sort(a + 1, a + n + 1, [&](auto a, auto b {return a.first < b.first;};
int ans = 0;
Fenwick<T> fw(n;
vector<pair<int, array<int, 17>>> v;
for (int i = 1;i <= n;i++ {
if (a[i].first != a[i - 1].first {
for (auto [id, f] : v fw.update(id, { f };
v.clear(;
}
auto res = fw.query(a[i].second.f;
for (int j = k;j >= 1;j-- res[j] = res[j - 1];
res[1] = 1;
(ans += res[k] %= P;
v.push_back({ a[i].second,res };
}
cout << ans << '\n';
return 0;
}