比赛时并没有搞出来qwq

题目中的两种变换可以当作是字符 1 或 0 的一次运动。而我开始只去考虑了 1 的运动，而忽视了 0 的运动。实际上 0 的运动规律是更容易找到的。

观察到 011\to 110 可以看作 0 在右边有连续两个 1 时右移 2 位，而 110\to 011 可以看作 0 在左边有连续两个 1 时左移 2 位。考虑整个字符串的变换，发现两个 0 是不可以相互跨越的，并且每个 0 的下标的奇偶性在变换中保持不变。那么对于两个等长的子串，若它们满足以下两个条件，则可以互相通过变换达到：

• 0 的个数相等；
• 第 i 个 0 在这两个子串中的下标奇偶性对应相同。

于是我们只需要对 0 哈希它的下标奇偶性。可以先搞出它在原串中的奇偶性，再对应左端点的奇偶性分别哈希两次。

代码：

#include <cstdio>
const int MAXN=220000;
const int BASE=19260817;
const int MOD=1004535809;
char a[MAXN];
int powb[MAXN];
int cnt[MAXN], h1[MAXN], h2[MAXN];
inline int query(int l, int r)
{
    if (l&1) return (h1[r]-1ll*h1[l-1]*powb[cnt[r]-cnt[l-1]]%MOD+MOD)%MOD;
    else return (h2[r]-1ll*h2[l-1]*powb[cnt[r]-cnt[l-1]]%MOD+MOD)%MOD;
}
int main()
{
//  freopen("D.in", "r", stdin);
//  freopen("D.out", "w", stdout);
    int n, q;
    scanf("%d%s", &n, a+1);
    powb[0]=1;
    for (int i=1; i<=n; i++)
    {
        powb[i]=1ll*powb[i-1]*BASE%MOD;
        cnt[i]=cnt[i-1]+(a[i]=='0');
        if (a[i]=='0')
        {
            h1[i]=(1ll*h1[i-1]*BASE+(i&1)+1)%MOD;
            h2[i]=(1ll*h2[i-1]*BASE+(i&1^1)+1)%MOD;
        }
        else h1[i]=h1[i-1], h2[i]=h2[i-1];
    }
    scanf("%d", &q);
    while (q--)
    {
        int l, r, len;
        scanf("%d%d%d", &l, &r, &len);
        if (query(l, l+len-1)==query(r, r+len-1)) puts("Yes");
        else puts("No");
    }
    return 0;
}