代码

// noi17a 【NOI2017】整数  (fast)
// x stored as base-2^30 digits; block (64 digit) summaries for "next non-full /
// next non-zero digit" give amortised O(1) per carry run.
#include <cstdio>
#include <cstring>
#include <cstdlib>

typedef unsigned long long u64;
typedef unsigned int u32;

#ifdef TEST_IO
static const char *IN; static u64 INSZ; static char *OUT; static u64 OUTSZ = 0; static u64 OUTLIM = 1u<<28;
#else
struct DI { u64 abi; const char*in; u64 insz; char*out; u64 outlim; u64 outsz; char*err;
            u64 errlim; u64 errsz; const char*IB; u64 IBlim; char*OB; u64 OBlim; u64 tscfreq; }
            __attribute__((packed));
#define DUCKINFO 0x243FFF90ULL
static struct DI *di;
static const char *IN; static u64 INSZ; static char *OUT; static u64 OUTSZ = 0; static u64 OUTLIM;
#endif

static const u32 MASK = (1u << 30) - 1u;
static const int MAXD = 1000104;
static const int NB = MAXD / 64 + 2;          // 15627
static const int NC = NB / 64 + 2;            // 246

static u32 dg[MAXD];
static unsigned char blkState[NB];   // 0 normal, 1 all-zero, 2 all-MASK
static u64 blkFull[NB], blkZero[NB];
static u64 cFull[NC], cZero[NC];

static inline void updBlockC(int g) {
    int c = g >> 6; u64 bit = 1ULL << (g & 63);
    if (blkFull[g] == ~0ULL) cFull[c] |= bit; else cFull[c] &= ~bit;
    if (blkZero[g] == ~0ULL) cZero[c] |= bit; else cZero[c] &= ~bit;
}
static inline void updDigit(int p) {
    u32 v = dg[p];
    int g = p >> 6; u64 bit = 1ULL << (p & 63);
    if (v == MASK) blkFull[g] |= bit; else blkFull[g] &= ~bit;
    if (v == 0) blkZero[g] |= bit; else blkZero[g] &= ~bit;
    updBlockC(g);
}

static inline void setBlockAll(int g, int allOnes) {
    if (allOnes) { blkFull[g] = ~0ULL; blkZero[g] = 0ULL; }
    else { blkFull[g] = 0ULL; blkZero[g] = ~0ULL; }
    updBlockC(g);
}
static inline void materialize(int g) {
    unsigned char st = blkState[g];
    if (!st) return;
    u32 v = (st == 1) ? 0u : MASK;
    u32 *q = dg + (g << 6);
    for (int i = 0; i < 64; i++) q[i] = v;
    blkState[g] = 0;
}
static inline u32 getDigit(int p) {
    int g = p >> 6;
    if (blkState[g]) materialize(g);
    return dg[p];
}
static inline void putDigit(int p, u32 v) {
    int g = p >> 6;
    if (blkState[g]) materialize(g);
    dg[p] = v;
    updDigit(p);
}
static inline void recomputeBlock(int g) {
    u32 *q = dg + (g << 6);
    u64 f = 0, z = 0;
    for (int i = 0; i < 64; i++) {
        if (q[i] == MASK) f |= 1ULL << i;
        if (q[i] == 0) z |= 1ULL << i;
    }
    blkFull[g] = f; blkZero[g] = z;
    updBlockC(g);
}
// assign val (0 or MASK) to digits [l,r)
static inline void assignRange(int l, int r, u32 val) {
    if (l >= r) return;
    int g0 = l >> 6, g1 = (r - 1) >> 6;
    if (g0 == g1) {
        if (blkState[g0]) materialize(g0);
        for (int i = l; i < r; i++) dg[i] = val;
        recomputeBlock(g0);
        return;
    }
    if (blkState[g0]) materialize(g0);
    for (int i = l; i < ((g0 + 1) << 6); i++) dg[i] = val;
    recomputeBlock(g0);
    for (int g = g0 + 1; g < g1; g++) { blkState[g] = (val == 0) ? 1 : 2; setBlockAll(g, val != 0); }
    if (blkState[g1]) materialize(g1);
    for (int i = g1 << 6; i < r; i++) dg[i] = val;
    recomputeBlock(g1);
}

// first index >= p with dg[idx] != MASK
static inline int findNonFull(int p) {
    int g = p >> 6;
    u64 m = ~blkFull[g] & (~0ULL << (p & 63));
    if (m) return (g << 6) + __builtin_ctzll(m);
    int gg = g + 1;
    while (gg < NB) {
        int cc = gg >> 6;
        u64 mm = ~cFull[cc] & (~0ULL << (gg & 63));
        if (!mm) {
            cc++;
            while (cc < NC && ~cFull[cc] == 0) cc++;
            if (cc >= NC) return MAXD;
            mm = ~cFull[cc]; gg = cc << 6;
            if (!mm) { gg = (cc << 6) + 64; continue; }
        }
        int g2 = (cc << 6) + __builtin_ctzll(mm);
        if (g2 >= NB) return MAXD;
        return (g2 << 6) + __builtin_ctzll(~blkFull[g2]);
    }
    return MAXD;
}
// first index >= p with dg[idx] != 0
static inline int findNonZero(int p) {
    int g = p >> 6;
    u64 m = ~blkZero[g] & (~0ULL << (p & 63));
    if (m) return (g << 6) + __builtin_ctzll(m);
    int gg = g + 1;
    while (gg < NB) {
        int cc = gg >> 6;
        u64 mm = ~cZero[cc] & (~0ULL << (gg & 63));
        if (!mm) {
            cc++;
            while (cc < NC && ~cZero[cc] == 0) cc++;
            if (cc >= NC) return MAXD;
            mm = ~cZero[cc]; gg = cc << 6;
            if (!mm) { gg = (cc << 6) + 64; continue; }
        }
        int g2 = (cc << 6) + __builtin_ctzll(mm);
        if (g2 >= NB) return MAXD;
        return (g2 << 6) + __builtin_ctzll(~blkZero[g2]);
    }
    return MAXD;
}

static inline void setZeroRange(int l, int r) {
    if (l >= r) return;
    int g0 = l >> 6, g1 = (r - 1) >> 6;
    if (g0 == g1) { for (int i = l; i < r; i++) { dg[i] = 0; updDigit(i); } return; }
    for (int i = l; i < ((g0 + 1) << 6); i++) { dg[i] = 0; updDigit(i); }
    for (int g = g0 + 1; g < g1; g++) {
        memset(dg + (g << 6), 0, 64 * sizeof(u32));
        blkFull[g] = 0; blkZero[g] = ~0ULL; updBlockC(g);
    }
    for (int i = g1 << 6; i < r; i++) { dg[i] = 0; updDigit(i); }
}
static inline void setOnesRange(int l, int r) {
    if (l >= r) return;
    int g0 = l >> 6, g1 = (r - 1) >> 6;
    if (g0 == g1) { for (int i = l; i < r; i++) { dg[i] = MASK; updDigit(i); } return; }
    for (int i = l; i < ((g0 + 1) << 6); i++) { dg[i] = MASK; updDigit(i); }
    for (int g = g0 + 1; g < g1; g++) {
        u32 *p = dg + (g << 6);
        for (int t = 0; t < 64; t++) p[t] = MASK;
        blkFull[g] = ~0ULL; blkZero[g] = 0; updBlockC(g);
    }
    for (int i = g1 << 6; i < r; i++) { dg[i] = MASK; updDigit(i); }
}

static inline void addVal(int p, u32 v) {
    if (!v) return;
    u32 cur = getDigit(p);
    u64 y = (u64)cur + v;
    if (y <= MASK) { putDigit(p, (u32)y); return; }
    putDigit(p, (u32)(y - (1u << 30)));
    int t = findNonFull(p + 1);
    assignRange(p + 1, t, 0);
    putDigit(t, getDigit(t) + 1);
}
static inline void subVal(int p, u32 v) {
    if (!v) return;
    u32 cur = getDigit(p);
    if (cur >= v) { putDigit(p, cur - v); return; }
    putDigit(p, (u32)((u64)cur + (1u << 30) - v));
    int t = findNonZero(p + 1);
    assignRange(p + 1, t, MASK);
    putDigit(t, getDigit(t) - 1);
}


// SWAR 8-digit-at-a-time unsigned parser (bounded by end)
static inline u64 parseU(const char *&p, const char *end) {
    u64 v = 0;
    while (p + 8 <= end) {
        u64 x;
        __builtin_memcpy(&x, p, 8);
        u64 d = x - 0x3030303030303030ULL;
        if ((d + 0x0606060606060606ULL) & 0xF0F0F0F0F0F0F0F0ULL) break;
        u64 t = (d * 10 + (d >> 8)) & 0x00FF00FF00FF00FFULL;
        t = (t * 100 + (t >> 16)) & 0x0000FFFF0000FFFFULL;
        t = (t * 10000 + (t >> 32)) & 0xFFFFFFFFULL;
        v = v * 100000000ULL + t;
        p += 8;
    }
    while (p < end && *p >= '0' && *p <= '9') v = v * 10 + (*p++ - '0');
    return v;
}
static inline void skipToDigit(const char *&p, const char *end) {
    while (p < end && (*p < '0' || *p > '9')) p++;
}

int main() {
#ifdef TEST_IO
    static char inbuf[1 << 26];
    INSZ = fread(inbuf, 1, sizeof(inbuf), stdin);
    IN = inbuf;
    static char outbuf[1 << 24];
    OUT = outbuf; OUTLIM = sizeof(outbuf);
#else
    di = (struct DI *)DUCKINFO;
    IN = di->in; INSZ = di->insz;
    OUT = di->out; OUTLIM = di->outlim;
#endif
    for (int g = 0; g < NB; g++) { blkFull[g] = 0ULL; blkZero[g] = ~0ULL; }
    for (int c = 0; c < NC; c++) { cFull[c] = 0ULL; cZero[c] = ~0ULL; }

    const char *p = IN, *pend = IN + INSZ;
    long long n = (long long)parseU(p, pend);
    skipToDigit(p, pend); (void)parseU(p, pend);      // t1
    skipToDigit(p, pend); (void)parseU(p, pend);      // t2
    skipToDigit(p, pend); (void)parseU(p, pend);      // t3
    for (long long op = 0; op < n; op++) {
        skipToDigit(p, pend);
        long long t = (long long)parseU(p, pend);
        p++;                            // skip the single delimiter
        if (t == 1) {
            long long a;
            if (*p == '-') { p++; a = -(long long)parseU(p, pend); }
            else a = (long long)parseU(p, pend);
            p++;
            long long b = (long long)parseU(p, pend);
            p++;
            if (a == 0) continue;
            int q = (int)(b / 30);
            int r = (int)(b % 30);
            u64 av = (u64)(a > 0 ? a : -a);
            u64 sh = av << r;
            u32 s0 = (u32)(sh & MASK);
            u32 s1 = (u32)(sh >> 30);
            if (a > 0) { addVal(q, s0); addVal(q + 1, s1); }
            else { subVal(q, s0); subVal(q + 1, s1); }
        } else {
            long long k = (long long)parseU(p, pend);
            p++;
            if (OUTSZ + 2 <= OUTLIM) {
                OUT[OUTSZ++] = (char)('0' + ((getDigit((int)(k / 30)) >> (k % 30)) & 1u));
                OUT[OUTSZ++] = '\n';
            }
        }
    }
#ifdef TEST_IO
    fwrite(outbuf, 1, OUTSZ, stdout);
#else
    di->outsz = OUTSZ;
    register long rax __asm__("rax") = 60;
    register long rdi __asm__("rdi") = 0;
    __asm__ volatile("syscall" :: "a"(rax), "D"(rdi) : "rcx", "r11", "memory");
    __builtin_unreachable();
#endif
    return 0;
}

评测结果