Stack Exterminable Arrays

prologue

CSPS2023 T2 原题，什么成分我就不多说了。（考场上没写出来的菜鱼，想到栈了然后算法假了，寄）

analysis

（虽然这样不对，但是我还是想撇一下我的错解）

错解

我们开一个栈，每一个元素进来看和栈顶元素一样不一样，如果不一样，就入栈，否则就 \(ans + cnt\)，\(cnt\) 表示我们的栈有多少次是空的。

正解

我们同样是开一个栈，但是我们这个栈用来存储两个位置 \((now, nw)\) 表示的是这个到目前为止的状态，这个状态为了防止重复，所以我们对这个状态进行一个哈希，为了减小冲突，我们还可以对这两个采取不同的哈希方式。每次进行累加这个状态就好了。

code time

// author : Carp

#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define fom(i, a) for(int i=a; i; -- i)
#define foa(i, a, b) for(int i=a; i < b; ++ i)
#define fos(i, a, b) for(int i=a; i <= b; ++ i)
#define fop(i, a, b) for(int i=a; i >= b; -- i)
#define ws putchar(' ')
#define wl putchar('\n')

template <class T> inline void waw(T x)
{
    if(x > 9) waw(x / 10);
    putchar(x % 10 ^ 48);
}

template <class T> inline void ww(T x)
{
    if(x < 0) x = ~x + 1, putchar('-');
    waw(x);
}

template <class T> inline void read(T &res)
{
    char ch = getchar(); bool f = 0; res = 0;
    for(; !isdigit(ch); ch = getchar()) f |= ch == '-';
    for(; isdigit(ch); ch = getchar()) res = (res << 1) + (res << 3) + (ch ^ 48);
    res = f ? ~res + 1 : res;
}

const int N = 3e5 + 10;

const ll  P = 998244353;

typedef pair<ll, ll> pll;

int n, a[N], stk[N];

ll hsh[N];

map<pll, ll> sta;

mt19937 rnd(15617);

inline void solve()
{
    read(n); 
    
    fos(i, 1, n) read(a[i]);

    fos(i, 1, n + 5) hsh[i] = rnd();

    int top = 0, now = 0, nw = 0;
    
    ll ans = 0;

    sta.clear();

    sta[{0, 0}] = 1;

    fos(i, 1, n)
    {
        if(stk[top] == a[i] && top) -- top, now += (hsh[top + 1] * a[i]) % P, nw ^= (hsh[top + 1] * a[i]) % P;
        else stk[++ top] = a[i], now -= (hsh[top] * a[i]) % P, nw ^= (hsh[top] * a[i]) % P;

        ans += sta[{now, nw}];
        sta[{now, nw}] ++ ;
    }

    ww(ans), wl;
}

int main() { ll T; read(T); while(T -- ) solve(); return 0; }