题目描述
难度分:2100
输入n(1≤n≤3×105)、m(1≤m≤3×105)和长为n的数组a(1≤a[i]≤m)。
定义振荡序列为形如[3,1,3],[3,2,3,2],[1]这种最多由两种元素组成的,相邻元素不同的序列。
定义f(x,y)为a中最长振荡子序列的长度,其中子序列的每个数要么是x,要么是y。
注:子序列不一定连续。
输出所有f(x,y)的和,其中1≤x<y≤m。
输入样例1
5 4
3 2 1 3 2
输出样例1
13
输入样例2
3 3
1 1 1
输出样例2
2
算法
贡献法
这种题目看着就很贡献法,因为不可能枚举所有的数对(x,y),但是本题求贡献的方式还挺抽象的。对于一个a[i],我们计算它对答案的贡献分为以下两种情况:
- a[i]是第一次出现:它和一个不在a数组中的数贡献就是1,设总共有c个[1,m]内的数不在a数组中,总的贡献就是c。它和在a中的数的贡献又分为两种情况:(1) 如果这个数第一次出现在a[i]的左边,那么a[i]直接接在后面形成更长的振荡序列即可,为它们形成的最长振荡序列贡献1。(2) 如果这个数第一次出现在a[i]的右边,那么a[i]就在它的前面,也为它们形成的最长振荡序列贡献1。所以一共有m−1−c个这样的数,就能有m−1−c的贡献。这两种情况的总贡献加起来就是m−1−c+c=m−1。
- a[i]不是第一次出现,假设它上一次出现的位置是pre[a[i]](可以用一个哈希表来维护),那么(pre[a[i]],i)中间有多少个不同的数就能贡献多少,假设一共有k个不同的数。这k个数都可以接在上一个a[i]的后面形成振荡序列,为它们的长度都增加1,k个序列就增加k的贡献。
至于如何统计区间内不同数的个数?可以用主席树,也可以用树状数组维护每个数的最新下标,即每个数值a[i]最后一次出现的时候在树状数组的i位置加1,之前出现数值a[i]加1的下标j上加−1撤销掉。查询区间内下标个数,这样对应的就是区间中有多少个不同的数,详见代码。
复杂度分析
时间复杂度
遍历i∈[1,n]时计算答案,而每个下标i都有一次对树状数组的操作,时间复杂度为O(log2n)。因此,整个算法的时间复杂度为O(nlog2n)。
空间复杂度
空间消耗主要是两部分:哈希表pre,在最差情况下需要存O(n)个值的最早出现位置,因此空间复杂度为O(n);树状数组tr,其长度也是O(n)。因此,整个算法的额外空间复杂度为O(n)。
C++ 代码
#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
int n, m;
class Fenwick {
public:
explicit Fenwick(int n): sums_(n + 1) {}
int lowbit(int x) {
return x&-x;
}
void add(int idx, int val) {
for(; idx < sums_.size(); idx += lowbit(idx)) {
sums_[idx] += val;
}
}
int query(int idx) {
int ans = 0;
for(; idx > 0; idx -= lowbit(idx)) {
ans += sums_[idx];
}
return ans;
}
int query(int left, int right) {
if(left > right) return 0;
return query(right) - query(left - 1);
}
private:
vector<int> sums_;
};
int main() {
scanf("%d%d", &n, &m);
LL ans = 0;
unordered_map<int, int> pre;
Fenwick tr(n + 1);
for(int i = 1; i <= n; i++) {
int a;
scanf("%d", &a);
if(pre.count(a)) {
int j = pre[a];
ans += tr.query(j + 1, i - 1);
tr.add(j, -1);
}else {
// 首次出现
ans += m - 1;
}
tr.add(i, 1);
pre[a] = i;
}
printf("%lld\n", ans);
return 0;
}