526互联

Codeforces Round 905 (Div. 2) C. You Are So Beautiful（数据结构）

发布时间 2023-10-23 20:40:13作者: ikunhuaji

Codeforces Round 905 (Div. 2) C. You Are So Beautiful

定义：

设数组 abcd

  • 子数组定义：从原数组砍去前面若干元素，后边若干元素，剩余的数组。如：bc、ab
  • 子序列定义：从原数组删除若干元素，剩余元素拼凑一起，组成的数组。如：ac、bd

思路：

作为结果的连续子数组，如果他为 [ \(a_l\)，……，\(a_r\) ]

则在 l 之前不能出现和\(a_l\)相同的数，否则子序列会相同

同理，r 之后不能出现和\(a_r\)相同的数

因此，用num存储当前经过的元素为相同元素的开头位置的个数

当遍历到 \(a_i\) 为\(a_i\)相同元素结尾时，前面的所有开头元素都可作为开头，\(a_i\)为结尾，ans+=num

#define int long long
#define ld long double

using namespace std;

const int N = 1e5 + 10;

int t, n, k, m;
int x, y, z;
int a[N];

void solve()
{
    cin >> n;
    map<int, int>fr, ed;
    for (int i = 1; i <= n; i++)
    {
        cin >> a[i];
        x = a[i];
        if (!fr[x])
        {
            fr[x] = i;
            ed[x] = i;
        }
        else
        {
            ed[x] = i;
        }
    }

    int num = 0, ans = 0;

    for (int i = 1; i <= n; i++)
    {
        x = a[i];
        if (fr[x] == i)
        {
            ++num;
        }
        if (ed[x] == i)
        {
            ans += num;
        }
    }

    cout << ans << endl;
}

signed main()
{
    //t = 1;
    cin >> t;
    while (t--)
    {
        solve();
    }

    return 0;
}