HDU 学数数导致的

题目解析

首先，数对是有序的，<1,2>和<2,1>被视为不同的两组数字。

其次，数对<p,q>的p和q可以相等。

子序列为 p 0 p q，观察到，中间要出现一个0。那么，我们只需要找到第一个 p 满足与前一个 p 中间隔了最少一个0，并记录它的位置。那么，在它位置之后出现的所有正整数组成的集合的大小，就是 p 对答案的贡献。

那么只需要先把满足条件的p的位置都求出来，然后按照从大到小的顺序排序一下，从后往前维护一个集合，然后遍历到p的位置的时候更新答案值，即可。

代码实现

#include <iostream>
#include <map>
#include <set>
#include <vector>
#include <algorithm>
#include <stack>
#include <queue>
#include <utility>
#include <cmath>
#include <cstring>
#include <string>
using namespace std;
long long t, n, a[1000010], sum0, ans, num;
struct node {
    long long num0;
    long long pos;
}e[1000010];
vector<long long>pos;
bool vis[1000010] = {};
int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    cin >> t;
    while (t--) {
        sum0 = 0;
        ans = 0;
        num = 0;
        pos.clear();
        for (int i = 0; i < 1000010; i++) {
            vis[i] = false;
            e[i].pos = -1;
        }
        vis[0] = true;
        cin >> n;
        for (int i = 0; i < n; i++) {
            cin >> a[i];
            if (a[i] == 0)sum0++;//记录0出现过的次数
            else if (e[a[i]].pos == -1) {//如果a[i]之前没出现过，则记录位置和前导0的数量
                e[a[i]].pos = i;
                e[a[i]].num0 = sum0;
            }
            else if (e[a[i]].pos >= 0 && e[a[i]].num0 != sum0) {//如果出现过，则比较前导0的数量是否相等。若不等，则说明之间出现0，记录位置
                pos.push_back(i);
                e[a[i]].pos = -2;//打上标记，防止再被处理
            }
        }
        sort(pos.begin(), pos.end());//对位置进行排序
        for (int i = pos.size() - 1, j = n - 1; i >= 0; j--) {
            if (j == pos[i]) {//碰到符合的位置，则更新答案值
                ans += num;
                i--;
            }
            if (!vis[a[j]]) {//之前没遇到过，则放入集合中，更新集合大小
                vis[a[j]] = true;
                num++;
            }
        }
        cout << ans << "\n";
    }
}