挺神仙的。首先$60$分暴力是比较好打的。
就是枚举左端点,看右端点能否是$0$
但是这样肯定是过不了的,假如我们只枚举一次,把得到的栈记录下来
那么若区间$(l, r)$是可行的,那么$s_{l - } = s_r$,证明自己yy一下吧。。
然后就是字符串hash乱搞了。。
#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("%d\n", ans);
}
printf("%lld", ans);
return 0;
}
/*
abaababababbbbbaavbaaaabbbaaaabbabbbaabbabbb
*/