E - I Hate Sigma Problems (atcoder.jp)

此文章为临时文章。

一、分析原始代码的问题

您的代码如下：

#include<bits/stdc++.h>
#define ll long long
#define mem(x) memset(x,0,sizeof(x))
using namespace std;
const int N=200005;
int n,a[N],cnt;
int main(){
    cin>>n;
    for(int i=1;i<=n;i++){
        cin>>a[i];
    }
    for(int i=1;i<=n;i++){
        for(int j=i;j<=n;j++){
            int t[N]={0};
            for(int k=i;k<=j;k++){
                t[a[k]]++;
                if(t[a[k]]<=1){
                    cnt++;
                }
            }
        }
    }
    cout<<cnt;
    return 0;
}

问题分析：

时间复杂度过高： 您的代码使用了三重循环，时间复杂度为 O(N^3) 。对于 N \leq 2 \times 10^5 的数据规模，这个算法远远无法在合理时间内运行完成。
不必要的重复计算： 在每个子数组中，您都重新初始化数组 t 并计算子数组中不同元素的个数，这导致了大量的重复计算。

结论： 我们需要找到一个更高效的算法，将时间复杂度降低到 O(N \log N) 或更低。

二、改进算法的思路

1. 问题重新表述

目标： 计算所有子数组中不同元素的数量之和，即求：

S = \sum_{i=1}^{N} \sum_{j=i}^{N} f(i, j)

其中， f(i, j) 是子数组 A_i, A_{i+1}, \ldots, A_j 中不同元素的数量。

2. 算法设计

为了降低时间复杂度，我们需要找到一种线性或接近线性的算法。我们可以通过计算每个元素对总和的贡献来实现这一点。

关键思想：

元素的贡献： 对于数组中的每个元素，我们计算它作为新出现的不同元素时，对总和的贡献。
统计每个元素的贡献： 对于元素 v ，其在数组中的出现位置为 p_1, p_2, \ldots, p_k 。我们需要计算元素 v 在所有子数组中作为新出现的不同元素的总贡献。

3. 算法步骤

记录每个元素的出现位置：
- 创建一个映射 pos，将每个元素映射到其在数组中的所有出现位置。
计算每个元素的贡献：
- 对于每个元素 v ：
  - 获取其出现位置列表 positions。
  - 在 positions 的开头添加 0，末尾添加 N + 1 ，表示数组的开始和结束。
  - 对于 positions 中的每两个相邻位置 p_{i-1} 和 p_i ：
    - 计算左侧可能的起始位置数量：left = p_i - p_{i-1}。
    - 计算右侧可能的结束位置数量：right = N - p_i + 1。
    - 元素 v 在这些子数组中作为新出现的不同元素，对总和的贡献为 contribution = left * right。
  - 将每个 contribution 累加到总和 total 中。
计算总和：
- 对所有元素的贡献求和，得到最终的答案。

4. 算法复杂度

时间复杂度： O(N \log N) ，因为我们需要对每个元素的出现位置进行处理，且元素的种类数最多为 N 。
空间复杂度： O(N) ，用于存储元素的出现位置。

三、代码实现

#include <iostream>
#include <vector>
#include <unordered_map>
#include <algorithm>

using namespace std;

typedef long long ll;

int main() {
    int N;
    cin >> N;
    vector<int> A(N + 1);
    unordered_map<int, vector<int>> pos;

    // 读取数组并记录每个元素的出现位置
    for (int i = 1; i <= N; ++i) {
        cin >> A[i];
        pos[A[i]].push_back(i);
    }

    ll total = 0;
    // 对于每个元素，计算其贡献
    for (auto& entry : pos) {
        vector<int>& positions = entry.second;
        // 在开头添加0，在末尾添加N+1
        positions.insert(positions.begin(), 0);
        positions.push_back(N + 1);

        // 计算贡献
        for (size_t i = 1; i < positions.size() - 1; ++i) {
            ll left = positions[i] - positions[i - 1];
            ll right = N - positions[i] + 1;
            total += left * right;
        }
    }

    cout << total << endl;

    return 0;
}

四、代码解释

读取输入并记录元素出现位置：

unordered_map<int, vector<int>> pos;
for (int i = 1; i <= N; ++i) {
    cin >> A[i];
    pos[A[i]].push_back(i);
}

计算每个元素的贡献：
```
for (auto& entry : pos) {
    vector<int>& positions = entry.second;
    positions.insert(positions.begin(), 0);
    positions.push_back(N + 1);

    for (size_t i = 1; i < positions.size() - 1; ++i) {
        ll left = positions[i] - positions[i - 1];
        ll right = N - positions[i] + 1;
        total += left * right;
    }
}
```
- positions[i] - positions[i - 1] 计算了当前元素在前一次出现和本次出现之间的位置数量，表示左侧可能的起始位置数量。
- N - positions[i] + 1 计算了从当前位置到数组末尾的元素数量，表示右侧可能的结束位置数量。
- left * right 得到了当前元素作为新出现的不同元素时，对总和的贡献。
输出结果：
```
cout << total << endl;
```

五、样例测试

样例输入1：

3
1 2 2

计算过程：

元素1的出现位置：[1]
- positions = [0, 1, 4]
- 贡献：(1 - 0) * (3 - 1 + 1) = 1 * 3 = 3
元素2的出现位置：[2, 3]
- positions = [0, 2, 3, 4]
- 贡献：
  - (2 - 0) * (3 - 2 + 1) = 2 * 2 = 4
  - (3 - 2) * (3 - 3 + 1) = 1 * 1 = 1
总和：3 + 4 + 1 = 8

输出：

样例输入2：

9
5 4 2 2 3 2 4 4 1

您可以手动计算一下，或者直接运行代码，输出结果为：

六、总结

效率提升： 通过重新设计算法，我们将时间复杂度从 O(N^3) 降低到了 O(N \log N) ，对于题目给定的数据规模，能够在合理时间内运行。
算法关键点： 通过计算每个元素在不同子数组中作为新出现的不同元素的贡献，我们避免了对每个子数组进行显式的遍历。
适用场景： 这种方法适用于需要计算子数组中元素出现次数或其他基于元素位置的贡献的问题。

七、进一步优化

如果想要将时间复杂度降低到 O(N) ，可以考虑以下优化：

使用数组代替 unordered_map： 由于元素的值范围已知且不超过 N ，可以使用数组来存储每个元素的出现位置，避免哈希映射的开销。
预处理优化： 在读取输入时，就将元素的出现位置存储在数组中，避免额外的遍历。

但是在实际运行中，对于 N \leq 2 \times 10^5 的数据规模，当前的 O(N \log N) 算法已经足够高效。

八、完整代码

下面是使用数组优化后的完整代码：

#include <iostream>
#include <vector>
using namespace std;

typedef long long ll;
const int MAX_N = 200005;

int main() {
    int N;
    cin >> N;
    vector<int> A(N + 1);
    vector<vector<int>> pos(MAX_N);

    // 读取数组并记录每个元素的出现位置
    for (int i = 1; i <= N; ++i) {
        cin >> A[i];
        pos[A[i]].push_back(i);
    }

    ll total = 0;
    // 对于每个可能的元素值（1 到 N）
    for (int v = 1; v <= N; ++v) {
        if (pos[v].empty()) continue;
        vector<int>& positions = pos[v];
        positions.insert(positions.begin(), 0);
        positions.push_back(N + 1);

        for (size_t i = 1; i < positions.size() - 1; ++i) {
            ll left = positions[i] - positions[i - 1];
            ll right = N - positions[i] + 1;
            total += left * right;
        }
    }

    cout << total << endl;

    return 0;
}

说明：

数组 pos： 使用数组代替哈希映射，索引直接对应元素的值。
遍历范围优化： 只遍历有出现的元素，跳过空的 pos[v]。