代码

#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 struct { uint64_t w[4]; } u256;
#define NB 117188
#define N1 1832
#define N2 29

static u256 blk[NB];
static uint64_t fm1[N1], nm1[N1];
static uint64_t fm2[N2], nm2[N2];
static uint64_t fm3, nm3;

static const char *P;
static uint64_t O;

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

static inline int is_full(const u256 *b){ return b->w[0]==~0ull && b->w[1]==~0ull && b->w[2]==~0ull && b->w[3]==~0ull; }
static inline int is_zero(const u256 *b){ return (b->w[0]|b->w[1]|b->w[2]|b->w[3])==0; }
static inline void set1(u256 *b){ b->w[0]=1; b->w[1]=0; b->w[2]=0; b->w[3]=0; }
static inline void setfullm1(u256 *b){ b->w[0]=~1ull; b->w[1]=~0ull; b->w[2]=~0ull; b->w[3]=~0ull; }
static inline void incr(u256 *b){ if(++b->w[0]==0) if(++b->w[1]==0) if(++b->w[2]==0) ++b->w[3]; }
static inline void decr(u256 *b){ if(b->w[0]--==0) if(b->w[1]--==0) if(b->w[2]--==0) b->w[3]--; }

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

static inline int point_add(int pos, const uint64_t v[4]){
    int l2 = pos >> 12;
    int l1 = pos >> 6;
    uint64_t b2 = 1ull << (l1 & 63);
    uint64_t b1 = 1ull << (pos & 63);
    uint64_t b3 = 1ull << l2;
    uint64_t f3 = fm3, n3 = nm3;
    uint64_t f2 = fm2[l2], n2 = nm2[l2];
    if (f3 & b3) f2 = n2 = ~0ull;
    else if (!(n3 & b3)) f2 = n2 = 0;
    uint64_t f1 = fm1[l1], n1 = nm1[l1];
    if (f2 & b2) f1 = n1 = ~0ull;
    else if (!(n2 & b2)) f1 = n1 = 0;
    uint64_t nv[4];
    int ovf;
    if (f1 & b1){
        uint64_t borrow = 1;
        nv[0] = v[0] - 1; borrow = (v[0]==0);
        nv[1] = v[1] - borrow; borrow = (v[1]==0 && borrow);
        nv[2] = v[2] - borrow; borrow = (v[2]==0 && borrow);
        nv[3] = v[3] - borrow;
        ovf = (v[0]|v[1]|v[2]|v[3]) != 0;
    } else if (!(n1 & b1)){
        nv[0]=v[0]; nv[1]=v[1]; nv[2]=v[2]; nv[3]=v[3]; ovf = 0;
    } else {
        unsigned __int128 acc;
        uint64_t c;
        acc = (unsigned __int128)blk[pos].w[0] + v[0]; nv[0]=(uint64_t)acc; c = (uint64_t)(acc>>64);
        acc = (unsigned __int128)blk[pos].w[1] + v[1] + c; nv[1]=(uint64_t)acc; c = (uint64_t)(acc>>64);
        acc = (unsigned __int128)blk[pos].w[2] + v[2] + c; nv[2]=(uint64_t)acc; c = (uint64_t)(acc>>64);
        acc = (unsigned __int128)blk[pos].w[3] + v[3] + c; nv[3]=(uint64_t)acc; c = (uint64_t)(acc>>64);
        ovf = (int)c;
    }
    blk[pos].w[0]=nv[0]; blk[pos].w[1]=nv[1]; blk[pos].w[2]=nv[2]; blk[pos].w[3]=nv[3];
    int full = (nv[0]==~0ull && nv[1]==~0ull && nv[2]==~0ull && nv[3]==~0ull);
    int zero = ((nv[0]|nv[1]|nv[2]|nv[3])==0);
    if (full) f1 |= b1; else f1 &= ~b1;
    if (!zero) n1 |= b1; else n1 &= ~b1;
    if (f1 == ~0ull) f2 |= b2; else f2 &= ~b2;
    if (n1 != 0) n2 |= b2; else n2 &= ~b2;
    if (f2 == ~0ull) f3 |= b3; else f3 &= ~b3;
    if (n2 != 0) n3 |= b3; else n3 &= ~b3;
    fm1[l1] = f1; nm1[l1] = n1;
    fm2[l2] = f2; nm2[l2] = n2;
    fm3 = f3; nm3 = n3;
    return ovf;
}

static inline int point_sub(int pos, const uint64_t v[4]){
    int l2 = pos >> 12;
    int l1 = pos >> 6;
    uint64_t b2 = 1ull << (l1 & 63);
    uint64_t b1 = 1ull << (pos & 63);
    uint64_t b3 = 1ull << l2;
    uint64_t f3 = fm3, n3 = nm3;
    uint64_t f2 = fm2[l2], n2 = nm2[l2];
    if (f3 & b3) f2 = n2 = ~0ull;
    else if (!(n3 & b3)) f2 = n2 = 0;
    uint64_t f1 = fm1[l1], n1 = nm1[l1];
    if (f2 & b2) f1 = n1 = ~0ull;
    else if (!(n2 & b2)) f1 = n1 = 0;
    uint64_t nv[4];
    int ovf;
    if (f1 & b1){
        /* old = FULL, nv = FULL - v = ~v; no borrow */
        nv[0] = ~v[0]; nv[1] = ~v[1]; nv[2] = ~v[2]; nv[3] = ~v[3];
        ovf = 0;
    } else if (!(n1 & b1)){
        /* old = 0, nv = 0 - v = -v (two's complement = ~v + 1), borrow = v != 0 */
        unsigned __int128 acc;
        uint64_t c = 1;
        acc = (unsigned __int128)~v[0] + c; nv[0]=(uint64_t)acc; c = (uint64_t)(acc>>64);
        acc = (unsigned __int128)~v[1] + c; nv[1]=(uint64_t)acc; c = (uint64_t)(acc>>64);
        acc = (unsigned __int128)~v[2] + c; nv[2]=(uint64_t)acc; c = (uint64_t)(acc>>64);
        acc = (unsigned __int128)~v[3] + c; nv[3]=(uint64_t)acc;
        ovf = (v[0]|v[1]|v[2]|v[3]) != 0;
    } else {
        unsigned __int128 acc;
        uint64_t c;
        acc = (unsigned __int128)blk[pos].w[0] - v[0]; nv[0]=(uint64_t)acc; c = ((uint64_t)(acc>>64)) & 1;
        acc = (unsigned __int128)blk[pos].w[1] - v[1] - c; nv[1]=(uint64_t)acc; c = ((uint64_t)(acc>>64)) & 1;
        acc = (unsigned __int128)blk[pos].w[2] - v[2] - c; nv[2]=(uint64_t)acc; c = ((uint64_t)(acc>>64)) & 1;
        acc = (unsigned __int128)blk[pos].w[3] - v[3] - c; nv[3]=(uint64_t)acc; c = ((uint64_t)(acc>>64)) & 1;
        ovf = (int)c;
    }
    blk[pos].w[0]=nv[0]; blk[pos].w[1]=nv[1]; blk[pos].w[2]=nv[2]; blk[pos].w[3]=nv[3];
    int full = (nv[0]==~0ull && nv[1]==~0ull && nv[2]==~0ull && nv[3]==~0ull);
    int zero = ((nv[0]|nv[1]|nv[2]|nv[3])==0);
    if (full) f1 |= b1; else f1 &= ~b1;
    if (!zero) n1 |= b1; else n1 &= ~b1;
    if (f1 == ~0ull) f2 |= b2; else f2 &= ~b2;
    if (n1 != 0) n2 |= b2; else n2 &= ~b2;
    if (f2 == ~0ull) f3 |= b3; else f3 &= ~b3;
    if (n2 != 0) n3 |= b3; else n3 &= ~b3;
    fm1[l1] = f1; nm1[l1] = n1;
    fm2[l2] = f2; nm2[l2] = n2;
    fm3 = f3; nm3 = n3;
    return ovf;
}

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

static inline void zero_full_l2(int l2, int off2){
    int pos = (l2 << 12) + off2;
    int l1 = pos >> 6, off = pos & 63;
    int l1in = l1 & 63;
    fm1[l1] = (off == 0) ? 0 : ((1ull << off) - 1);
    nm1[l1] = fm1[l1];
    fm2[l2] = (1ull << l1in) - 1;
    nm2[l2] = (off == 0) ? fm2[l2] : (fm2[l2] | (1ull << l1in));
    uint64_t b3 = 1ull << l2;
    fm3 &= ~b3;
    nm3 |= b3;
}

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 b2 = 1ull << (l1 & 63);
    fm2[l2] &= ~b2;
    nm2[l2] |= b2;
}

static inline void set_full_l2(int l2, int off2){
    int pos = (l2 << 12) + off2;
    int l1 = pos >> 6, off = pos & 63;
    int l1in = l1 & 63;
    fm1[l1] = ~0ull << off;
    nm1[l1] = fm1[l1];
    fm2[l2] = ~0ull << l1in;
    nm2[l2] = fm2[l2];
    uint64_t b3 = 1ull << l2;
    if (fm2[l2] == ~0ull) fm3 |= b3; else fm3 &= ~b3;
    nm3 |= b3;
}

static inline void set_full_l1(int l1, int off){
    fm1[l1] = ~0ull << off;
    nm1[l1] = ~0ull << off;
    int l2 = l1 >> 6;
    uint64_t b2 = 1ull << (l1 & 63);
    if (fm1[l1] == ~0ull) fm2[l2] |= b2; else fm2[l2] &= ~b2;
    nm2[l2] |= b2;
}

/* ---- fused carry ---- */

static inline void carry_add(int p){
    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)){
            if (l2n > l2){
                int l1n = l2n << 6;
                set1(&blk[l2n << 12]);
                fm1[l1n] = 0; nm1[l1n] = 1ull;
                fm2[l2n] = 0; nm2[l2n] = 1ull;
                fm3 &= ~b3; nm3 |= b3;
                return;
            } else {
                uint64_t b1 = 1ull << off;
                set1(&blk[p]);
                fm1[l1] = 0; nm1[l1] = b1;
                uint64_t b2 = 1ull << (l1 & 63);
                fm2[l2] = 0; nm2[l2] = b2;
                fm3 &= ~b3; nm3 |= b3;
                return;
            }
        }
        int c2 = (l2n == l2) ? (l1 & 63) : 0;
        uint64_t m2 = ~fm2[l2n] >> c2;
        int c2pos = c2;
        if (l2n == l2 && off > 0 && (fm2[l2n] & (1ull << c2))){
            zero_full_l1(l1, off);
            c2pos = c2 + 1;
        }
        while (m2){
            int c2r = c2 + ctz(m2);
            uint64_t b2 = 1ull << c2r;
            int l1n = (l2n << 6) + c2r;
            if (c2r > c2pos){
                uint64_t zm = ((1ull << (c2r - c2pos)) - 1) << c2pos;
                fm2[l2n] &= ~zm; nm2[l2n] &= ~zm;
            }
            c2pos = c2r + 1;
            if (!(nm2[l2n] & b2)){
                if (l1n > l1){
                    set1(&blk[l1n << 6]);
                    fm1[l1n] = 0; nm1[l1n] = 1ull;
                    fm2[l2n] &= ~b2; nm2[l2n] |= b2;
                } else {
                    uint64_t b1 = 1ull << off;
                    set1(&blk[p]);
                    fm1[l1] = 0; nm1[l1] = b1;
                    fm2[l2n] &= ~b2; nm2[l2n] |= b2;
                }
                if (fm2[l2n] == ~0ull) fm3 |= b3; else fm3 &= ~b3;
                if (nm2[l2n] != 0) nm3 |= b3; else nm3 &= ~b3;
                return;
            }
            int c1 = (l1n == l1) ? off : 0;
            uint64_t m1 = ~fm1[l1n] >> c1;
            if (m1){
                int c1r = c1 + ctz(m1);
                int j = (l1n << 6) + c1r;
                uint64_t b1 = 1ull << c1r;
                if (c1r > c1){
                    uint64_t zm = ((1ull << (c1r - c1)) - 1) << c1;
                    fm1[l1n] &= ~zm; nm1[l1n] &= ~zm;
                }
                if (nm1[l1n] & b1){
                    incr(&blk[j]);
                    if (is_full(&blk[j])) fm1[l1n] |= b1; else fm1[l1n] &= ~b1;
                    nm1[l1n] |= b1;
                } else {
                    set1(&blk[j]);
                    fm1[l1n] &= ~b1; nm1[l1n] |= b1;
                }
                if (fm1[l1n] == ~0ull) fm2[l2n] |= b2; else fm2[l2n] &= ~b2;
                if (nm1[l1n] != 0) nm2[l2n] |= b2; else nm2[l2n] &= ~b2;
                if (fm2[l2n] == ~0ull) fm3 |= b3; else fm3 &= ~b3;
                if (nm2[l2n] != 0) nm3 |= b3; else nm3 &= ~b3;
                return;
            }
            {
                uint64_t zm = ~0ull << c1;
                fm1[l1n] &= ~zm; nm1[l1n] &= ~zm;
                if (fm1[l1n] == ~0ull) fm2[l2n] |= b2; else fm2[l2n] &= ~b2;
                if (nm1[l1n] != 0) nm2[l2n] |= b2; else nm2[l2n] &= ~b2;
            }
            m2 &= m2 - 1;
        }
        if (c2pos < 64){
            uint64_t zm = ~0ull << c2pos;
            fm2[l2n] &= ~zm; nm2[l2n] &= ~zm;
        }
        if (fm2[l2n] == ~0ull) fm3 |= b3; else fm3 &= ~b3;
        if (nm2[l2n] != 0) nm3 |= b3; else nm3 &= ~b3;
        m3 &= m3 - 1;
    }
}

/* ---- fused borrow ---- */

static inline void borrow_sub(int p){
    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){
            if (l2n > l2){
                int l1n = l2n << 6;
                setfullm1(&blk[l2n << 12]);
                fm1[l1n] = ~0ull ^ 1ull; nm1[l1n] = ~0ull;
                fm2[l2n] = ~0ull ^ 1ull; nm2[l2n] = ~0ull;
                fm3 &= ~b3; nm3 |= b3;
                return;
            } else {
                uint64_t b1 = 1ull << off;
                setfullm1(&blk[p]);
                fm1[l1] = ~0ull ^ b1; nm1[l1] = ~0ull;
                uint64_t b2 = 1ull << (l1 & 63);
                fm2[l2] = ~0ull ^ b2; nm2[l2] = ~0ull;
                fm3 &= ~b3; nm3 |= b3;
                return;
            }
        }
        int c2 = (l2n == l2) ? (l1 & 63) : 0;
        uint64_t m2 = nm2[l2n] >> c2;
        int c2pos = c2;
        if (l2n == l2 && off > 0 && !(nm2[l2n] & (1ull << c2))){
            set_full_l1(l1, off);
            c2pos = c2 + 1;
        }
        while (m2){
            int c2r = c2 + ctz(m2);
            uint64_t b2 = 1ull << c2r;
            int l1n = (l2n << 6) + c2r;
            if (c2r > c2pos){
                uint64_t zm = ((1ull << (c2r - c2pos)) - 1) << c2pos;
                fm2[l2n] |= zm; nm2[l2n] |= zm;
            }
            c2pos = c2r + 1;
            if (fm2[l2n] & b2){
                if (l1n > l1){
                    setfullm1(&blk[l1n << 6]);
                    fm1[l1n] = ~0ull ^ 1ull; nm1[l1n] = ~0ull;
                    fm2[l2n] &= ~b2; nm2[l2n] |= b2;
                } else {
                    uint64_t b1 = 1ull << off;
                    setfullm1(&blk[p]);
                    fm1[l1] = ~0ull ^ b1; nm1[l1] = ~0ull;
                    fm2[l2n] &= ~b2; nm2[l2n] |= b2;
                }
                if (fm2[l2n] == ~0ull) fm3 |= b3; else fm3 &= ~b3;
                if (nm2[l2n] != 0) nm3 |= b3; else nm3 &= ~b3;
                return;
            }
            int c1 = (l1n == l1) ? off : 0;
            uint64_t m1 = nm1[l1n] >> c1;
            if (m1){
                int c1r = c1 + ctz(m1);
                int j = (l1n << 6) + c1r;
                uint64_t b1 = 1ull << c1r;
                if (c1r > c1){
                    uint64_t zm = ((1ull << (c1r - c1)) - 1) << c1;
                    fm1[l1n] |= zm; nm1[l1n] |= zm;
                }
                if (fm1[l1n] & b1){
                    setfullm1(&blk[j]);
                    fm1[l1n] &= ~b1; nm1[l1n] |= b1;
                } else {
                    decr(&blk[j]);
                    if (is_zero(&blk[j])) nm1[l1n] &= ~b1; else nm1[l1n] |= b1;
                }
                if (fm1[l1n] == ~0ull) fm2[l2n] |= b2; else fm2[l2n] &= ~b2;
                if (nm1[l1n] != 0) nm2[l2n] |= b2; else nm2[l2n] &= ~b2;
                if (fm2[l2n] == ~0ull) fm3 |= b3; else fm3 &= ~b3;
                if (nm2[l2n] != 0) nm3 |= b3; else nm3 &= ~b3;
                return;
            }
            {
                uint64_t zm = ~0ull << c1;
                fm1[l1n] |= zm; nm1[l1n] |= zm;
                if (fm1[l1n] == ~0ull) fm2[l2n] |= b2; else fm2[l2n] &= ~b2;
                if (nm1[l1n] != 0) nm2[l2n] |= b2; else nm2[l2n] &= ~b2;
            }
            m2 &= m2 - 1;
        }
        if (c2pos < 64){
            uint64_t zm = ~0ull << c2pos;
            fm2[l2n] |= zm; nm2[l2n] |= zm;
        }
        if (fm2[l2n] == ~0ull) fm3 |= b3; else fm3 &= ~b3;
        if (nm2[l2n] != 0) nm3 |= b3; else nm3 &= ~b3;
        m3 &= m3 - 1;
    }
}

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

static inline void add_val(int q, int r, uint64_t av){
    uint64_t lo[4]; uint64_t hi = 0;
    int w = r >> 6, s = r & 63;
    lo[0]=lo[1]=lo[2]=lo[3]=0;
    lo[w] = av << s;
    if (s > 34){
        uint64_t ch = av >> (64 - s);
        if (w + 1 < 4) lo[w+1] = ch; else hi = ch;
    }
    if (point_add(q, lo)) carry_add(q + 1);
    if (hi){ uint64_t h[4] = {hi,0,0,0}; if (point_add(q+1, h)) carry_add(q + 2); }
}
static inline void sub_val(int q, int r, uint64_t av){
    uint64_t lo[4]; uint64_t hi = 0;
    int w = r >> 6, s = r & 63;
    lo[0]=lo[1]=lo[2]=lo[3]=0;
    lo[w] = av << s;
    if (s > 34){
        uint64_t ch = av >> (64 - s);
        if (w + 1 < 4) lo[w+1] = ch; else hi = ch;
    }
    if (point_sub(q, lo)) borrow_sub(q + 1);
    if (hi){ uint64_t h[4] = {hi,0,0,0}; if (point_sub(q+1, h)) 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();
    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 = 0;
            while (*P > ' '){ b = b*10 + (*P - '0'); P++; }
            P++;  /* skip separator (newline) */
            int q = b >> 8;
            int r = b & 255;
            if (neg) sub_val(q, r, (uint64_t)a);
            else if (a) add_val(q, r, (uint64_t)a);
        } else {
            int k = 0;
            while (*P > ' '){ k = k*10 + (*P - '0'); P++; }
            P++;  /* skip separator (newline) */
            int q = k >> 8;
            int r = k & 255;
            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 b2 = 1ull << (l1 & 63);
                    if (fm2[l2] & b2) v = 1;
                    else if (!(nm2[l2] & b2)) v = 0;
                    else {
                        uint64_t b1 = 1ull << (q & 63);
                        if (fm1[l1] & b1) v = 1;
                        else if (!(nm1[l1] & b1)) v = 0;
                        else v = (blk[q].w[r >> 6] >> (r & 63)) & 1;
                    }
                }
            }
            out[O++] = (char)('0' + (v & 1));
            out[O++] = '\n';
        }
    }
    done(O, di, out, use_di);
}

评测结果