代码

#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));

typedef unsigned __int128 u128;
#define FULL ((u128)-1)
#define NB 234496      /* 128-bit blocks, covers 30n+30 bits for n=1e6 */
#define NW 8           /* words per mask (512 bits) */
#define N1 458         /* chunks = NB/512 */

static u128 blk[NB];
static uint64_t fm1[N1*NW], nm1[N1*NW];   /* chunk masks, 512-bit each */
static uint64_t fm0[NW], nm0[NW];         /* root, 512-bit over N1 chunks */

static const char *P;
static uint64_t O;

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

/* materialize chunk l1 from root (only if lazy full/zero) */
static inline void mat_chunk(int l1){
    int w = l1 >> 6;
    uint64_t b = 1ull << (l1 & 63);
    uint64_t *f = fm1 + l1*NW, *n = nm1 + l1*NW;
    if (fm0[w] & b) {
        for (int i=0;i<NW;i++){ f[i]=~0ull; n[i]=~0ull; }
    } else if (!(nm0[w] & b)) {
        for (int i=0;i<NW;i++){ f[i]=0; n[i]=0; }
    }
}

static inline int point_add(int pos, u128 v){
    int l1 = pos >> 9, off = pos & 511;
    mat_chunk(l1);
    int w1 = off >> 6;
    uint64_t b1 = 1ull << (off & 63);
    uint64_t *f = fm1 + l1*NW, *n = nm1 + l1*NW;
    u128 old;
    if (f[w1] & b1) old = FULL;
    else if (!(n[w1] & b1)) old = 0;
    else old = blk[pos];
    u128 nv = old + v;
    blk[pos] = nv;
    int ovf = nv < old;
    if (nv == FULL) f[w1] |= b1; else f[w1] &= ~b1;
    if (nv != 0) n[w1] |= b1; else n[w1] &= ~b1;
    {
        int w0 = l1 >> 6;
        uint64_t b0 = 1ull << (l1 & 63);
        if (nv == FULL) {
            uint64_t af = f[0]&f[1]&f[2]&f[3]&f[4]&f[5]&f[6]&f[7];
            if (af == ~0ull) fm0[w0] |= b0;
        } else {
            fm0[w0] &= ~b0;
        }
        if (nv != 0) {
            nm0[w0] |= b0;
        } else {
            uint64_t an = n[0]|n[1]|n[2]|n[3]|n[4]|n[5]|n[6]|n[7];
            if (!an) nm0[w0] &= ~b0;
        }
    }
    return ovf;
}

static inline int point_sub(int pos, u128 v){
    int l1 = pos >> 9, off = pos & 511;
    mat_chunk(l1);
    int w1 = off >> 6;
    uint64_t b1 = 1ull << (off & 63);
    uint64_t *f = fm1 + l1*NW, *n = nm1 + l1*NW;
    u128 old;
    if (f[w1] & b1) old = FULL;
    else if (!(n[w1] & b1)) old = 0;
    else old = blk[pos];
    u128 nv = old - v;
    blk[pos] = nv;
    int ovf = nv > old;
    if (nv == FULL) f[w1] |= b1; else f[w1] &= ~b1;
    if (nv != 0) n[w1] |= b1; else n[w1] &= ~b1;
    {
        int w0 = l1 >> 6;
        uint64_t b0 = 1ull << (l1 & 63);
        if (nv == FULL) {
            uint64_t af = f[0]&f[1]&f[2]&f[3]&f[4]&f[5]&f[6]&f[7];
            if (af == ~0ull) fm0[w0] |= b0;
        } else {
            fm0[w0] &= ~b0;
        }
        if (nv != 0) {
            nm0[w0] |= b0;
        } else {
            uint64_t an = n[0]|n[1]|n[2]|n[3]|n[4]|n[5]|n[6]|n[7];
            if (!an) nm0[w0] &= ~b0;
        }
    }
    return ovf;
}

/* find first non-full block >= pos */
static inline int find_nf(int pos){
    int l1 = pos >> 9, off = pos & 511;
    int c = l1;
    for (;;) {
        int w = c >> 6;
        uint64_t m = ~fm0[w] >> (c & 63);
        int j = -1;
        if (m) j = c + ctz(m);
        else {
            for (int ww = w+1; ww < NW; ww++) {
                m = ~fm0[ww];
                if (m){ j = (ww << 6) + ctz(m); break; }
            }
        }
        if (j < 0) return -1;
        if (!(nm0[j >> 6] & (1ull << (j & 63)))) return (j > l1) ? (j << 9) : pos;
        int st = (j == l1) ? off : 0;
        int w2 = st >> 6;
        uint64_t m2 = ~fm1[j*NW + w2] >> (st & 63);
        if (m2) return (j << 9) + st + ctz(m2);
        int res = -1;
        for (int ww = w2+1; ww < NW; ww++) {
            m2 = ~fm1[j*NW + ww];
            if (m2){ res = (j << 9) + (ww << 6) + ctz(m2); break; }
        }
        if (res >= 0) return res;
        c = j + 1;
    }
}

/* find first non-zero block >= pos */
static inline int find_nz(int pos){
    int l1 = pos >> 9, off = pos & 511;
    int c = l1;
    for (;;) {
        int w = c >> 6;
        uint64_t m = nm0[w] >> (c & 63);
        int j = -1;
        if (m) j = c + ctz(m);
        else {
            for (int ww = w+1; ww < NW; ww++) {
                m = nm0[ww];
                if (m){ j = (ww << 6) + ctz(m); break; }
            }
        }
        if (j < 0) return -1;
        if (fm0[j >> 6] & (1ull << (j & 63))) return (j > l1) ? (j << 9) : pos;
        int st = (j == l1) ? off : 0;
        int w2 = st >> 6;
        uint64_t m2 = nm1[j*NW + w2] >> (st & 63);
        if (m2) return (j << 9) + st + ctz(m2);
        int res = -1;
        for (int ww = w2+1; ww < NW; ww++) {
            m2 = nm1[j*NW + ww];
            if (m2){ res = (j << 9) + (ww << 6) + ctz(m2); break; }
        }
        if (res >= 0) return res;
        c = j + 1;
    }
}

/* set block bits [l,r] (within one chunk) to full(v=2)/zero(v=0), then bubble */
static inline void set_chunk(int l1, int l, int r, int v){
    uint64_t *f = fm1 + l1*NW, *n = nm1 + l1*NW;
    int wl = l >> 6, wr = r >> 6;
    if (wl == wr) {
        uint64_t mask = (~0ull >> (63 - (r & 63))) & (~0ull << (l & 63));
        if (v == 2){ f[wl] |= mask; n[wl] |= mask; }
        else { f[wl] &= ~mask; n[wl] &= ~mask; }
    } else {
        uint64_t ml = ~0ull << (l & 63);
        uint64_t mr = ~0ull >> (63 - (r & 63));
        if (v == 2){ f[wl] |= ml; f[wr] |= mr; n[wl] |= ml; n[wr] |= mr; }
        else { f[wl] &= ~ml; f[wr] &= ~mr; n[wl] &= ~ml; n[wr] &= ~mr; }
        for (int w = wl+1; w < wr; w++){ f[w] = (v==2)?~0ull:0; n[w] = (v==2)?~0ull:0; }
    }
    /* bubble */
    uint64_t af = f[0]&f[1]&f[2]&f[3]&f[4]&f[5]&f[6]&f[7];
    uint64_t b = 1ull << (l1 & 63);
    int w0 = l1 >> 6;
    if (af == ~0ull) fm0[w0] |= b; else fm0[w0] &= ~b;
    uint64_t an = n[0]|n[1]|n[2]|n[3]|n[4]|n[5]|n[6]|n[7];
    if (an) nm0[w0] |= b; else nm0[w0] &= ~b;
}

/* set chunks [l,r] (root level) to full(v=2)/zero(v=0) */
static inline void set_root(int l, int r, int v){
    int wl = l >> 6, wr = r >> 6;
    if (wl == wr) {
        uint64_t mask = (~0ull >> (63 - (r & 63))) & (~0ull << (l & 63));
        if (v == 2){ fm0[wl] |= mask; nm0[wl] |= mask; }
        else { fm0[wl] &= ~mask; nm0[wl] &= ~mask; }
    } else {
        uint64_t ml = ~0ull << (l & 63);
        uint64_t mr = ~0ull >> (63 - (r & 63));
        if (v == 2){ fm0[wl] |= ml; fm0[wr] |= mr; nm0[wl] |= ml; nm0[wr] |= mr; }
        else { fm0[wl] &= ~ml; fm0[wr] &= ~mr; nm0[wl] &= ~ml; nm0[wr] &= ~mr; }
        for (int w = wl+1; w < wr; w++){ fm0[w] = (v==2)?~0ull:0; nm0[w] = (v==2)?~0ull:0; }
    }
}

/* set blocks [l,r] to full(v=2)/zero(v=0) */
static inline void set_range(int l, int r, int v){
    if (l > r) return;
    int l1l = l >> 9, l1r = r >> 9;
    if (l1l == l1r){ set_chunk(l1l, l & 511, r & 511, v); return; }
    int fl = ((l & 511) == 0) ? l1l : l1l + 1;
    int fr = ((r & 511) == 511) ? l1r : l1r - 1;
    if (fl <= fr) set_root(fl, fr, v);
    if (fl > l1l) set_chunk(l1l, l & 511, 511, v);
    if (fr < l1r) set_chunk(l1r, 0, r & 511, v);
}

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, (u128)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, (u128)1);
}

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

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 >> 7;
            int r = b & 127;
            if (a > 0) add_val(q, r, (uint64_t)a);
            else if (a < 0) sub_val(q, r, (uint64_t)(-(int64_t)a));
        } else {
            int k = rd();
            int q = k >> 7;
            int r = k & 127;
            uint64_t v;
            {
                int l1 = q >> 9, off = q & 511;
                int w0 = l1 >> 6;
                uint64_t b0 = 1ull << (l1 & 63);
                if (fm0[w0] & b0) v = 1;
                else if (!(nm0[w0] & b0)) v = 0;
                else {
                    int w1 = off >> 6;
                    uint64_t b1 = 1ull << (off & 63);
                    uint64_t *f = fm1 + l1*NW, *n = nm1 + l1*NW;
                    if (f[w1] & b1) v = 1;
                    else if (!(n[w1] & 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);
}

评测结果