ABC371E I Hate Sigma Problems 题解
- 题目描述
- 问题陈述
- 限制因素
- 样例1解析
- 题解
- (1) 暴力枚举
- 做法
- 代码
- 运行结果
- (2) 暴力优化
- 做法
- 代码
- 运行结果
- 正解
- 代码
- 运行结果
- 结语
题目描述
问题陈述
给你一个长度为 N N N 的整数序列 A = ( A 1 , A 2 , … , A N ) A = (A_1, A_2, \ldots, A_N) A=(A1,A2,…,AN) 。定义 f ( l , r ) f(l, r) f(l,r) 为:
- 子序列 ( A l , A l + 1 , … , A r ) (A_l, A_{l+1}, \ldots, A_r) (Al,Al+1,…,Ar) 中不同值的个数。
计算下面的表达式
∑ i = 1 N ∑ j = i N f ( i , j ) \displaystyle \sum_{i=1}^{N}\sum_{j=i}^N f(i,j) i=1∑Nj=i∑Nf(i,j)
限制因素
- 1 ≤ N ≤ 2 × 1 0 5 1\leq N\leq 2\times 10^5 1≤N≤2×105
- 1 ≤ A i ≤ N 1\leq A_i\leq N 1≤Ai≤N
- 所有输入值均为整数。
样例1解析
f ( 1 , 1 ) = ( A 1 ) 中不同值的个数 = ( 1 ) 中不同值的个数 = 1 f(1, 1) = (A_1) 中不同值的个数 = (1) 中不同值的个数 = 1 f(1,1)=(A1)中不同值的个数=(1)中不同值的个数=1
f ( 1 , 2 ) = ( A 1 , A 2 ) 中不同值的个数 = ( 1 , 2 ) 中不同值的个数 = 2 f(1, 2) = (A_1, A_2) 中不同值的个数 = (1, 2) 中不同值的个数 = 2 f(1,2)=(A1,A2)中不同值的个数=(1,2)中不同值的个数=2
f ( 1 , 3 ) = ( A 1 , A 2 , A 3 ) 中不同值的个数 = ( 1 , 2 , 2 ) 中不同值的个数 = 2 f(1, 3) = (A_1, A_2, A_3) 中不同值的个数 = (1, 2, 2) 中不同值的个数 = 2 f(1,3)=(A1,A2,A3)中不同值的个数=(1,2,2)中不同值的个数=2
f ( 2 , 2 ) = ( A 2 ) 中不同值的个数 = ( 2 ) 中不同值的个数 = 1 f(2, 2) = (A_2) 中不同值的个数 = (2) 中不同值的个数 = 1 f(2,2)=(A2)中不同值的个数=(2)中不同值的个数=1
f ( 2 , 3 ) = ( A 2 , A 3 ) 中不同值的个数 = ( 2 , 2 ) 中不同值的个数 = 1 f(2, 3) = (A_2, A_3) 中不同值的个数 = (2, 2) 中不同值的个数 = 1 f(2,3)=(A2,A3)中不同值的个数=(2,2)中不同值的个数=1
f ( 3 , 3 ) = ( A 3 ) 中不同值的个数 = ( 3 ) 中不同值的个数 = 1 f(3, 3) = (A_3) 中不同值的个数 = (3) 中不同值的个数 = 1 f(3,3)=(A3)中不同值的个数=(3)中不同值的个数=1
∑ i = 1 3 ∑ j = i 3 f ( i , j ) \ \ \ \ \displaystyle \sum_{i = 1}^{3} \sum_{j = i}^{3} f(i, j) i=1∑3j=i∑3f(i,j)
= f ( 1 , 1 ) + f ( 1 , 2 ) + f ( 1 , 3 ) + f ( 2 , 2 ) + f ( 2 , 3 ) + f ( 3 , 3 ) = f(1, 1) + f(1, 2) + f(1, 3) + f(2, 2) + f(2, 3) + f(3, 3) =f(1,1)+f(1,2)+f(1,3)+f(2,2)+f(2,3)+f(3,3)
= 1 + 2 + 2 + 1 + 1 + 1 = 1 + 2 + 2 + 1 + 1 + 1 =1+2+2+1+1+1
= 8 = 8 =8
题解
(1) 暴力枚举
做法
按照题目要求,枚举 i i i 和 j j j,然后算一下从 i i i 到 j j j 的不同值的个数。
算不同值的个数时,可以用一个数组记录每个值是否在之前出现过,每遍历一个数,如果它之前没出现过,就把答案 + 1 + 1 +1,否则直接跳过。时间复杂度 O ( n 3 ) O(n^3) O(n3)。
代码
#include <iostream>
#include <cstring>
#include <algorithm>using namespace std;typedef long long LL;const int N = 200010;int n;
int a[N];
bool st[N];
LL ans;void work(int l, int r)
{int res = 0;for (int i = 1; i <= n; i ++ ) st[i] = false;for (int i = l; i <= r; i ++ ){if (!st[a[i]]) res ++ ;st[a[i]] = true;}ans += res;
}int main()
{scanf("%d", &n);for (int i = 1; i <= n; i ++ ) scanf("%d", &a[i]);for (int i = 1; i <= n; i ++ )for (int j = i; j <= n; j ++ )work(i, j);printf("%lld\n", ans);return 0;
}
运行结果
(2) 暴力优化
做法
我们发现,每次我们都把整个 s t st st 数组清空,因此浪费了很多时间。我们可以在每次 i + 1 i + 1 i+1 时清空 s t st st 数组,当 j j j 循环时,每次将 A j A_j Aj 加入 s t st st,然后当前的 r e s res res 就是 f ( i , j ) f(i, j) f(i,j)。时间复杂度 O ( n 2 ) O(n^2) O(n2)。
代码
#include <iostream>
#include <cstring>
#include <algorithm>using namespace std;typedef long long LL;const int N = 200010;int n;
int a[N];
bool st[N];
LL ans;void work(int l, int r)
{int res = 0;for (int i = 1; i <= n; i ++ ) st[i] = false;for (int i = l; i <= r; i ++ ){if (!st[a[i]]) res ++ ;st[a[i]] = true;ans += res;}
}int main()
{scanf("%d", &n);for (int i = 1; i <= n; i ++ ) scanf("%d", &a[i]);for (int i = 1; i <= n; i ++ )work(i, n);printf("%lld\n", ans);return 0;
}
运行结果
正解
刚才,我们优化了 j j j,现在我们考虑优化 i i i,即求出一个 ∑ j = 1 n f ( 1 , j ) \displaystyle \sum_{j = 1}^n f(1, j) j=1∑nf(1,j),就能推出 ∑ j = i n f ( i , j ) ( 2 ≤ i ≤ n ) \displaystyle \sum_{j = i}^{n} f(i, j) (2 \le i \le n) j=i∑nf(i,j)(2≤i≤n)。
我们考虑一下,如果 i i i 变成了 i + 1 i + 1 i+1,那么 f ( i , j ) f(i, j) f(i,j) 变成 f ( i + 1 , j ) f(i + 1, j) f(i+1,j) 有什么变化。
显然,如果 A i A_i Ai 在 i i i ~ j j j 中只出现一次,那么 i i i ~ j j j 中 A i A_i Ai 这个数出现次数为 1 1 1,而 i + 1 i + 1 i+1 ~ j j j 中 A i A_i Ai 这个数出现次数为 0 0 0,其它数出现次数不变,相当于只有 A i A_i Ai 从有到没有,不同值个数 − 1 - 1 −1。如果 A i A_i Ai 在 i i i ~ j j j 中出现一次以上,那么 i i i ~ j j j 中 A i A_i Ai 这个数出现次数 > 1 > 1 >1,而 i + 1 i + 1 i+1 ~ j j j 中 A i A_i Ai 这个数出现次数为 ≥ 1 \ge 1 ≥1,其它数出现次数不变,相当于所有数的存现都没有变,不同值个数不变。
接着,我们发现存在一个 k k k,使得 j j j 从 i i i 到 k k k 个数发生变化, j j j 从 k + 1 k + 1 k+1 到 n n n 个数不发生变化。因为每次 j + 1 j + 1 j+1 时每个数的个数都只会增加,所以 A i A_i Ai 的出现次数是单调不减的,所以一但 A i > 1 A_i > 1 Ai>1 将一直 A i > 1 A_i > 1 Ai>1,所以 k k k 存在。
最后,我们发现,如果 A i A_i Ai 后面还有 = A i = A_i =Ai 的数,那么 k k k 等于第一个 = A i = A_i =Ai 的下标 − 1 - 1 −1,否则 k = n k = n k=n。因为如果 A i A_i Ai 后面还有 = A i = A_i =Ai 的数,那么当 j j j 到第一个 = A i = A_i =Ai 的下标时, A i A_i Ai 的数量最先 > 1 > 1 >1 因此 k k k 等于第一个 = A i = A_i =Ai 的下标 − 1 - 1 −1。如果 A i A_i Ai 后面没有 = A i = A_i =Ai 的数,那么无论如何 A i A_i Ai 的出现次数都 = 1 = 1 =1,所以永远不可能存在两个值为 A i A_i Ai 的数,所以 k = n k = n k=n。
因此,我们预处理出 i = 1 i = 1 i=1 时 ∑ j = 1 n f ( i , j ) \displaystyle \sum_{j = 1}^n f(i, j) j=1∑nf(i,j) 的结果和每个数后面第一个与它相同的下标(如果没有则设为 n n n)。接着, i i i 从 1 1 1 到 n − 1 n - 1 n−1 遍历,每次算出依次去掉 A i A_i Ai后会把 $ \sum_{j = 1}^n f(i, j)$ 减去的数 = k − i + 1 k - i + 1 k−i+1。最后把预处理的数和每一次去掉剩下的数加在一起就是答案。
时间复杂度 O ( n ) O(n) O(n)。
代码
#include <iostream>
#include <cstring>
#include <algorithm>using namespace std;typedef long long LL;const int N = 200010;int n;
int a[N];
bool st[N];
int ne[N], last[N];int main()
{scanf("%d", &n);for (int i = 1; i <= n; i ++ ) scanf("%d", &a[i]);LL sum = 0, cnt = 0;for (int i = 1; i <= n; i ++ ){if (!st[a[i]]){st[a[i]] = true;cnt ++ ;}sum += cnt;ne[last[a[i]]] = i;last[a[i]] = i;}LL ans = sum;for (int i = 1; i < n; i ++ ){int t = ne[i];if (!t) t = n + 1;sum -= t - i;ans += sum;}printf("%lld\n", ans);return 0;
}
运行结果
结语
再去看这道题,我们先从暴力开始,一步一步优化,最终成功解决了题目。
巧妙的做法往往不是一蹴而就的,而是一步一步优化得到的结果。