代码

#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 NB 470000
#define NS ((NB+63)>>6)
#define FULL (~0ull)

static uint64_t block[NB];
static uint64_t ful[NS];   // bit=1 iff block is FULL
static uint64_t nz[NS];    // bit=1 iff block is nonzero

static const char *P;      // parse pointer
static uint64_t O;         // output index

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

static inline int find_notfull(int p){
    int w = p >> 6;
    uint64_t m = ~ful[w] >> (p & 63);
    if (m) return p + ctzll_(m);
    while (ful[++w] == FULL) {}
    return (w << 6) + ctzll_(~ful[w]);
}

static inline int find_notzero(int p){
    int w = p >> 6;
    uint64_t m = nz[w] >> (p & 63);
    if (m) return p + ctzll_(m);
    while (nz[++w] == 0) {}
    return (w << 6) + ctzll_(nz[w]);
}

static inline void set_bit0(uint64_t *a, int i, int v){
    int w = i >> 6; uint64_t b = 1ull << (i & 63);
    if (v) a[w] |= b; else a[w] &= ~b;
}

// add v to block[i]; update bitsets; return overflow
static inline int add_block(int i, uint64_t v){
    uint64_t old = block[i];
    uint64_t nv = old + v;
    block[i] = nv;
    int w = i >> 6; uint64_t b = 1ull << (i & 63);
    if (nv) nz[w] |= b; else nz[w] &= ~b;
    if (nv == FULL) ful[w] |= b; else ful[w] &= ~b;
    return nv < old;
}

static inline int sub_block(int i, uint64_t v){
    uint64_t old = block[i];
    uint64_t nv = old - v;
    block[i] = nv;
    int w = i >> 6; uint64_t b = 1ull << (i & 63);
    if (nv) nz[w] |= b; else nz[w] &= ~b;
    if (nv == FULL) ful[w] |= b; else ful[w] &= ~b;
    return nv > old;
}

static inline void inc_block(int i){
    block[i] += 1;
    int w = i >> 6; uint64_t b = 1ull << (i & 63);
    nz[w] |= b;
    if (block[i] == FULL) ful[w] |= b;
    // else ful already 0 (was not full before, +1 only becomes full or stays not-full)
}

static inline void dec_block(int i){
    block[i] -= 1;
    int w = i >> 6; uint64_t b = 1ull << (i & 63);
    if (block[i]) nz[w] |= b; else nz[w] &= ~b;
    ful[w] &= ~b;
}

static inline void zero_range(int l, int r){
    for (int i = l; i <= r; i++){
        block[i] = 0;
        set_bit0(nz, i, 0);
        set_bit0(ful, i, 0);
    }
}

static inline void one_range(int l, int r){
    for (int i = l; i <= r; i++){
        block[i] = FULL;
        set_bit0(nz, i, 1);
        set_bit0(ful, i, 1);
    }
}

static inline void carry_add(int p){
    int j = find_notfull(p);
    zero_range(p, j-1);
    inc_block(j);
}

static inline void borrow_sub(int p){
    int j = find_notzero(p);
    one_range(p, j-1);
    dec_block(j);
}

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 (add_block(q, lo)) carry_add(q+1);
    if (add_block(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 (sub_block(q, lo)) borrow_sub(q+1);
    if (sub_block(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 = read(0, lbuf, sizeof(lbuf));
        lbuf[n2] = 0;
        P = lbuf;
        out = obuf;
    }

    int n = rd();
    rd(); rd(); rd(); // t1 t2 t3

    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 sub_val(q, r, (uint64_t)(-(int64_t)a));
        } else {
            int k = rd();
            int bit = (int)((block[k>>6] >> (k & 63)) & 1);
            out[O++] = (char)('0' + bit);
            out[O++] = '\n';
        }
    }
    done(O, di, out, use_di);
}

评测结果