CF1223F Stack Exterminable Arrays 题解

zifanwang · 2023-10-24 18:39:15 · 题解

这题是 CSP-S 2023 T2 的加强版。

区间 [l,r] 可以消除当且仅当 a_l=a_r 且 [l+1,r-1] 可消除，或存在一个数 k(l\le k\le r) 满足 [l,k],[k+1,r] 都可消除。

所以一个可消除区间肯定是由若干个左右端点颜色（a_i 是第 i 个点的颜色）相同的可消除连续子区间拼起来的。

考虑对于每个右端点 i 求出最近的左端点使得对应子区间满足条件，记为 l_i。记 f_i 为 i 作为右端点的合法子区间个数，那么答案就是 \sum f_i，易得 f_i=f_{l_i-1}+1。

很明显 a_{l_i}=a_i，不然就不满足左端点最靠右。由此显然可得区间 [l_i+1,i-1] 可消除，也就是说从 p=i-1 开始不断地跳 p=l_p-1，最终一定可以跳到 p=l_i。

于是可以对每个点用一个 map 维护每种颜色往左边跳到的第一个这种颜色的点的编号。每个点 i 的 map 都需要继承 l_i-1 的 map，可以直接 swap，因为后面 l_i-1 的 map 就不会再用到了。

时间复杂度 O(n\log n)。

参考代码：

#include<bits/stdc++.h>
#define ll long long
#define mxn 300003
#define rep(i,a,b) for(int i=a;i<=b;++i)
#define rept(i,a,b) for(int i=a;i<b;++i)
using namespace std;
int q,n,a[mxn],p[mxn];
ll ans,f[mxn];
map<int,int>mp[mxn];
signed main(){
    scanf("%d",&q);
    while(q--){
        scanf("%d",&n);
        rep(i,1,n)scanf("%d",&a[i]),mp[i].clear(),f[i]=p[i]=0;
        ans=0;
        rep(i,1,n){
            auto it=mp[i-1].find(a[i]);
            if(it!=mp[i-1].end()){
                p[i]=it->second-1;
                f[i]=f[p[i]]+1,ans+=f[i];
                swap(mp[i],mp[p[i]]);
            }
            mp[i][a[i]]=i;
        }
        printf("%lld\n",ans);
    }
    return 0;
}