思路：从头到尾用栈扫一遍，每到一个字符和栈顶能消除就消除，否则入栈，记录扫到每个位置栈内的状态，最后根据每种状态的出现次数得到答案（区间 $[l,r]$ 合法当且仅当栈内的状态 $s_{l-1}=s_r$）。

代码：

#include<bits/stdc++.h>
using namespace std;
unordered_map<string,int> mp;
string s,stk;
int n,ans;
int main()
{
	ios::sync_with_stdio(false);
	cin.tie(NULL);
	cin>>n;cin>>s;
	mp[""]++;
	for(auto i=s.begin();i!=s.end();i++)
	{
		auto ed=stk.end();
		if(ed!=stk.begin())//栈不空 
		{
			ed--;
			if((*ed)==*i) stk.erase(ed),mp[stk]++;//可以和栈顶消除
			else stk+=*i,mp[stk]++;//不能消除，入栈
		}
		else stk+=*i,mp[stk]++;//直接入栈
	}
		
	for(auto i=mp.begin();i!=mp.end();i++) 
		ans+=(*i).second*((*i).second-1)/2;
	cout<<ans;
	return 0;
}

问题

1. 为什么会WA + MLE
2. 本地运行结果为什么和在线 ide 不一样（本地无论如何都过不了样例二三四，样例二输出 32613，在线 ide 就是对的）。