CF1223F Stack Exterminable Arrays

传送门

Solution

从 $1$ 到 $n$ 枚举数字，对于当前数字，若与栈顶元素相同，则弹出栈顶元素，否则压入当前数字。随后将当前栈的状态通过哈希映射到 map 数组中。map 数组负责统计该状态出现的次数。

若枚举到位置 $j$ 和 $i$ 时栈的状态相同，则说明序列 $[j+1,i]$ 是可消除的。因此以 $i$ 为结尾的可消除序列的数量就是合法的 $j$ 的数量。

本题采用双哈希防止冲突。答案需要开 long long。

Code

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;

const ll N = 5e5 + 10, mod = 1e9 + 7;

ll ba[N], bb[N], n, ha, hb, ans, T;
map<pair<ll, ll>, ll> mp;
stack<ll> st;

void solve()
{
	scanf("%lld", &n);
	ha = hb = ans = 0;
	mp.clear();
	mp[make_pair(ha, hb)]++;
	for (int i = 1; i <= n; i++) {
		ll x;
		scanf("%lld", &x);
		if (st.size() && st.top() == x) {
			ha = (ha - x * ba[st.size()] % mod + mod) % mod;
			hb = (hb - x * bb[st.size()] % mod + mod) % mod;
			st.pop();
		} else {
			st.push(x);
			ha = (ha + x * ba[st.size()] % mod + mod) % mod;
			hb = (hb + x * bb[st.size()] % mod + mod) % mod;
		}
		ans += mp[make_pair(ha, hb)];
		mp[make_pair(ha, hb)]++;
	}
	printf("%lld\n", ans);
	while (st.size()) st.pop();
}

int main()
{
	scanf("%lld", &T);
	ba[0] = bb[0] = 1;
	for (int i = 1; i <= 3e5; i++)
		ba[i] = ba[i - 1] * 127 % mod;
	for (int i = 1; i <= 3e5; i++)
		bb[i] = bb[i - 1] * 129 % mod;
	while (T--) solve();
	return 0;
}