CF1223F题解

Biuld · 2023-10-23 10:49:08 · 题解

考场上脑残了，原思路有点小问题。

原思路：
令 sum_i 为以 i 为结尾的答案个数
对于每个 a[i]，找到每个 a[j]==a[i] 且 j<i，若区间 [j+1,i-1] 可完美消除，则 sum[i]+=1+sum[j-1]。

正解：
一个显然的结论：若区间 [x,y] 可消并区间 [y+1,z] 可消，则区间 [x,z] 可消。
实际上它反过来也是成立的：若区间 [x,z] 可消并区间 [x,y] 可消 (y<z)，则区间 [y+1,z] 可消。
（考场没想出这点

所以我们在计算 sum_i 时不必找出所有满足条件的 j，只需找到其中最大的一个即可。

则令 f_i 为满足区间 [f_i,i] 可消的最大的一个。显然有 a[f[i]]==a[i] 且区间 [f_i+1,i-1] 同样可消。

我们的问题就来到了如何求解 f，一个较为暴力的思路为：

令 now=i-1，从 now 开始找完美可消区间，即 [f_{now},now]，若存在，则使 now=f[now]-1，继续查找，直至 a[now]==a[i] 为止，并 f[i]=now 。

代码如下：

for(int i = 1; i <= n; ++ i){
    int now = i - 1;
    while(now > 0 && a[now] != a[i]){
        now = f[now] - 1;
    }
    if(now > 0){
    //若没有满足的区间是会出现 now<=0 的情况
        f[i] = now;
    }
}

明显，这是会 TLE 的，那么如何简化这查找 f 的过程呢。

我们定义一个 map<int,int> mp[N]， mp[i][j] 记录一个 lst ，满足区间 [lst+1,i] 可消且 a[lst]==j。我们查找时只需 f[i]=mp[i-1][a[i]] 即可。

关于 mp 的求解，显然的， mp[i][a[i]]=i; 发现若有区间 [x,y] 可消，则 mp[y] 可直接顺承 mp[x-1]，可以使用 swap 快速实现。

完整代码：

#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N = 3e5 + 5;

int T;

int n, a[N];

map<int, int> mp[N];

int sum[N];
int ans;

signed main(){
    ios::sync_with_stdio(false);

    cin >> T;

    while(T --){
        cin >> n;

        for(int i = 1; i <= n; ++ i){
            cin >> a[i];
            sum[i] = 0;
            mp[i].clear();
        } ans = 0;

        for(int i = 1; i <= n; ++ i){
            int j = mp[i - 1][a[i]];
            swap(mp[j - 1], mp[i]);

            if(j > 0){
                sum[i] = sum[j - 1] + 1;
                ans += sum[i];
            }

            mp[i][a[i]] = i;
        }

        cout << ans << '\n';
    }

    return 0;
}