题意:
对于一个01字符串，如果将这个字符串0和1取反后，再将整个串反过来和原串一样，就称作“反对称”字符串。比如00001111和010101就是反对称的，1001就不是。
现在给出一个长度为N的01字符串，求它有多少个子串是反对称的。
数据范围：N小于等于5e5。
题解：类似于回文串，不过匹配的是按照不相等来匹配，利用manacher的思想可以O（n）过。
代码：
#include<bits/stdc++.h>
using namespace std;
const int maxn=1e6+50;
char s[maxn];
char a[maxn];
int hw[maxn];//数组最远扩展的距离。
int cnt;int n;
void change()
{s[1]='~';s[2]='#';cnt=2;int len=strlen(a+1);for(int i=1;i<=len;i++){s[++cnt]=a[i];s[++cnt]='#';}s[++cnt]='!';
}
void manacher()
{change();int maxright=0;int mid=0;for(int i=2;i<=cnt-1;i++){if(i%2==1){hw[i]=0;continue;}if(i<maxright){hw[i]=min(hw[mid*2-i],maxright-i);}else hw[i]=1;// cout<<i<<"...."<<hw[i]<<endl;while(s[i+hw[i]]=='#'&&s[i-hw[i]]=='#'||((s[i+hw[i]]^s[i-hw[i]])==1)){++hw[i];}if(hw[i]+i>maxright){maxright=i+hw[i];mid=i;}}
}
int main()
{scanf("%d",&n);scanf("%s",a+1);manacher();long long sum=0;
/* for(int i=1;i<=cnt;i++){cout<<i<<"---"<<s[i]<<"----"<<hw[i]<<endl;}*/for(int i=2;i<=cnt-1;i+=2){sum+=(long long)(hw[i]/2);}printf("%lld\n",sum);return 0;}