题目描述

难度分:$1400$

输入$T(\leq 10^4)$表示$T$组数据。所有数据的$n$之和$\leq 2 \times 10^5$。每组数据输入$n(1 \leq n \leq 10^5)$和长为$n$的数组$a(1 \leq a[i] \leq 10^9)$。

输出$a$有多少个非空连续子数组$b$，满足$b$是$a$的唯一子序列（不存在其他的子序列等于$b$）。

输入样例

6
1
1
2
1 1
3
1 2 1
4
2 3 2 1
5
4 5 4 5 4
10
1 7 7 2 3 4 3 2 1 100

输出样例

1
1
4
7
4
28

算法

思维题

感觉还是蛮难的，关键是分析唯一需要满足什么性质。观察一下样例就可以发现，只有第一次出现的数值$x$和最后一次出现的数值$y$之间这一段子数组才可能唯一，否则如果左边还有$x$，第一个位置就可以替换成更左边的$x$，如果右边还有$y$，最后一个位置就可以替换成更右边的$y$，且不影响子序列的内容。

先预处理出每个元素值第一次的出现位置和最后一次的出现位置，存入到两个哈希表$first$和$last$中，并将$last$中的索引都转存到一个数组$pos$中排好序。然后遍历$i \in [1,n]$，如果$first[a[i]]=i$，就开始统计以$a[i]$开头的子数组对应的子序列有多少个满足在整个数组中只出现一次。这时候二分一下$pos$数组，看看有多少个最后出现索引$j \geq i$，这些$j$所决定的子数组$[i,j]$都能满足相应子序列在整个数组中只出现一次。

复杂度分析

时间复杂度

预处理出两个哈希表$first$和$last$只需要遍历一遍数组，时间复杂度$O(n)$。遍历一遍$last$表，预处理出$pos$数组时间复杂度$O(n)$，对$pos$数组排序时间复杂度$O(nlog_2n)$。最后遍历一遍数组求答案，对于每个满足$first[a[i]]=i$的$i$，都要在$pos$数组上做一次二分查找，时间复杂度为$O(log_2n)$。

综上，整个算法的时间复杂度为$O(nlog_2n)$。

空间复杂度

空间瓶颈在于两个哈希表$first$和$last$，以及$pos$数组，它们都是线性空间。因此，整个算法的额外空间复杂度为$O(n)$。

C++ 代码

#include <bits/stdc++.h>

using namespace std;
typedef long long LL;

const int N = 100010;
int T, n, a[N];

struct custom_hash {
    static uint64_t splitmix64(uint64_t x) {
        x += 0x9e3779b97f4a7c15;
        x = (x ^ (x >> 30)) * 0xbf58476d1ce4e5b9;
        x = (x ^ (x >> 27)) * 0x94d049bb133111eb;
        return x ^ (x >> 31);
    }

    size_t operator()(uint64_t x) const {
        static const uint64_t FIXED_RANDOM = chrono::steady_clock::now().time_since_epoch().count();
        return splitmix64(x + FIXED_RANDOM);
    }
};

int main() {
    scanf("%d", &T);
    while(T--) {
        scanf("%d", &n);
        unordered_map<int, int, custom_hash> last, first;
        for(int i = 1; i <= n; i++) {
            scanf("%d", &a[i]);
            last[a[i]] = i;
            if(!first.count(a[i])) first[a[i]] = i;
        }
        vector<int> pos;
        for(auto&[num, x]: last) {
            pos.push_back(x);
        }
        sort(pos.begin(), pos.end());
        LL ans = 0;
        for(int i = 1; i <= n; i++) {
            if(i == first[a[i]]) {
                ans += pos.size() - (lower_bound(pos.begin(), pos.end(), i) - pos.begin());
            }
        }
        printf("%lld\n", ans);
    }
    return 0;
}