自动搬运

查看原文

来自洛谷，原作者为

	紫题 **

搬运于2025-08-24 21:27:22，当前版本为作者最后更新于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:$

#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;
}