代码

#include <immintrin.h>
typedef unsigned u32;
typedef unsigned long long u64;

enum { MAXN = 300000, WORDS = (MAXN + 63) / 64 + 8 };
static u64 base[4][WORDS] __attribute__((aligned(32)));
static u64 shifted_[4][8][WORDS] __attribute__((aligned(32)));

static __attribute__((always_inline)) inline u64 shift_word(const u64 *p,
                                                             int word,
                                                             int shift) {
    if (!shift) return p[word];
    return (p[word] >> shift) | (p[word + 1] << (64 - shift));
}

__attribute__((target("avx2,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;
        base[0][i >> 6] |= (u64)(a & 1u) << (i & 63);
        base[1][i >> 6] |= (u64)(a >> 1) << (i & 63);
        base[2][i >> 6] |= (u64)(b & 1u) << (i & 63);
        base[3][i >> 6] |= (u64)(b >> 1) << (i & 63);
    }
    for (int plane = 0; plane < 4; ++plane)
        for (int shift = 0; shift < 8; ++shift)
            for (int word = 0; word <= words + 4; ++word)
                shifted_[plane][shift][word] =
                    shift_word(base[plane], word, shift);

    const __m256i low_mask = _mm256_set1_epi8(15);
    const __m256i lookup = _mm256_setr_epi8(
        0,1,1,2,1,2,2,3,1,2,2,3,2,3,3,4,
        0,1,1,2,1,2,2,3,1,2,2,3,2,3,3,4);
    const __m256i zero = _mm256_setzero_si256();

    for (int z = 0; z < q; ++z) {
        unsigned x = (unsigned)qx[z], y = (unsigned)qy[z];
        unsigned length = (unsigned)ql[z];
        const unsigned char *a0 =
            (const unsigned char *)shifted_[0][x & 7] + (x >> 3);
        const unsigned char *a1 =
            (const unsigned char *)shifted_[1][x & 7] + (x >> 3);
        const unsigned char *b0 =
            (const unsigned char *)shifted_[2][y & 7] + (y >> 3);
        const unsigned char *b1 =
            (const unsigned char *)shifted_[3][y & 7] + (y >> 3);
        u32 total = 0;
        __m256i vector_total = zero;
        while (length >= 256) {
            __m256i va0 = _mm256_loadu_si256((const __m256i *)a0);
            __m256i va1 = _mm256_loadu_si256((const __m256i *)a1);
            __m256i vb0 = _mm256_loadu_si256((const __m256i *)b0);
            __m256i vb1 = _mm256_loadu_si256((const __m256i *)b1);
            __m256i different = _mm256_or_si256(
                _mm256_xor_si256(va0, vb0), _mm256_xor_si256(va1, vb1));
            __m256i equal = _mm256_xor_si256(different,
                                              _mm256_set1_epi32(-1));
            __m256i count = _mm256_add_epi8(
                _mm256_shuffle_epi8(lookup, _mm256_and_si256(equal, low_mask)),
                _mm256_shuffle_epi8(lookup,
                    _mm256_and_si256(_mm256_srli_epi16(equal, 4), low_mask)));
            __m256i sums = _mm256_sad_epu8(count, zero);
            vector_total = _mm256_add_epi64(vector_total, sums);
            a0 += 32; a1 += 32; b0 += 32; b1 += 32;
            length -= 256;
        }
        u64 lane[4] __attribute__((aligned(32)));
        _mm256_store_si256((__m256i *)lane, vector_total);
        total = (u32)(lane[0] + lane[1] + lane[2] + lane[3]);
        while (length >= 64) {
            u64 same = ~((*(const u64 *)a0 ^ *(const u64 *)b0) |
                         (*(const u64 *)a1 ^ *(const u64 *)b1));
            total += (u32)__builtin_popcountll(same);
            a0 += 8; a1 += 8; b0 += 8; b1 += 8;
            length -= 64;
        }
        if (length) {
            u64 same = ~((*(const u64 *)a0 ^ *(const u64 *)b0) |
                         (*(const u64 *)a1 ^ *(const u64 *)b1));
            same &= ~0ull >> (64 - length);
            total += (u32)__builtin_popcountll(same);
        }
        ans[z] = total;
    }
    _mm256_zeroupper();
}

评测结果