代码

#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 (~0ull)
#define NB 470016
#define N1 7344
#define N2 115
#define N3 2

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

static uint64_t *const FM[5] = {0, fm1, fm2, fm3, &fm4};
static uint64_t *const NM[5] = {0, nm1, nm2, nm3, &nm4};

static const char *P;
static uint64_t O;

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

/* ---- point add / sub (fully unrolled) ---- */

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

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

/* ---- find (bottom-up, unrolled) ---- */

static int find_nf_r(int level, int node, int base, int pos){
    if (level == 0) return base;
    uint64_t fullmask = FM[level][node];
    int childsz = 1 << (6 * (level - 1));
    int c0 = (pos - base) / childsz;
    if (c0 < 0) c0 = 0;
    if (c0 >= 64) return -1;
    uint64_t m = (~fullmask) >> c0;
    while (m){
        int c = c0 + ctz(m);
        int res = find_nf_r(level - 1, node * 64 + c, base + c * childsz, pos);
        if (res != -1) return res;
        m &= m - 1;
    }
    return -1;
}
static int find_nz_r(int level, int node, int base, int pos){
    if (level == 0) return base;
    uint64_t nzmask = NM[level][node];
    int childsz = 1 << (6 * (level - 1));
    int c0 = (pos - base) / childsz;
    if (c0 < 0) c0 = 0;
    if (c0 >= 64) return -1;
    uint64_t m = nzmask >> c0;
    while (m){
        int c = c0 + ctz(m);
        int res = find_nz_r(level - 1, node * 64 + c, base + c * childsz, pos);
        if (res != -1) return res;
        m &= m - 1;
    }
    return -1;
}
static inline int find_nf(int pos){ return find_nf_r(4, 0, 0, pos); }
static inline int find_nz(int pos){ return find_nz_r(4, 0, 0, pos); }

/* ---- set_range (recursive, from v3) ---- */

static void set_range(int level, int node, int base, int l, int r, int v){
    int span = 1 << (6 * level);
    if (l <= base && base + span - 1 <= r){
        if (v == 2){ FM[level][node] = ~0ull; NM[level][node] = ~0ull; }
        else { FM[level][node] = 0; NM[level][node] = 0; }
        return;
    }
    if (level == 1){
        int cl = (l > base) ? (l - base) : 0;
        int cr = (r < base + 63) ? (r - base) : 63;
        uint64_t mask = ((1ull << (cr - cl + 1)) - 1) << cl;
        if (v == 2){ fm1[node] |= mask; nm1[node] |= mask; }
        else { fm1[node] &= ~mask; nm1[node] &= ~mask; }
        return;
    }
    int childsz = span >> 6;
    int cl = (l > base) ? ((l - base) / childsz) : 0;
    int cr = (r - base) / childsz;
    if (cr > 63) cr = 63;
    int fl = (base + cl * childsz >= l) ? cl : cl + 1;
    int fr = (base + (cr + 1) * childsz - 1 <= r) ? cr : cr - 1;
    if (fl <= fr){
        uint64_t mask = ((1ull << (fr - fl + 1)) - 1) << fl;
        if (v == 2){ FM[level][node] |= mask; NM[level][node] |= mask; }
        else { FM[level][node] &= ~mask; NM[level][node] &= ~mask; }
    }
    int bl = (cl < fl) ? cl : -1;
    int br = (cr > fr) ? cr : -1;
    if (bl >= 0){
        int child = node * 64 + bl;
        uint64_t bit = 1ull << bl;
        if (FM[level][node] & bit){ FM[level-1][child] = ~0ull; NM[level-1][child] = ~0ull; }
        else if (!(NM[level][node] & bit)){ FM[level-1][child] = 0; NM[level-1][child] = 0; }
        set_range(level - 1, child, base + bl * childsz, l, r, v);
        int cf = (FM[level-1][child] == ~0ull);
        int cn = (NM[level-1][child] != 0);
        if (cf) FM[level][node] |= bit; else FM[level][node] &= ~bit;
        if (cn) NM[level][node] |= bit; else NM[level][node] &= ~bit;
    }
    if (br >= 0 && br != bl){
        int child = node * 64 + br;
        uint64_t bit = 1ull << br;
        if (FM[level][node] & bit){ FM[level-1][child] = ~0ull; NM[level-1][child] = ~0ull; }
        else if (!(NM[level][node] & bit)){ FM[level-1][child] = 0; NM[level-1][child] = 0; }
        set_range(level - 1, child, base + br * childsz, l, r, v);
        int cf = (FM[level-1][child] == ~0ull);
        int cn = (NM[level-1][child] != 0);
        if (cf) FM[level][node] |= bit; else FM[level][node] &= ~bit;
        if (cn) NM[level][node] |= bit; else NM[level][node] &= ~bit;
    }
}

/* ---- query ---- */

static inline uint64_t get_block(int pos){
    int l3 = pos >> 18;
    int l2 = pos >> 12;
    int l1 = pos >> 6;
    uint64_t b4 = 1ull << l3;
    if (fm4 & b4) return FULL;
    if (!(nm4 & b4)) return 0;
    uint64_t b3 = 1ull << (l2 & 63);
    if (fm3[l3] & b3) return FULL;
    if (!(nm3[l3] & b3)) return 0;
    uint64_t b2 = 1ull << (l1 & 63);
    if (fm2[l2] & b2) return FULL;
    if (!(nm2[l2] & b2)) return 0;
    uint64_t b1 = 1ull << (pos & 63);
    if (fm1[l1] & b1) return FULL;
    if (!(nm1[l1] & b1)) return 0;
    return blk[pos];
}

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

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

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

__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 >> 6;
            int r = b & 63;
            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();
            uint64_t bv = get_block(k >> 6);
            int bit = (int)((bv >> (k & 63)) & 1);
            out[O++] = (char)('0' + bit);
            out[O++] = '\n';
        }
    }
    done(O, di, out, use_di);
}

评测结果