代码

#include <stdint.h>
#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));

#define FULL 0xFFFFFFFFu
#define NB 937600          /* 14650*64 */
#define N1 14650
#define N2 229
#define N3 4

static uint32_t blk[NB];
static uint64_t f1[N1], z1[N1];
static uint64_t f2[N2], z2[N2];
static uint64_t f3[N3], z3[N3];
static uint64_t f4, z4;

static const char *P;
static uint64_t O;

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

/* ---- point add / sub (32-bit leaf) ---- */

static inline uint32_t point_add(int pos, uint32_t v){
    int l1 = pos >> 6, c1 = pos & 63;
    int l2 = l1 >> 6, c2 = l1 & 63;
    int l3 = l2 >> 6, c3 = l2 & 63;
    {
        uint64_t b = 1ull << l3;
        if (f4 & b){ f3[l3] = ~0ull; z3[l3] = ~0ull; }
        else if (!(z4 & b)){ f3[l3] = 0; z3[l3] = 0; }
    }
    {
        uint64_t b = 1ull << c3;
        if (f3[l3] & b){ f2[l2] = ~0ull; z2[l2] = ~0ull; }
        else if (!(z3[l3] & b)){ f2[l2] = 0; z2[l2] = 0; }
    }
    {
        uint64_t b = 1ull << c2;
        if (f2[l2] & b){ f1[l1] = ~0ull; z1[l1] = ~0ull; }
        else if (!(z2[l2] & b)){ f1[l1] = 0; z1[l1] = 0; }
    }
    uint32_t old, nv, ovf;
    {
        uint64_t b = 1ull << c1;
        if (f1[l1] & b) old = FULL;
        else if (!(z1[l1] & b)) old = 0;
        else old = blk[pos];
        uint64_t s = (uint64_t)old + v;
        nv = (uint32_t)s; ovf = (uint32_t)(s >> 32);
        blk[pos] = nv;
        if (nv == FULL) f1[l1] |= b; else f1[l1] &= ~b;
        if (nv != 0) z1[l1] |= b; else z1[l1] &= ~b;
    }
    {
        uint64_t b = 1ull << c2;
        if (f1[l1] == ~0ull) f2[l2] |= b; else f2[l2] &= ~b;
        if (z1[l1] != 0) z2[l2] |= b; else z2[l2] &= ~b;
    }
    {
        uint64_t b = 1ull << c3;
        if (f2[l2] == ~0ull) f3[l3] |= b; else f3[l3] &= ~b;
        if (z2[l2] != 0) z3[l3] |= b; else z3[l3] &= ~b;
    }
    {
        uint64_t b = 1ull << l3;
        if (f3[l3] == ~0ull) f4 |= b; else f4 &= ~b;
        if (z3[l3] != 0) z4 |= b; else z4 &= ~b;
    }
    return ovf;
}

static inline uint32_t point_sub(int pos, uint32_t v){
    int l1 = pos >> 6, c1 = pos & 63;
    int l2 = l1 >> 6, c2 = l1 & 63;
    int l3 = l2 >> 6, c3 = l2 & 63;
    {
        uint64_t b = 1ull << l3;
        if (f4 & b){ f3[l3] = ~0ull; z3[l3] = ~0ull; }
        else if (!(z4 & b)){ f3[l3] = 0; z3[l3] = 0; }
    }
    {
        uint64_t b = 1ull << c3;
        if (f3[l3] & b){ f2[l2] = ~0ull; z2[l2] = ~0ull; }
        else if (!(z3[l3] & b)){ f2[l2] = 0; z2[l2] = 0; }
    }
    {
        uint64_t b = 1ull << c2;
        if (f2[l2] & b){ f1[l1] = ~0ull; z1[l1] = ~0ull; }
        else if (!(z2[l2] & b)){ f1[l1] = 0; z1[l1] = 0; }
    }
    uint32_t old, nv, ovf;
    {
        uint64_t b = 1ull << c1;
        if (f1[l1] & b) old = FULL;
        else if (!(z1[l1] & b)) old = 0;
        else old = blk[pos];
        uint64_t s = (uint64_t)old - v;
        nv = (uint32_t)s; ovf = (uint32_t)(s >> 63);   /* borrow if underflow */
        blk[pos] = nv;
        if (nv == FULL) f1[l1] |= b; else f1[l1] &= ~b;
        if (nv != 0) z1[l1] |= b; else z1[l1] &= ~b;
    }
    {
        uint64_t b = 1ull << c2;
        if (f1[l1] == ~0ull) f2[l2] |= b; else f2[l2] &= ~b;
        if (z1[l1] != 0) z2[l2] |= b; else z2[l2] &= ~b;
    }
    {
        uint64_t b = 1ull << c3;
        if (f2[l2] == ~0ull) f3[l3] |= b; else f3[l3] &= ~b;
        if (z2[l2] != 0) z3[l3] |= b; else z3[l3] &= ~b;
    }
    {
        uint64_t b = 1ull << l3;
        if (f3[l3] == ~0ull) f4 |= b; else f4 &= ~b;
        if (z3[l3] != 0) z4 |= b; else z4 &= ~b;
    }
    return ovf;
}

/* ---- find (top-down, 4 levels) ---- */

static inline int find_nf(int pos){
    int l1 = pos >> 6, c1 = pos & 63;
    int l2 = l1 >> 6, c2 = l1 & 63;
    int l3 = l2 >> 6, c3 = l2 & 63;
    uint64_t m4 = ~f4 >> l3;
    while (m4){
        int l3n = l3 + ctz(m4);
        uint64_t b4 = 1ull << l3n;
        if (!(z4 & b4)) return (l3n > l3) ? (l3n << 18) : pos;
        int c3s = (l3n == l3) ? c3 : 0;
        uint64_t m3 = ~f3[l3n] >> c3s;
        while (m3){
            int c3r = c3s + ctz(m3);
            uint64_t b3 = 1ull << c3r;
            int l2n = (l3n << 6) + c3r;
            if (!(z3[l3n] & b3)){
                int st = l2n << 12;
                return (st > pos) ? st : pos;
            }
            int c2s = (l2n == l2) ? c2 : 0;
            uint64_t m2 = ~f2[l2n] >> c2s;
            while (m2){
                int c2r = c2s + ctz(m2);
                uint64_t b2 = 1ull << c2r;
                int l1n = (l2n << 6) + c2r;
                if (!(z2[l2n] & b2)){
                    int st = l1n << 6;
                    return (st > pos) ? st : pos;
                }
                int c1s = (l1n == l1) ? c1 : 0;
                uint64_t m1 = ~f1[l1n] >> c1s;
                if (m1) return (l1n << 6) + c1s + ctz(m1);
                m2 &= m2 - 1;
            }
            m3 &= m3 - 1;
        }
        m4 &= m4 - 1;
    }
    return -1;
}

static inline int find_nz(int pos){
    int l1 = pos >> 6, c1 = pos & 63;
    int l2 = l1 >> 6, c2 = l1 & 63;
    int l3 = l2 >> 6, c3 = l2 & 63;
    uint64_t m4 = z4 >> l3;
    while (m4){
        int l3n = l3 + ctz(m4);
        uint64_t b4 = 1ull << l3n;
        if (f4 & b4) return (l3n > l3) ? (l3n << 18) : pos;
        int c3s = (l3n == l3) ? c3 : 0;
        uint64_t m3 = z3[l3n] >> c3s;
        while (m3){
            int c3r = c3s + ctz(m3);
            uint64_t b3 = 1ull << c3r;
            int l2n = (l3n << 6) + c3r;
            if (f3[l3n] & b3){
                int st = l2n << 12;
                return (st > pos) ? st : pos;
            }
            int c2s = (l2n == l2) ? c2 : 0;
            uint64_t m2 = z2[l2n] >> c2s;
            while (m2){
                int c2r = c2s + ctz(m2);
                uint64_t b2 = 1ull << c2r;
                int l1n = (l2n << 6) + c2r;
                if (f2[l2n] & b2){
                    int st = l1n << 6;
                    return (st > pos) ? st : pos;
                }
                int c1s = (l1n == l1) ? c1 : 0;
                uint64_t m1 = z1[l1n] >> c1s;
                if (m1) return (l1n << 6) + c1s + ctz(m1);
                m2 &= m2 - 1;
            }
            m3 &= m3 - 1;
        }
        m4 &= m4 - 1;
    }
    return -1;
}

/* ---- set_range (4 levels) ---- */

static inline void __attribute__((always_inline)) upd_l3(int l3){
    uint64_t b = 1ull << l3;
    if (f3[l3] == ~0ull) f4 |= b; else f4 &= ~b;
    if (z3[l3] != 0) z4 |= b; else z4 &= ~b;
}
static inline void __attribute__((always_inline)) upd_l2(int l2){
    uint64_t b = 1ull << (l2 & 63);
    int l3 = l2 >> 6;
    if (f2[l2] == ~0ull) f3[l3] |= b; else f3[l3] &= ~b;
    if (z2[l2] != 0) z3[l3] |= b; else z3[l3] &= ~b;
}
static inline void __attribute__((always_inline)) set_r1(int l1, int cl, int cr, int v){
    uint64_t mask = (~0ull >> (64 - (cr - cl + 1))) << cl;
    if (v == 2){ f1[l1] |= mask; z1[l1] |= mask; }
    else { f1[l1] &= ~mask; z1[l1] &= ~mask; }
    int l2 = l1 >> 6;
    uint64_t b2 = 1ull << (l1 & 63);
    if (f1[l1] == ~0ull) f2[l2] |= b2; else f2[l2] &= ~b2;
    if (z1[l1] != 0) z2[l2] |= b2; else z2[l2] &= ~b2;
}
static inline void __attribute__((always_inline)) set_r2(int l2, int l, int r, int v){
    int l1l = l >> 6, l1r = r >> 6;
    if (l1l == l1r){ set_r1(l1l, l & 63, r & 63, v); upd_l2(l2); return; }
    int fl = ((l & 63) == 0) ? l1l : l1l + 1;
    int fr = ((r & 63) == 63) ? l1r : l1r - 1;
    if (fl <= fr){
        uint64_t mask = (~0ull >> (64 - (fr - fl + 1))) << fl;
        if (v == 2){ f2[l2] |= mask; z2[l2] |= mask; }
        else { f2[l2] &= ~mask; z2[l2] &= ~mask; }
    }
    if (fl > l1l) set_r1(l1l, l & 63, 63, v);
    if (fr < l1r) set_r1(l1r, 0, r & 63, v);
    upd_l2(l2);
}
static inline void __attribute__((always_inline)) set_r3(int l3, int l, int r, int v){
    int l2l = l >> 12, l2r = r >> 12;
    if (l2l == l2r){ set_r2(l2l, l, r, v); upd_l3(l3); return; }
    int fl = ((l & 4095) == 0) ? l2l : l2l + 1;
    int fr = ((r & 4095) == 4095) ? l2r : l2r - 1;
    if (fl <= fr){
        uint64_t mask = (~0ull >> (64 - (fr - fl + 1))) << fl;
        if (v == 2){ f3[l3] |= mask; z3[l3] |= mask; }
        else { f3[l3] &= ~mask; z3[l3] &= ~mask; }
    }
    if (fl > l2l) set_r2(l2l, l, (l2l + 1) * 4096 - 1, v);
    if (fr < l2r) set_r2(l2r, l2r * 4096, r, v);
    upd_l3(l3);
}
static inline void __attribute__((always_inline)) set_range(int l, int r, int v){
    if (l > r) return;
    int l3l = l >> 18, l3r = r >> 18;
    if (l3l == l3r){ set_r3(l3l, l, r, v); return; }
    int fl = ((l & 262143) == 0) ? l3l : l3l + 1;
    int fr = ((r & 262143) == 262143) ? l3r : l3r - 1;
    if (fl <= fr){
        uint64_t mask = (~0ull >> (64 - (fr - fl + 1))) << fl;
        if (v == 2){ f4 |= mask; z4 |= mask; }
        else { f4 &= ~mask; z4 &= ~mask; }
    }
    if (fl > l3l) set_r3(l3l, l, (l3l + 1) * 262144 - 1, v);
    if (fr < l3r) set_r3(l3r, l3r * 262144, r, v);
}

/* ---- carry / borrow ---- */

static inline void carry_add(int p){
    int j = find_nf(p);
    if (j < 0) return;
    if (j - 1 >= p) set_range(p, j - 1, 0);
    point_add(j, (uint32_t)1);
}
static inline void borrow_sub(int p){
    int j = find_nz(p);
    if (j < 0) return;
    if (j - 1 >= p) set_range(p, j - 1, 2);
    point_sub(j, (uint32_t)1);
}

static inline void add_val(int q, int r, uint32_t av){
    uint64_t v = (uint64_t)av << r;
    uint32_t lo = (uint32_t)v, hi = (uint32_t)(v >> 32);
    uint32_t c = point_add(q, lo);
    if (point_add(q + 1, hi + c)) carry_add(q + 2);
}
static inline void sub_val(int q, int r, uint32_t av){
    uint64_t v = (uint64_t)av << r;
    uint32_t lo = (uint32_t)v, hi = (uint32_t)(v >> 32);
    uint32_t c = point_sub(q, lo);
    if (point_sub(q + 1, hi + c)) 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;
}

__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();

    for (int i = 0; i < n; i++){
        int op = rd();
        if (op == 1){
            int a = rds();
            int b = rd();
            int q = b >> 5;
            int r = b & 31;
            if (a > 0) add_val(q, r, (uint32_t)a);
            else if (a < 0) sub_val(q, r, (uint32_t)(-(int64_t)a));
        } else {
            int k = rd();
            int q = k >> 5;
            int r = k & 31;
            uint32_t v;
            {
                int l1 = q >> 6, c1 = q & 63;
                int l2 = l1 >> 6, c2 = l1 & 63;
                int l3 = l2 >> 6, c3 = l2 & 63;
                uint64_t b4 = 1ull << l3;
                if (f4 & b4) v = 1;
                else if (!(z4 & b4)) v = 0;
                else {
                    uint64_t b3 = 1ull << c3;
                    if (f3[l3] & b3) v = 1;
                    else if (!(z3[l3] & b3)) v = 0;
                    else {
                        uint64_t b2 = 1ull << c2;
                        if (f2[l2] & b2) v = 1;
                        else if (!(z2[l2] & b2)) v = 0;
                        else {
                            uint64_t b1 = 1ull << c1;
                            if (f1[l1] & b1) v = 1;
                            else if (!(z1[l1] & b1)) v = 0;
                            else v = (blk[q] >> r) & 1;
                        }
                    }
                }
            }
            out[O++] = (char)('0' + (v & 1));
            out[O++] = '\n';
        }
    }
    done(O, di, out, use_di);
}

评测结果