对于一个01字符串，如果将这个字符串0和1取反后，再将整个串反过来和原串一样，就称作“反对称”字符串。比如00001111和010101就是反对称的，1001就不是。
现在给出一个长度为N的01字符串，求它有多少个子串是反对称的。

第一行一个正整数N (N <= 500,000)。第二行一个长度为N的01字符串。

一个正整数，表示反对称子串的个数。

鸣谢 JZP

 1 #include <cstdio> 2  3 const int siz = 1000005; 4  5 int n; 6 int s[siz]; 7 int r[siz]; 8 char str[siz]; 9 10 inline int min(int a, int b)11 {12     return a < b ? a : b;13 }14 15 inline bool check(int a, int b)16 {17     return18         (a == 0 && b == 1)19     ||  (a == 1 && b == 0)20     ||  (a == 3 && b == 3);21 }22 23 signed main(void)24 {25     scanf("%d%s", &n, str + 1);26     27     /*<--- Prework --->*/ 28     29     30     for (int i = 1; i <= n; ++i)31     {32         static int tot = 0;33         s[++tot] = 3;34         s[++tot] = str[i] - ‘0‘;35     }36     37     n = 2*n + 1;38     39     s[n] = 3;40     s[0] = 4;41     s[n + 1] = 4;42     43     /*<--- Manacher --->*/44     45     for (int i = 1; i <= n; i += 2)46     {47         static int maxi = 0, id = 0;48         49         if (i <= maxi)50             r[i] = min(maxi - i + 1, r[2*id - i]);51         else52             r[i] = 1;53         54         while (check(s[i + r[i]], s[i - r[i]]))55             ++r[i];56         57         if (maxi < r[i] + i - 1)58             maxi = r[i] + i - 1, id = i;59     }60     61     /*<--- Calculate --->*/62     63     long long ans = 0LL;64     65     for (int i = 1; i <= n; i += 2)66         ans += (r[i] - 1) >> 1;67         68     printf("%lld\n", ans);69 }