主要思路

刚开始看到分治的标签就下定决心用分治做，没一会发现信息非常难利用就弃疗了。考虑用类似于 KMP 的 AC 自动机的方法完成本题。

首先设置\(dp[i]\)为以\(i\)开头向右延伸的答案，那么我们往左的时候可以合并之，并设置\(nxt[i]\)来进行跳跃；由于得到\(nxt\)数组的过程暴力做时间复杂度会 GG，所以我们可以使用类似 AC 自动机的方式用 Map 合并信息：交换\(nxt[i]+1\)位置的 Map 并设置当前位置。最后做 DP 即可。

代码

// CF1240D.cpp
#include <bits/stdc++.h>
#define ll long long

using namespace std;

const int MAX_N = 3e5 + 200;

int q, n, ai[MAX_N], nxt[MAX_N], dp[MAX_N];
map<int, int> nxt_map[MAX_N];
ll ans;

int main()
{
    scanf("%d", &q);
    while (q--)
    {
        scanf("%d", &n), ans = 0;
        for (int i = 1; i <= n; i++)
            scanf("%d", &ai[i]);
        for (int i = 1; i <= n + 2; i++)
            nxt[i] = -1, dp[i] = 0, nxt_map[i].clear();
        for (int i = n; i >= 1; i--)
        {
            if (nxt_map[i + 1].count(ai[i]))
            {
                int pos = nxt_map[i + 1][ai[i]];
                if (pos <= n && ai[i] == ai[pos])
                {
                    nxt[i] = pos, swap(nxt_map[i], nxt_map[pos + 1]);
                    if (pos <= n - 1)
                        nxt_map[i][ai[pos + 1]] = pos + 1;
                }
            }
            nxt_map[i][ai[i]] = i;
        }
        for (int i = n; i >= 1; i--)
            if (nxt[i] != -1)
                dp[i] = 1 + dp[nxt[i] + 1], ans += dp[i];
        printf("%lld\n", ans);
    }
    return 0;
}