题解 P1637 【三元上升子序列】
紫题
2019-03-23 21:03:09
## 这道题可以拓展到M元上升子序列。
## 做法: DP + 树状数组优化
仿照$LIS$的做法，设$f[i][j]$为以$a[j]$为结尾的长度为$i$的上升子序列的个数。
得到状态转移方程：$f[i][j] = {\sum_{k<j,a[k]<a[j]}}f[i-1][k]$
转移时暴力枚举，显然复杂度为$O(N^{2}M)$
考虑到k有两个限制条件，$k<j$和$a[k]<a[j]$，可以先将$a[]$离散化，再用树状数组维护。
具体来说，在外层循环$i$，建立一个树状数组，以$a[k]$为下标存储$f[i-1][k]$的值。当内层循环到$j$时，$f[i][j]+=ask(a[j]-1)$，然后在转移到下一个$j$之前$add(a[j],f[i-1][j])$。
$j$从小到大循环保证了$k<j$，查询$f[i-1][j-1]$的前缀和保证了$a[k]<a[j]$。
复杂度$O(NMlogN)$。
~~双倍经验：UVA12983~~
$CODE:$
```cpp
#include<iostream>
#include<cstring>
#include<cstdio>
#include<algorithm>
using namespace std;
typedef long long ll;
ll n, a[30010], s[30010], m, f[4][30010], c[60010], ans;
ll val(int x) { return lower_bound(s+1, s+m+1, x) - s; }
ll ask(int x, ll sum = 0) {
for(; x; x -= (x & (-x))) sum += c[x];
return sum;
}
void add(int x, ll v) { for(; x <= m; x += (x & (-x))) c[x] += v; }
int main() {
cin >> n;
for(int i = 1; i <= n; i++) cin >> a[i], s[i] = a[i];
sort(s+1, s+n+1);
m = unique(s+1, s+n+1) - s - 1;
for(int i = 1; i <= n; i++) f[1][i] = 1, a[i] = val(a[i]);
for(int i = 2; i <= 3; i++) {
memset(c, 0, sizeof(c));
for(int j = 1; j <= n; j++) {
f[i][j] = ask(a[j]-1);
add(a[j], f[i-1][j]);
}
}
for(int i = 1; i <= n; i++) ans += f[3][i];
cout << ans << endl;
return 0;
}
```