代码

#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 NLEAF (1<<19)         /* 524288 leaves, covers 470000 blocks */
#define NB 470000

static uint64_t blk[NLEAF];
static uint8_t st[2*NLEAF];   /* 0=zero, 1=mixed, 2=full */
static uint8_t lz[2*NLEAF];   /* 0=none, 1=zero, 2=full (internal only) */

static const char *P;
static uint64_t O;

static inline void apply(int node, int v){
    st[node] = (uint8_t)v;
    if (node < NLEAF) lz[node] = (uint8_t)(v == 2 ? 2 : 1);  /* lz: 0=none, 1=zero, 2=full */
    else blk[node - NLEAF] = (v == 2) ? FULL : 0ull;
}
static inline void push(int node){
    int v = lz[node];
    if (v){
        int sv = (v == 2) ? 2 : 0;
        apply(node<<1, sv);
        apply(node<<1|1, sv);
        lz[node] = 0;
    }
}
static inline void pull(int node){
    int a = st[node<<1], b = st[node<<1|1];
    st[node] = (uint8_t)((a == b) ? a : 1);
}

/* first leaf >= pos whose state != 2 (not full). Returns -1 if none. */
static int find_nf(int node, int l, int r, int pos){
    if (r < pos) return -1;
    int s = st[node];
    if (s == 2) return -1;
    if (l == r) return l;
    if (s == 0) return (l > pos) ? l : pos;
    int mid = (l + r) >> 1;
    int res = find_nf(node<<1, l, mid, pos);
    if (res != -1) return res;
    return find_nf(node<<1|1, mid+1, r, pos);
}
/* first leaf >= pos whose state != 0 (nonzero). */
static int find_nz(int node, int l, int r, int pos){
    if (r < pos) return -1;
    int s = st[node];
    if (s == 0) return -1;
    if (l == r) return l;
    if (s == 2) return (l > pos) ? l : pos;
    int mid = (l + r) >> 1;
    int res = find_nz(node<<1, l, mid, pos);
    if (res != -1) return res;
    return find_nz(node<<1|1, mid+1, r, pos);
}

static void set_range(int node, int l, int r, int ql, int qr, int v){
    if (ql <= l && r <= qr){ apply(node, v); return; }
    push(node);
    int mid = (l + r) >> 1;
    if (ql <= mid) set_range(node<<1, l, mid, ql, qr, v);
    if (qr > mid)  set_range(node<<1|1, mid+1, r, ql, qr, v);
    pull(node);
}

/* add v to leaf pos; return 1 on overflow */
static int point_add(int node, int l, int r, int pos, uint64_t v){
    if (l == r){
        uint64_t old = blk[l];
        uint64_t nv = old + v;
        blk[l] = nv;
        st[node] = (uint8_t)((nv == 0) ? 0 : (nv == FULL) ? 2 : 1);
        return nv < old;
    }
    push(node);
    int mid = (l + r) >> 1;
    int ovf = (pos <= mid) ? point_add(node<<1, l, mid, pos, v)
                           : point_add(node<<1|1, mid+1, r, pos, v);
    pull(node);
    return ovf;
}
/* subtract v from leaf pos; return 1 on underflow */
static int point_sub(int node, int l, int r, int pos, uint64_t v){
    if (l == r){
        uint64_t old = blk[l];
        uint64_t nv = old - v;
        blk[l] = nv;
        st[node] = (uint8_t)((nv == 0) ? 0 : (nv == FULL) ? 2 : 1);
        return nv > old;
    }
    push(node);
    int mid = (l + r) >> 1;
    int ovf = (pos <= mid) ? point_sub(node<<1, l, mid, pos, v)
                           : point_sub(node<<1|1, mid+1, r, pos, v);
    pull(node);
    return ovf;
}

static uint64_t get_block(int node, int l, int r, int pos){
    if (st[node] == 0) return 0;
    if (st[node] == 2) return FULL;
    if (l == r) return blk[l];
    int mid = (l + r) >> 1;
    if (pos <= mid) return get_block(node<<1, l, mid, pos);
    return get_block(node<<1|1, mid+1, r, pos);
}

static inline void carry_add(int p){
    int j = find_nf(1, 0, NLEAF-1, p);
    if (j < 0) return;
    if (j - 1 >= p) set_range(1, 0, NLEAF-1, p, j-1, 0);
    point_add(1, 0, NLEAF-1, j, 1);
}
static inline void borrow_sub(int p){
    int j = find_nz(1, 0, NLEAF-1, p);
    if (j < 0) return;
    if (j - 1 >= p) set_range(1, 0, NLEAF-1, p, j-1, 2);
    point_sub(1, 0, NLEAF-1, 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(1, 0, NLEAF-1, q, lo)) carry_add(q+1);
    if (hi && point_add(1, 0, NLEAF-1, 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(1, 0, NLEAF-1, q, lo)) borrow_sub(q+1);
    if (hi && point_sub(1, 0, NLEAF-1, q+1, 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 >> 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(1, 0, NLEAF-1, k >> 6);
            int bit = (int)((bv >> (k & 63)) & 1);
            out[O++] = (char)('0' + bit);
            out[O++] = '\n';
        }
    }
    done(O, di, out, use_di);
}

评测结果