代码

// This code is AI-generated. (AI 生成的代码)
// WC2017 挑战-任务2 (rock-paper-scissors range queries).
//
// Map s1[i] -> "120"[s1[i]-'0'], the hand that s1[i] beats, so a win at offset i
// is exactly s1'[x+i] == s2[y+i].  Encode each hand with two bit planes:
// v1 = (c=='1'), v2 = (c=='2'); then c == d iff (v1^w1)|(v2^w2) has no bit at
// that position.  Store s1 as A1/A2 and s2 as B1/B2.
//
// For a query the B planes must be shifted by d = y-x bits.  Precompute P[r]
// = B >> r for r = 0..7; an arbitrary offset is then handled with a byte
// pointer offset qb (off = 8*qb + r).  Matching 256 positions at a time with
// AVX2, the mismatch planes are popcounted with a nibble table + vpsadbw, and
// the answer is l - mismatches.  Partial words at the two ends are scalar.
#include <immintrin.h>
#include <stdint.h>
#include <string.h>
#pragma GCC optimize("O3")
#pragma GCC target("avx2,popcnt")

typedef unsigned long long u64;

enum { MAXN = 300000, MAXNW = (MAXN + 63) / 64, PAD = MAXNW + 32, TOTAL = 3 * MAXNW + 128 };

static u64 A1[TOTAL], A2[TOTAL];
static u64 P1[8][TOTAL], P2[8][TOTAL];

static inline u64 mword(const u64 *a1, const u64 *a2, const char *b1, const char *b2, int off) {
    u64 x1, x2, y1, y2;
    memcpy(&x1, b1 + (size_t)off * 8, 8);
    memcpy(&x2, b2 + (size_t)off * 8, 8);
    y1 = a1[0]; y2 = a2[0];
    return (y1 ^ x1) | (y2 ^ x2);
}

void solve(int n, int q, char *s1, char *s2, int *q_x, int *q_y, int *q_len, unsigned *ans) {
    for (int i = 0; i < n; ++i) s1[i] = "120"[s1[i] - '0'];
    int nw = (n + 63) >> 6;

    memset(A1, 0, sizeof(u64) * TOTAL);
    memset(A2, 0, sizeof(u64) * TOTAL);
    memset(P1, 0, sizeof(P1));
    memset(P2, 0, sizeof(P2));
    for (int i = 0; i < n; ++i) {
        int w = PAD + (i >> 6);
        u64 bit = 1ULL << (i & 63);
        char c = s1[i];
        if (c == '1') A1[w] |= bit; else if (c == '2') A2[w] |= bit;
        c = s2[i];
        if (c == '1') P1[0][w] |= bit; else if (c == '2') P2[0][w] |= bit;
    }
    for (int r = 1; r < 8; ++r) {
        const u64 *s1p = P1[0], *s2p = P2[0];
        u64 *d1 = P1[r], *d2 = P2[r];
        int sh = 64 - r;
        for (int j = -nw; j <= 2 * nw + 2; ++j) {
            int k = PAD + j;
            d1[k] = (s1p[k + 1] << sh) | (s1p[k] >> r);
            d2[k] = (s2p[k + 1] << sh) | (s2p[k] >> r);
        }
    }

    const __m256i tab = _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 m0f = _mm256_set1_epi8(0x0f);
    const __m256i zero = _mm256_setzero_si256();

    for (int k = 0; k < q; ++k) {
        int x = q_x[k], y = q_y[k], l = q_len[k];
        int d = y - x;
        int off = d & 63;
        int woff = d >> 6;
        int r = off & 7, qb = off >> 3;
        int w_start = x >> 6, boff = x & 63;
        int w_end = (x + l - 1) >> 6, beoff = (x + l - 1) & 63;

        const char *b1 = (const char *)&P1[r][0] + (size_t)(PAD + w_start + woff) * 8 + qb;
        const char *b2 = (const char *)&P2[r][0] + (size_t)(PAD + w_start + woff) * 8 + qb;
        const u64 *a1 = A1 + PAD + w_start;
        const u64 *a2 = A2 + PAD + w_start;

        u64 ones = 0;
        if (w_start == w_end) {
            u64 mask = (~0ULL << boff);
            if (beoff != 63) mask &= (1ULL << (beoff + 1)) - 1;
            ones += (u64)__builtin_popcountll(mword(a1, a2, b1, b2, 0) & mask);
        } else {
            if (boff) ones += (u64)__builtin_popcountll(mword(a1, a2, b1, b2, 0) & (~0ULL << boff));
            if (beoff != 63)
                ones += (u64)__builtin_popcountll(mword(a1 + (w_end - w_start), a2 + (w_end - w_start),
                                                      b1, b2, w_end - w_start) & ((1ULL << (beoff + 1)) - 1));
            int lo = w_start + (boff ? 1 : 0);
            int hi = w_end - ((beoff != 63) ? 1 : 0);
            int u = lo;
            __m256i acc = zero;
            while (u + 3 <= hi) {
                int o = u - w_start;
                __m256i av1 = _mm256_loadu_si256((const __m256i *)(a1 + o));
                __m256i av2 = _mm256_loadu_si256((const __m256i *)(a2 + o));
                __m256i bv1 = _mm256_loadu_si256((const __m256i *)(b1 + (size_t)o * 8));
                __m256i bv2 = _mm256_loadu_si256((const __m256i *)(b2 + (size_t)o * 8));
                __m256i m = _mm256_or_si256(_mm256_xor_si256(av1, bv1), _mm256_xor_si256(av2, bv2));
                __m256i lo4 = _mm256_and_si256(m, m0f);
                __m256i hi4 = _mm256_and_si256(_mm256_srli_epi16(m, 4), m0f);
                __m256i pc = _mm256_add_epi8(_mm256_shuffle_epi8(tab, lo4), _mm256_shuffle_epi8(tab, hi4));
                acc = _mm256_add_epi64(acc, _mm256_sad_epu8(pc, zero));
                u += 4;
            }
            u64 lane[4];
            _mm256_storeu_si256((__m256i *)lane, acc);
            ones += lane[0] + lane[1] + lane[2] + lane[3];
            for (; u <= hi; ++u)
                ones += (u64)__builtin_popcountll(mword(a1 + (u - w_start), a2 + (u - w_start), b1, b2, u - w_start));
        }
        ans[k] = (unsigned)(l - (int)ones);
    }
}

#ifdef LOCAL_TEST
#include <cstdio>
int main() {
    int n, q;
    if (scanf("%d %d", &n, &q) != 2) return 0;
    static char s1[1000005], s2[1000005];
    scanf("%s %s", s1, s2);
    static int qx[1000005], qy[1000005], ql[1000005];
    static unsigned ans[1000005];
    for (int i = 0; i < q; ++i) scanf("%d %d %d", &qx[i], &qy[i], &ql[i]);
    solve(n, q, s1, s2, qx, qy, ql, ans);
    for (int i = 0; i < q; ++i) printf("%u\n", ans[i]);
    return 0;
}
#endif

评测结果