代码

// 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 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);
}

// 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;
    u64 y = (u64)dg[p] + v;
    if (y <= MASK) { dg[p] = (u32)y; updDigit(p); return; }
    dg[p] = (u32)(y - (1u << 30)); updDigit(p);
    int t = findNonFull(p + 1);
    setZeroRange(p + 1, t);
    dg[t] = dg[t] + 1; updDigit(t);
}
static inline void subVal(int p, u32 v) {
    if (!v) return;
    if (dg[p] >= v) { dg[p] -= v; updDigit(p); return; }
    dg[p] = (u32)((u64)dg[p] + (1u << 30) - v); updDigit(p);
    int t = findNonZero(p + 1);
    setOnesRange(p + 1, t);
    dg[t] = dg[t] - 1; updDigit(t);
}


// 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' + ((dg[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;
}

评测结果