QwQ和01串

发表于 2021-09-01 更新于 2026-08-08 分类于 algorithm 本文字数： 1.3k 阅读时长 ≈ 5 分钟

Description

QwQ是所有`01`串的控制者，但因为`0`是虚的，`1`才是实的，所以QwQ的遥控器只能控制`1`而不能直接控制`0`。

不幸的是，QwQ的遥控器坏了，控制力有所衰减，只能必须是连续的三个1才能被QwQ所控制。

对于一个01串，可以对它实施这样一个操作：选择中三个连续的1，把这三位向前或向后移动任意多位。

比如说这样： 001110110010 000111110010

或者这样：001110110010 111000110010

如果串可以通过QwQ的若干次操作得到，QwQ就认为和是相等的。

有一天QwQ终于发现了宇宙的本质就是一个长度为的01串但大部分人并不能理解这个神奇的宇宙,于是他们向01串的造物主QwQ问了个问题，每个问题的形式如下：中的第位到第位所组成的子串是否等于中的第位到第位所组成的子串？

Input

第一行输入2个正整数

表示宇宙串

的长度和询问次数

第二行输入1个长度为的01串表示QwQ对整个宇宙的理解。

接下来qq行每行四个正整数，表示每个询问。

题目保证对于每个询问，,且

Output

对于每个询问，输出一行`Yes`或`No`。

一开始的做法是先求前缀和然后找0的位置并用辅助数组jl[]记录当前k字符上一'0'的索引，若k字符为'0'则记录其本身的索引

然后7.8.9的测试点就爆掉了

最后AC的做法是用BKDR_hash来回应问询，加上快读到70ms

#include <bits/stdc++.h>

#define LL long long
#define f(i, a, b) for (int i = a; i <= b; i++)
#define IN freopen("in.txt", "r", stdin)
#define OUT freopen("out.txt", "w", stdout)

const LL B = 13331;
const LL M = 33951943;
const LL BA = 233;

char s[200087];
LL sum[200087], jl[200087], rank[200087], bk[200087], hash_at[200087]; //back to index
int n, q, aa, bb, cc, dd;

typedef unsigned long long ull;
ull hashs[200087], po[200087];
struct FastIO
{
    static const int S = 5 << 20; //MB
    int wpos;
    char wbuf[S];
    FastIO() : wpos(0) {}
    inline int xchar()
    {
        static char buf[S];
        static int len = 0, pos = 0;
        if (pos == len)
            pos = 0, len = fread(buf, 1, S, stdin);
        if (pos == len)
            return -1;
        return buf[pos++];
    }
    inline int xint()
    {
        int s = 1, c = xchar(), x = 0;
        while (c <= 32)
            c = xchar();
        if (c == '-')
            s = -1, c = xchar();
        for (; '0' <= c && c <= '9'; c = xchar())
            x = x * 10 + c - '0';
        return x * s;
    }
    inline void xstring(char *s)
    {
        int c = xchar();
        while (c <= 32)
            c = xchar();
        for (; c > 32; c = xchar())
            *s++ = c;
        *s = 0;
    }
    inline void wll(LL x)
    {
        if (x < 0)
            wchar('-'), x = -x;

        char s[30];
        int n = 0;
        while (x || !n)
            s[n++] = '0' + x % 10, x /= 10;
        while (n--)
            wchar(s[n]);
    }
    inline void wchar(int x)
    {
        if (wpos == S)
            fwrite(wbuf, 1, S, stdout), wpos = 0;
        wbuf[wpos++] = x;
    }
    inline void wstring(const char *s)
    {
        while (*s)
            wchar(*s++);
    }
    ~FastIO()
    {
        if (wpos)
            fwrite(wbuf, 1, wpos, stdout), wpos = 0;
    }
} io;

LL quikpower(LL b)
{
    LL ans = 1, base = BA;
    while (b > 0)
    {
        if (b & 1)
        {
            ans *= base;
            ans %= M;
        }
        base *= base;
        base %= M;
        b >>= 1;
    }
    return ans;
}

void sums()
{
    sum[1] = s[0] - '0';
    jl[1] = 1;
    f(i, 2, n)
    {
        if (s[i - 1] == '0')
            jl[i] = i;
        else
            jl[i] = jl[i - 1];
        sum[i] = sum[i - 1] + s[i - 1] - '0';
    }
    int sum_0 = n - sum[n], judge = n; //sum_0::0的个数
    //io.wll(sum_0);
    for (int cnt = sum_0; cnt > 0; cnt--)
    {
        bk[cnt] = jl[judge];   //第cnt个0的index
        rank[jl[judge]] = cnt; //0-index to cnt
        judge = jl[judge] - 1;
    }
}

void hash_init()
{
    int sum_0 = n - sum[n];
    po[0] = 1;
    po[1] = B;
    hashs[bk[1]] = (sum[bk[1]] - sum[0]) % 3; //第一个0
    hash_at[bk[1]] = (sum[bk[1]] - sum[0]) % 3;
    for (int k = 2; k <= sum_0; k++)
    {
        hashs[bk[k]] = ((sum[bk[k]] - sum[bk[k - 1]]) % 3 + hashs[bk[k - 1]] * B);
        hash_at[bk[k]] = ((sum[bk[k]] - sum[bk[k - 1]]) % 3 + hash_at[bk[k - 1]] * BA) % M;
        po[k] = po[k - 1] * B;
    }
}

LL gethash2(int l, int r)
{
    if (rank[l] == 1)
        return hash_at[r];
    return (hash_at[r] + M - hash_at[bk[rank[l] - 1]] * quikpower(rank[r] - rank[l] + 1) % M) % M;
}

LL gethash(int l, int r)
{
    if (rank[l] == 1)
        return hashs[r];
    return (hashs[r] - hashs[bk[rank[l] - 1]] * po[rank[r] - rank[l] + 1]);
}

int check2(int a, int b, int c, int d)
{
    if (sum[b] - sum[a - 1] != sum[d] - sum[c - 1])
    {
        io.wstring("No\n");
        return 0;
    }
    int x = jl[b], y = jl[d];
    while (x >= a && y >= c)
    {
        if (abs(sum[b] - sum[x] - sum[d] + sum[y]) % 3)
        {
            io.wstring("No\n");
            return 0;
        }
        else
        {
            x = jl[x - 1];
            y = jl[y - 1];
        }
    }
    io.wstring("Yes\n");
    return 0;
}

void check(int a, int b, int c, int d)
{
    if (b - a + 1 - sum[b] + sum[a - 1] < 2)
    {
        check2(a, b, c, d);
        return;
    }
    if (sum[b] - sum[a - 1] != sum[d] - sum[c - 1] || ((abs(sum[b] - sum[jl[b]] - sum[d] + sum[jl[d]]) % 3) && jl[b] >= a && jl[d] >= c))
    {
        io.wstring("No\n");
        return;
    }
    int star = a;
    while (s[star - 1] == '1')
    {
        star += 1;
    }
    int le1 = sum[star] - sum[a - 1];
    ull ha1 = gethash(bk[rank[star] + 1], jl[b]);
    LL ha1_a = gethash2(bk[rank[star] + 1], jl[b]);
    star = c;
    while (s[star - 1] == '1')
    {
        star += 1;
    }
    int le2 = sum[star] - sum[c - 1];
    ull ha2 = gethash(bk[rank[star] + 1], jl[d]);
    LL ha2_a = gethash2(bk[rank[star] + 1], jl[d]);
    if (ha1 == ha2 && abs(le1 - le2) % 3 == 0 && ha1_a == ha2_a)
        io.wstring("Yes\n");
    else
        io.wstring("No\n");
}
int main()
{
    IN;
    OUT;
    n = io.xint();
    q = io.xint();
    io.xstring(s);
    sums();
    hash_init();
    f(i, 1, q)
    {
        aa = io.xint();
        bb = io.xint();
        cc = io.xint();
        dd = io.xint();
        check(aa, bb, cc, dd);
    }
    return 0;
}