代码

#include<bits/stdc++.h>

void solve(int n, int q, char *s1, char *s2, int *q_x, int *q_y, int *q_len, unsigned *ans)
{
    if (n <= 1e3)
        for (int i = 0; i < q; i++)
        {
            int x = q_x[i], y = q_y[i], len = q_len[i];
            ans[i] = 0;
            for (int t = 0; t < len; t++, x++, y++)
                ans[i] += ((s1[x] == '0' && s2[y] == '1') || (s1[x] == '1' && s2[y] == '2') ||
                           (s1[x] == '2' && s2[y] == '0')) ? 1 : 0;
        }
    else
    {
        for (int i = 0; i < q; i++)
            ans[i] = 0;
        int m = n - 64;
        std::vector<std::bitset<64>> na(m), nb(m);
        std::bitset<64> base;
        std::function<void(int, int, int, char, char, int)> solve2 = [&](int x, int y, int len, char ch1, char ch2,
                                                                         int id)
        {
            if (len <= 127)
            {
                for (int j = 0; j < len; j++, x++, y++)
                    ans[id] += (s1[x] == ch1 && s2[y] == ch2);
            }
            else
            {
                while (len > 127)
                {
                    auto temp = na[x] & nb[y];
                    x += 128, y += 128;
                    len -= 128;
                    ans[id] += temp.count();
                }
                for (int j = 0; j < len; j++, x++, y++)
                    ans[id] += (s1[x] == ch1 && s2[y] == ch2);
            }
        };
        std::function<void(char, char)> solve1 = [&](char ch1, char ch2)
        {
            for (int i = 0; i < 64; i++)
                base[i] = s1[i] == ch1;
            na[0] = base;
            for (int i = 1; i < m; i++)
            {
                base >>= 1;
                base[63] = s1[i + 63] == ch1;
                na[i] = base;
            }
            for (int i = 0; i < 64; i++)
                base[i] = s2[i] == ch2;
            nb[0] = base;
            for (int i = 1; i < m; i++)
            {
                base >>= 1;
                base[63] = s2[i + 63] == ch2;
                nb[i] = base;
            }
            for (int i = 0; i < q; i++)
            {
                int x = q_x[i], y = q_y[i], len = q_len[i];
                len = std::min(len, 25000);
                if (len <= 63)
                {
                    for (int j = 0; j < len; j++, x++, y++)
                        ans[i] += (s1[x] == ch1 && s2[y] == ch2);
                }
                else
                {
                    while (len > 63)
                    {
                        auto temp = na[x] & nb[y];
                        x += 64, y += 64;
                        len -= 64;
                        ans[i] += temp.count();
                    }
                    for (int j = 0; j < len; j++, x++, y++)
                        ans[i] += (s1[x] == ch1 && s2[y] == ch2);
                }
//                solve2(x, y, len, ch1, ch2, i);
            }
        };
        solve1('0', '1');
        solve1('1', '2');
        solve1('2', '0');
    }
}

评测结果