1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
| #include<bits/stdc++.h>
#define maxn 1000005
#define ll long long
#define put() putchar('\n')
using namespace std;
inline void read(int &x){
int f=1;x=0;char c=getchar();
while (c<'0'||c>'9') {if (c=='-') f=-1;c=getchar();}
while (c>='0'&&c<='9') {x=x*10+c-'0';c=getchar();}
x*=f;
}
int n;
int a[maxn],d[maxn];
inline void manacher(int n){
int i,mx,mid;
for (i=1;i<=n;i+=2) d[i]=1;
for (mx=mid=0,i=1;i<=n;i++) {
if (i<=mx) d[i]=min(d[mid*2-i],mx-i+1);
while (a[i-d[i]]+a[i+d[i]]==1||(a[i-d[i]]==2&&a[i+d[i]]==2)) d[i]++;
if (mx<i+d[i]) mx=i+d[i]-1,mid=i;
}
}
signed main(void){
freopen("1.in","r",stdin);
int i,m;ll ans=0;char ch;
read(n);a[0]=-1e8;a[++m]=2;cin>>ch;
for (i=1;i<=n;i++) a[++m]=ch-'0',ch=getchar(),a[++m]=2;a[++m]=1e9;
manacher(m);
for (i=1;i<=m;i++) if (i%2==1) ans+=(d[i]-1)/2;
printf("%lld",ans);
return 0;
}
|