复制Markdown ?展开
题目描述
Erwin 最近对一种叫 thair 的东西巨感兴趣。。。
在含有?
�
n 个整数的序列?
�
1
,
�
2
,
…
,
�
�
a?
1
?
?,a?
2
?
?,…,a?
n
?
? 中，三个数被称作thair当且仅当?
�
<
�
<
�
i<j<k 且?
�
�
<
�
�
<
�
�
a?
i
?
?<a?
j
?
?<a?
k
?
?。
求一个序列中 thair 的个数。
输入格式
开始一行一个正整数?
�
n,
以后一行?
�
n 个整数?
�
1
,
�
2
,
…
,
�
�
a?
1
?
?,a?
2
?
?,…,a?
n
?
?。
输出格式
一行一个整数表示 thair 的个数。
输入输出样例
输入 #1复制
4
2 1 3 4
输出 #1复制
2
输入 #2复制
5
1 2 2 3 4
输出 #2复制
7
说明/提示
样例2 解释
7
7 个 thair 分别是：
1 2 3
1 2 4
1 2 3
1 2 4
1 3 4
2 3 4
2 3 4
数据规模与约定
对于?
30
%
30% 的数据 保证?
�
≤
100
n≤100；
对于?
60
%
60% 的数据 保证?
�
≤
2000
n≤2000；
对于?
100
%
100% 的数据 保证?
1
≤
�
≤
3
×
1
0
4
1≤n≤3×10?
4
?，
1
≤
�
�
≤
1
0
5
1≤a?
i
?
?≤10?
5
?。
这道题可以拓展到M元上升子序列。
做法: DP + 树状数组优化
仿照
�
�
�
LIS的做法，设
�
[
�
]
[
�
]
f[i][j]为以
�
[
�
]
a[j]为结尾的长度为
�
i的上升子序列的个数。
得到状态转移方程：
�
[
�
]
[
�
]
=
∑
�
<
�
,
�
[
�
]
<
�
[
�
]
�
[
�
?
1
]
[
�
]
f[i][j]=∑?
k<j,a[k]<a[j]
?
?f[i?1][k]
转移时暴力枚举，显然复杂度为
�
(
�
2
�
)
O(N?
2
?M)
考虑到k有两个限制条件，
�
<
�
k<j和
�
[
�
]
<
�
[
�
]
a[k]<a[j]，可以先将
�
[
]
a[]离散化，再用树状数组维护。
具体来说，在外层循环
�
i，建立一个树状数组，以
�
[
�
]
a[k]为下标存储
�
[
�
?
1
]
[
�
]
f[i?1][k]的值。当内层循环到
�
j时，
�
[
�
]
[
�
]
+
=
�
�
�
(
�
[
�
]
?
1
)
f[i][j]+=ask(a[j]?1)，然后在转移到下一个
�
j之前
�
�
�
(
�
[
�
]
,
�
[
�
?
1
]
[
�
]
)
add(a[j],f[i?1][j])。?
�
j从小到大循环保证了
�
<
�
k<j，查询
�
[
�
?
1
]
[
�
?
1
]
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;
}