代码

typedef unsigned u32;
typedef unsigned long long u64;

enum { MAXN = 300000, WORDS = (MAXN + 63) / 64 + 2 };

static u64 first0[WORDS], first1[WORDS];
static u64 base0[WORDS], base1[WORDS];
static u64 second0[64][WORDS], second1[64][WORDS];

static __attribute__((always_inline)) inline u64 shifted(const u64 *a,
                                                          unsigned bit) {
    unsigned word = bit >> 6, shift = bit & 63;
    if (!shift) return a[word];
    return (a[word] >> shift) | (a[word + 1] << (64 - shift));
}

__attribute__((target("popcnt")))
void solve(int n, int q, char *s1, char *s2, int *qx, int *qy, int *ql,
           u32 *ans) {
    int words = (n + 63) >> 6;
    for (int i = 0; i < n; ++i) {
        unsigned a = (unsigned)(s1[i] - '0');
        unsigned b = ((unsigned)(s2[i] - '0') + 2u) % 3u;
        first0[i >> 6] |= (u64)(a & 1u) << (i & 63);
        first1[i >> 6] |= (u64)(a >> 1) << (i & 63);
        base0[i >> 6] |= (u64)(b & 1u) << (i & 63);
        base1[i >> 6] |= (u64)(b >> 1) << (i & 63);
    }
    for (int offset = 0; offset < 64; ++offset) {
        for (int word = 0; word <= words; ++word) {
            unsigned bit = (unsigned)(word << 6) + (unsigned)offset;
            second0[offset][word] = shifted(base0, bit);
            second1[offset][word] = shifted(base1, bit);
        }
    }

    for (int z = 0; z < q; ++z) {
        unsigned x = (unsigned)qx[z], y = (unsigned)qy[z];
        unsigned length = (unsigned)ql[z];
        unsigned shift = x & 63, ix = x >> 6, iy = y >> 6;
        const u64 *b0 = second0[y & 63] + iy;
        const u64 *b1 = second1[y & 63] + iy;
        u32 total = 0;
        while (length >= 64) {
            u64 a0, a1;
            if (shift) {
                a0 = (first0[ix] >> shift) |
                     (first0[ix + 1] << (64 - shift));
                a1 = (first1[ix] >> shift) |
                     (first1[ix + 1] << (64 - shift));
            } else {
                a0 = first0[ix]; a1 = first1[ix];
            }
            u64 same = ~((a0 ^ *b0++) | (a1 ^ *b1++));
            total += (u32)__builtin_popcountll(same);
            ++ix;
            length -= 64;
        }
        if (length) {
            u64 a0, a1;
            if (shift) {
                a0 = (first0[ix] >> shift) |
                     (first0[ix + 1] << (64 - shift));
                a1 = (first1[ix] >> shift) |
                     (first1[ix + 1] << (64 - shift));
            } else {
                a0 = first0[ix]; a1 = first1[ix];
            }
            u64 same = ~((a0 ^ *b0) | (a1 ^ *b1));
            same &= ~0ull >> (64 - length);
            total += (u32)__builtin_popcountll(same);
        }
        ans[z] = total;
    }
}

评测结果