CSP-S 2023 T2 一个很自然的想法

· · 题解

CSP-S 2023 T2 一个很自然的想法

考场上我花了两个多小时想的线性，这里分享一个非常好想的单 \log 做法。感谢 zhy 提供思路。

暴力 50 分就是枚举左端点，往一个方向入栈，如果栈的大小清空了就有解。（实际有 60？）

那么我们两个方向入栈，考虑 cdq 分治处理。

从 mid 到 l 不断往左移动指针，入左栈，把每个左栈版本的哈希值存下来。

从 mid+1 到 r 不断往右移动指针，入右栈，判断每个右栈版本的哈希值能匹配多少个左栈。

显然因为右栈等于左栈的时候可以消完。于是这道题就结束了。而且还能直接通过 CF1223F。

const I bas=200710241,N=2e6+10;
struct hashstack{
    I stk[N],top;LL vers[N];
    V clear(){top=0;}
    V push(I x){stk[++top]=x;vers[top]=vers[top-1]*bas+x;}
    V pop(){--top;}
    LL curv(){return vers[top];}
    V pushback(I x){
        if(stk[top]==x)pop();
        else push(x);}
}S;
gp_hash_table<LL,I>M;
I n,c[N];
LL sol(I l,I r){
    if(l>=r)return 0;
    I mid=l+r>>1;
    S.clear();M.clear();
    for(I i=mid;i>=l;--i)
        S.pushback(c[i]),
        ++M[S.curv()];
    S.clear();LL ans=0;
    fo(i,mid+1,r){
        S.pushback(c[i]);
        if(M.find(S.curv())!=M.end())
            ans+=M[S.curv()];}
    return ans+sol(l,mid)+sol(mid+1,r);}