题意
挺神仙的。首先$60$分暴力是比较好打的。
就是枚举左端点，看右端点能否是$0$
但是这样肯定是过不了的，假如我们只枚举一次，把得到的栈记录下来
那么若区间$(l, r)$是可行的，那么$s_{l - } = s_r$，证明自己yy一下吧。。
然后就是字符串hash乱搞了。。
代码语言：javascript复制#include<cstdio>
#include<algorithm>
#include<queue>
#include<cstring>
#include<map>
#define LL long long
#define ull unsigned long long
using namespace std;
const int MAXN = 1e6 10, mod = 1e9 7;
inline LL read() {
char c = getchar(); LL x = 0, f = 1;
while(c < '0' || c > '9') {if(c == '-') f = -1; c = getchar();}
while(c >= '0' && c <= '9') x = x * 10 c - '0', c = getchar();
return x * f;
}
char a[MAXN], s[MAXN];
int top = 0;
ull base = 12, base2 = 233, po1[MAXN], po2[MAXN];
map<ull, LL> mp;
int main() {
scanf("%s", a 1);
LL N = strlen(a 1), ans = 0;
ull sum = 0, sum2 = 0;
mp[0] = 1; po1[0] = 1; po2[0] = 1;
for(int i = 1; i <= N; i ) po1[i] = po1[i - 1] * base, po2[i] = po2[i - 1] * base2;
for(int i = 1; i <= N; i ) {
if(top && a[i] == s[top]) {
top--;
sum -= po1[top] * (a[i] - 'a' 1);
sum2 -= po2[top] * (a[i] - 'a' 1);
}
else {
sum = po1[top] * (a[i] - 'a' 1);
sum2 = po2[top] * (a[i] - 'a' 1) ;
s[ top] = a[i];
}
ans = mp[(sum << 5) sum2];
mp[(sum << 5) sum2] ;
// printf("%dn", ans);
}
printf("%lld", ans);
return 0;
}
/*
abaababababbbbbaavbaaaabbbaaaabbabbbaabbabbb
*/
