代码

#include <stdint.h>
#pragma GCC target("bmi")
#include <sys/auxv.h>
#include <unistd.h>

struct DuckInfo {
  uint64_t abi_version;
  const char *stdin_ptr; uint64_t stdin_size;
  char *stdout_ptr; uint64_t stdout_limit; uint64_t stdout_size;
  char *stderr_ptr; uint64_t stderr_limit; uint64_t stderr_size;
  const char *IB_ptr; uint64_t IB_limit;
  char *OB_ptr; uint64_t OB_limit;
  uint64_t tsc_frequency;
} __attribute__((packed));

typedef unsigned __int128 u128;
#define FULL ((u128)-1)
#define NB 234496
#define N1 3664
#define N2 58

static u128 blk[NB];
static uint64_t fm1[N1], nm1[N1];
static uint64_t fm3, nm3;

static const char *P;
static uint64_t O;
static int has_lazy;

static inline int ctz(uint64_t x){ return __builtin_ctzll(x); }

/* ---- point add / sub (single-block, materialize + bubble) ---- */

static inline int point_add(int pos, u128 v){
    int l2 = pos >> 12;
    int l1 = pos >> 6;
    int ovf;
    uint64_t old_fm1, old_nm1;
    if (has_lazy){
        uint64_t b3 = 1ull << l2;
        if (fm3 & b3){ fm1[l1] = ~0ull; nm1[l1] = ~0ull; }
        else if (!(nm3 & b3)){ fm1[l1] = 0; nm1[l1] = 0; }
    }
    old_fm1 = fm1[l1]; old_nm1 = nm1[l1];
    {
        uint64_t b = 1ull << (pos & 63);
        u128 old;
        if (old_fm1 & b) old = FULL;
        else if (!(old_nm1 & b)) old = 0;
        else old = blk[pos];
        u128 nv = old + v;
        blk[pos] = nv;
        ovf = nv < old;
        if (nv == FULL) fm1[l1] |= b; else fm1[l1] &= ~b;
        if (nv != 0) nm1[l1] |= b; else nm1[l1] &= ~b;
    }
    if ((old_fm1 == ~0ull) != (fm1[l1] == ~0ull) || (old_nm1 == 0) != (nm1[l1] == 0)){
        uint64_t b3 = 1ull << l2;
        if (fm1[l1] == ~0ull) fm3 |= b3; else fm3 &= ~b3;
        if (nm1[l1] != 0) nm3 |= b3; else nm3 &= ~b3;
    }
    return ovf;
}

static inline int point_sub(int pos, u128 v){
    int l2 = pos >> 12;
    int l1 = pos >> 6;
    int ovf;
    uint64_t old_fm1, old_nm1;
    if (has_lazy){
        uint64_t b3 = 1ull << l2;
        if (fm3 & b3){ fm1[l1] = ~0ull; nm1[l1] = ~0ull; }
        else if (!(nm3 & b3)){ fm1[l1] = 0; nm1[l1] = 0; }
    }
    old_fm1 = fm1[l1]; old_nm1 = nm1[l1];
    {
        uint64_t b = 1ull << (pos & 63);
        u128 old;
        if (old_fm1 & b) old = FULL;
        else if (!(old_nm1 & b)) old = 0;
        else old = blk[pos];
        u128 nv = old - v;
        blk[pos] = nv;
        ovf = nv > old;
        if (nv == FULL) fm1[l1] |= b; else fm1[l1] &= ~b;
        if (nv != 0) nm1[l1] |= b; else nm1[l1] &= ~b;
    }
    if ((old_fm1 == ~0ull) != (fm1[l1] == ~0ull) || (old_nm1 == 0) != (nm1[l1] == 0)){
        uint64_t b3 = 1ull << l2;
        if (fm1[l1] == ~0ull) fm3 |= b3; else fm3 &= ~b3;
        if (nm1[l1] != 0) nm3 |= b3; else nm3 &= ~b3;
    }
    return ovf;
}

/* ---- left-boundary suffix helpers (operate on a FULL/zero node) ---- */

/* zero blocks [pos, l2*4096+4095] of a FULL level-2 node l2; off2 = pos&4095 > 0 */
static inline void zero_full_l2(int l2, int off2){
    int pos = (l2 << 12) + off2;
    int l1 = pos >> 6, off = pos & 63;
    fm1[l1] = (off == 0) ? 0 : ((1ull << off) - 1);
    nm1[l1] = fm1[l1];
    uint64_t b3 = 1ull << l2;
    fm3 &= ~b3;
    nm3 |= b3;
}

/* zero blocks [pos, l1*64+63] of a FULL level-1 node l1; off = pos&63 > 0 */
static inline void zero_full_l1(int l1, int off){
    fm1[l1] = (1ull << off) - 1;
    nm1[l1] = (1ull << off) - 1;
    int l2 = l1 >> 6;
    uint64_t b3 = 1ull << l2;
    fm3 &= ~b3;
    nm3 |= b3;
}

/* set blocks [pos, l2*4096+4095] of a ZERO level-2 node l2 to full; off2 = pos&4095 > 0 */
static inline void set_full_l2(int l2, int off2){
    int pos = (l2 << 12) + off2;
    int l1 = pos >> 6, off = pos & 63;
    fm1[l1] = ~0ull << off;
    nm1[l1] = fm1[l1];
    uint64_t b3 = 1ull << l2;
    if (off2 == 0) fm3 |= b3; else fm3 &= ~b3;
    nm3 |= b3;
}

/* set blocks [pos, l1*64+63] of a ZERO level-1 node l1 to full; off = pos&63 > 0 */
static inline void set_full_l1(int l1, int off){
    fm1[l1] = ~0ull << off;
    nm1[l1] = ~0ull << off;
    int l2 = l1 >> 6;
    uint64_t b3 = 1ull << l2;
    if (fm1[l1] == ~0ull) fm3 |= b3; else fm3 &= ~b3;
    nm3 |= b3;
}

/* ---- fused carry: find first non-full block j >= p, zero [p, j-1], increment j ---- */

static inline void carry_add(int p){
    has_lazy = 1;
    int l2 = p >> 12, l1 = p >> 6, off = p & 63;
    int off2 = p & 4095;
    uint64_t m3 = ~fm3 >> l2;
    int l2pos = (off2 == 0) ? l2 : l2 + 1;
    if (off2 > 0 && (fm3 & (1ull << l2))){
        zero_full_l2(l2, off2);
    }
    while (m3){
        int l2n = l2 + ctz(m3);
        uint64_t b3 = 1ull << l2n;
        if (l2n > l2pos){
            uint64_t zm = ((1ull << (l2n - l2pos)) - 1) << l2pos;
            fm3 &= ~zm; nm3 &= ~zm;
        }
        l2pos = l2n + 1;
        if (!(nm3 & b3)){   /* group all-zero -> j = first block of the group */
            if (l2n > l2){
                blk[l2n << 12] = 1;
                fm1[l2n << 6] = 0; nm1[l2n << 6] = 1ull;
                fm3 &= ~b3; nm3 |= b3;
                return;
            } else {
                /* l2n == l2: j = p */
                uint64_t b1 = 1ull << off;
                blk[p] = 1;
                fm1[l1] = 0; nm1[l1] = b1;
                fm3 &= ~b3; nm3 |= b3;
                return;
            }
        }
        /* group mixed: scan its 64 l1 groups */
        int c1s = (l2n == l2) ? l1 : (l2n << 6);
        for (int l1n = c1s; l1n < (l2n << 6) + 64; l1n++){
            if (l1n >= N1){               /* virtual (padding) l1: all-zero */
                blk[l1n << 6] = 1;
                fm3 &= ~b3; nm3 |= b3;
                return;
            }
            if (fm1[l1n] == ~0ull){       /* full intermediate l1: zero it */
                fm1[l1n] = 0; nm1[l1n] = 0;
                continue;
            }
            if (nm1[l1n] == 0){           /* all-zero l1: j = its first block */
                if (l1n > l1){
                    blk[l1n << 6] = 1;
                    fm1[l1n] = 0; nm1[l1n] = 1ull;
                } else {
                    uint64_t b1 = 1ull << off;
                    blk[p] = 1;
                    fm1[l1] = 0; nm1[l1] = b1;
                }
                fm3 &= ~b3; nm3 |= b3;
                return;
            }
            int c0 = (l1n == l1) ? off : 0;
            uint64_t m1 = ~fm1[l1n] >> c0;
            if (m1){
                int c1r = c0 + ctz(m1);
                int j = (l1n << 6) + c1r;
                uint64_t b1 = 1ull << c1r;
                if (c1r > c0){
                    uint64_t zm = ((1ull << (c1r - c0)) - 1) << c0;
                    fm1[l1n] &= ~zm; nm1[l1n] &= ~zm;
                }
                if (nm1[l1n] & b1){
                    u128 nv = blk[j] + 1;
                    blk[j] = nv;
                    if (nv == FULL) fm1[l1n] |= b1; else fm1[l1n] &= ~b1;
                    nm1[l1n] |= b1;
                } else {
                    blk[j] = 1;
                    fm1[l1n] &= ~b1; nm1[l1n] |= b1;
                }
                if (fm1[l1n] == ~0ull) fm3 |= b3; else fm3 &= ~b3;
                if (nm1[l1n] != 0) nm3 |= b3; else nm3 &= ~b3;
                return;
            }
            /* suffix [c0..63] all-full: zero it, continue */
            {
                uint64_t zm = ~0ull << c0;
                fm1[l1n] &= ~zm; nm1[l1n] &= ~zm;
            }
        }
        m3 &= m3 - 1;
    }
}

/* ---- fused borrow: find first non-zero block j >= p, set [p, j-1] full, decrement j ---- */

static inline void borrow_sub(int p){
    has_lazy = 1;
    int l2 = p >> 12, l1 = p >> 6, off = p & 63;
    int off2 = p & 4095;
    uint64_t m3 = nm3 >> l2;
    int l2pos = (off2 == 0) ? l2 : l2 + 1;
    if (off2 > 0 && !(nm3 & (1ull << l2))){
        set_full_l2(l2, off2);
    }
    while (m3){
        int l2n = l2 + ctz(m3);
        uint64_t b3 = 1ull << l2n;
        if (l2n > l2pos){
            uint64_t zm = ((1ull << (l2n - l2pos)) - 1) << l2pos;
            fm3 |= zm; nm3 |= zm;
        }
        l2pos = l2n + 1;
        if (fm3 & b3){   /* group all-full -> j = first block of the group */
            if (l2n > l2){
                blk[l2n << 12] = FULL - 1;
                fm1[l2n << 6] = ~0ull ^ 1ull; nm1[l2n << 6] = ~0ull;
                fm3 &= ~b3; nm3 |= b3;
                return;
            } else {
                uint64_t b1 = 1ull << off;
                blk[p] = FULL - 1;
                fm1[l1] = ~0ull ^ b1; nm1[l1] = ~0ull;
                fm3 &= ~b3; nm3 |= b3;
                return;
            }
        }
        /* group mixed: scan its 64 l1 groups */
        int c1s = (l2n == l2) ? l1 : (l2n << 6);
        for (int l1n = c1s; l1n < (l2n << 6) + 64; l1n++){
            if (l1n >= N1){               /* virtual (padding) l1: all-zero */
                continue;
            }
            if (nm1[l1n] == 0){           /* zero intermediate l1: set it full */
                fm1[l1n] = ~0ull; nm1[l1n] = ~0ull;
                continue;
            }
            if (fm1[l1n] == ~0ull){       /* all-full l1: j = its first block */
                if (l1n > l1){
                    blk[l1n << 6] = FULL - 1;
                    fm1[l1n] = ~0ull ^ 1ull; nm1[l1n] = ~0ull;
                } else {
                    uint64_t b1 = 1ull << off;
                    blk[p] = FULL - 1;
                    fm1[l1] = ~0ull ^ b1; nm1[l1] = ~0ull;
                }
                fm3 &= ~b3; nm3 |= b3;
                return;
            }
            int c0 = (l1n == l1) ? off : 0;
            uint64_t m1 = nm1[l1n] >> c0;
            if (m1){
                int c1r = c0 + ctz(m1);
                int j = (l1n << 6) + c1r;
                uint64_t b1 = 1ull << c1r;
                if (c1r > c0){
                    uint64_t zm = ((1ull << (c1r - c0)) - 1) << c0;
                    fm1[l1n] |= zm; nm1[l1n] |= zm;
                }
                if (fm1[l1n] & b1){
                    blk[j] = FULL - 1;
                    fm1[l1n] &= ~b1; nm1[l1n] |= b1;
                } else {
                    u128 nv = blk[j] - 1;
                    blk[j] = nv;
                    if (nv == 0) nm1[l1n] &= ~b1; else nm1[l1n] |= b1;
                }
                if (fm1[l1n] == ~0ull) fm3 |= b3; else fm3 &= ~b3;
                if (nm1[l1n] != 0) nm3 |= b3; else nm3 &= ~b3;
                return;
            }
            /* suffix [c0..63] all-zero: set it full, continue */
            {
                uint64_t zm = ~0ull << c0;
                fm1[l1n] |= zm; nm1[l1n] |= zm;
            }
        }
        m3 &= m3 - 1;
    }
}

/* ---- add / sub a*2^r ---- */

static inline void add_val(int q, int r, uint64_t av){
    u128 lo = (u128)av << r;
    uint64_t hi = 0;
    if (r >= 99) hi = av >> (128 - r);
    if (point_add(q, lo)) carry_add(q + 1);
    if (hi && point_add(q + 1, (u128)hi)) carry_add(q + 2);
}
static inline void sub_val(int q, int r, uint64_t av){
    u128 lo = (u128)av << r;
    uint64_t hi = 0;
    if (r >= 99) hi = av >> (128 - r);
    if (point_sub(q, lo)) borrow_sub(q + 1);
    if (hi && point_sub(q + 1, (u128)hi)) borrow_sub(q + 2);
}

/* ---- parse ---- */

static inline int rd(){
    while (*P <= ' ') P++;
    int v = 0;
    while (*P > ' ') v = v*10 + (*P - '0'), P++;
    return v;
}
static inline int rds(){
    while (*P <= ' ') P++;
    int neg = 0;
    if (*P == '-'){ neg = 1; P++; }
    int v = 0;
    while (*P > ' ') v = v*10 + (*P - '0'), P++;
    return neg ? -v : v;
}

/* branchless 1..8 digit parse: load8, ctz-length, bswap+shift, SWAR convert */
static inline unsigned parse8(const char **pp){
    const char *p = *pp;
    unsigned long long x;
    __builtin_memcpy(&x, p, 8);
    unsigned long long m = (x - 0x3030303030303030ULL) & ~x & 0x8080808080808080ULL;
    int len = __builtin_ctzll(m) >> 3;
    unsigned long long d = __builtin_bswap64(x - 0x3030303030303030ULL);
    d >>= 64 - (len << 3);
    unsigned long long t = (d * 0x010AULL) & 0xFF00FF00FF00FF00ULL;
    t >>= 8;
    unsigned long long t2 = t * 0x00010064ULL;
    *pp = p + len;
    return (unsigned)(((t2 >> 16) & 0xFFFFULL) + 10000ULL * ((t2 >> 48) & 0xFFFFULL));
}

__attribute__((noreturn)) static void done(uint64_t olen, struct DuckInfo *di, char *out, int use_di){
    if (use_di) di->stdout_size = olen;
    else (void)!write(1, out, olen);
    asm volatile("mov $60, %%eax; xor %%edi, %%edi; syscall" ::: "rax","rdi","memory");
    __builtin_unreachable();
}

int main(){
    struct DuckInfo *di = (struct DuckInfo*)getauxval(0x6b637564);
    static char lbuf[1<<24];
    static char obuf[1<<22];
    char *out;
    int use_di = 0;
    if (di && di->abi_version >= 1 && di->stdin_ptr && di->stdout_ptr){
        P = di->stdin_ptr;
        out = di->stdout_ptr;
        use_di = 1;
    } else {
        long n2 = 0, t;
        while (n2 < (long)sizeof(lbuf) && (t = read(0, lbuf + n2, sizeof(lbuf) - n2)) > 0) n2 += t;
        lbuf[n2] = 0;
        P = lbuf;
        out = obuf;
    }

    int n = rd();
    rd(); rd(); rd();
    P++;  /* skip newline after header */

    for (int i = 0; i < n; i++){
        int op = *P++ - '0';
        P++;  /* skip separator */
        if (op == 1){
            int neg = 0;
            if (*P == '-'){ neg = 1; P++; }
            int a = 0;
            while (*P > ' '){ a = a*10 + (*P - '0'); P++; }
            P++;  /* skip separator */
            int b = (int)parse8(&P);
            P++;  /* skip separator (newline) */
            int q = b >> 7;
            int r = b & 127;
            if (neg) sub_val(q, r, (uint64_t)a);
            else if (a) add_val(q, r, (uint64_t)a);
        } else {
            int k = (int)parse8(&P);
            P++;  /* skip separator (newline) */
            int q = k >> 7;
            int r = k & 127;
            uint64_t v;
            {
                int l2 = q >> 12, l1 = q >> 6;
                uint64_t b3 = 1ull << l2;
                if (fm3 & b3) v = 1;
                else if (!(nm3 & b3)) v = 0;
                else {
                    uint64_t b1 = 1ull << (q & 63);
                    if (fm1[l1] & b1) v = 1;
                    else if (!(nm1[l1] & b1)) v = 0;
                    else v = (uint64_t)((blk[q] >> r) & 1);
                }
            }
            out[O++] = (char)('0' + (v & 1));
            out[O++] = '\n';
        }
    }
    done(O, di, out, use_di);
}

评测结果