代码

#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 SZ (1<<20)
#define MASK 0x3FFFFFFFu
#define FULL_FLAG (1u<<30)
#define NZ_FLAG   (1u<<31)

static uint32_t t[2*SZ];   /* leaves = value|flags, internal = flags */
static int has_lazy;

static const char *P;
static uint64_t O;

static inline int ctz(uint32_t x){ return __builtin_ctz(x); }

/* materialize path to leaf q; returns actual leaf value */
static inline uint32_t mat_read(int q){
    int node = 1;
    for (int i = 19; i >= 0; i--){
        uint32_t f = t[node];
        if (f == 0 || (f & FULL_FLAG)){ t[node<<1] = f; t[node<<1|1] = f; }
        node = (node << 1) | ((q >> i) & 1);
    }
    uint32_t f = t[node];
    return (f == 0) ? 0 : (f & FULL_FLAG) ? MASK : (t[node] & MASK);
}

static inline int point_add(int q, uint32_t v){
    int idx = SZ + q;
    uint32_t old_flags, oldv;
    if (has_lazy){
        old_flags = 0;  /* recompute below */
        oldv = mat_read(q);
        old_flags = ((oldv == MASK) ? FULL_FLAG : 0) | ((oldv != 0) ? NZ_FLAG : 0);
    } else {
        uint32_t old = t[idx];
        oldv = old & MASK;
        old_flags = old & (FULL_FLAG | NZ_FLAG);
    }
    uint32_t nv = oldv + v;
    int carry = nv >> 30;
    uint32_t n30 = nv & MASK;
    uint32_t new_flags = ((n30 == MASK) ? FULL_FLAG : 0) | ((n30 != 0) ? NZ_FLAG : 0);
    t[idx] = n30 | new_flags;
    if (new_flags != old_flags){
        for (int node = idx >> 1; node >= 1; node >>= 1){
            uint32_t flags = ((t[node<<1] & t[node<<1|1]) & FULL_FLAG)
                           | ((t[node<<1] | t[node<<1|1]) & NZ_FLAG);
            if (flags == t[node]) break;
            t[node] = flags;
        }
    }
    return carry;
}

static inline int point_sub(int q, uint32_t v){
    int idx = SZ + q;
    uint32_t old_flags, oldv;
    if (has_lazy){
        oldv = mat_read(q);
        old_flags = ((oldv == MASK) ? FULL_FLAG : 0) | ((oldv != 0) ? NZ_FLAG : 0);
    } else {
        uint32_t old = t[idx];
        oldv = old & MASK;
        old_flags = old & (FULL_FLAG | NZ_FLAG);
    }
    int32_t nv = (int32_t)oldv - (int32_t)v;
    int borrow = nv < 0;
    uint32_t res = borrow ? (uint32_t)(nv + (1<<30)) : (uint32_t)nv;
    uint32_t new_flags = ((res == MASK) ? FULL_FLAG : 0) | ((res != 0) ? NZ_FLAG : 0);
    t[idx] = res | new_flags;
    if (new_flags != old_flags){
        for (int node = idx >> 1; node >= 1; node >>= 1){
            uint32_t flags = ((t[node<<1] & t[node<<1|1]) & FULL_FLAG)
                           | ((t[node<<1] | t[node<<1|1]) & NZ_FLAG);
            if (flags == t[node]) break;
            t[node] = flags;
        }
    }
    return borrow;
}

static int find_nf(int node, int nl, int nr, int j){
    if (nr <= j) return -1;
    uint32_t f = t[node];
    if (f & FULL_FLAG) return -1;
    if (nr - nl == 1) return nl;
    if (f == 0) return (j > nl) ? j : nl;
    int mid = (nl + nr) >> 1;
    int r = find_nf(node<<1, nl, mid, j);
    if (r != -1) return r;
    return find_nf(node<<1|1, mid, nr, j);
}

static int find_nz(int node, int nl, int nr, int j){
    if (nr <= j) return -1;
    uint32_t f = t[node];
    if (f == 0) return -1;
    if (nr - nl == 1) return nl;
    if (f & FULL_FLAG) return (j > nl) ? j : nl;
    int mid = (nl + nr) >> 1;
    int r = find_nz(node<<1, nl, mid, j);
    if (r != -1) return r;
    return find_nz(node<<1|1, mid, nr, j);
}

/* short-climb (eager flags, no lazy): first leaf >= j not full */
static inline int find_nf_fast(int j){
    int x = SZ + j;
    if (!(t[x] & FULL_FLAG)) return j;
    while (x > 1){
        if (!(x & 1)){   /* left child -> right sibling is to the right */
            int sib = x ^ 1;
            if (!(t[sib] & FULL_FLAG)){ x = sib; break; }
        }
        x >>= 1;
    }
    if (x <= 1) return SZ;
    while (x < SZ){
        x = (x << 1) | ((t[x<<1] & FULL_FLAG) != 0);
    }
    return x - SZ;
}

/* short-climb: first leaf >= j not zero */
static inline int find_nz_fast(int j){
    int x = SZ + j;
    if (t[x] != 0) return j;
    while (x > 1){
        if (!(x & 1)){
            int sib = x ^ 1;
            if (t[sib] != 0){ x = sib; break; }
        }
        x >>= 1;
    }
    if (x <= 1) return SZ;
    while (x < SZ){
        x = (x << 1) | (t[x<<1] == 0);
    }
    return x - SZ;
}

static void range_zero(int node, int nl, int nr, int l, int r){
    if (nr <= l || r <= nl) return;
    if (l <= nl && nr <= r){ t[node] = 0; return; }
    uint32_t f = t[node];
    if (f == 0 || (f & FULL_FLAG)){ t[node<<1] = f; t[node<<1|1] = f; }
    int mid = (nl + nr) >> 1;
    range_zero(node<<1, nl, mid, l, r);
    range_zero(node<<1|1, mid, nr, l, r);
    t[node] = ((t[node<<1] & t[node<<1|1]) & FULL_FLAG) | ((t[node<<1] | t[node<<1|1]) & NZ_FLAG);
}

static void range_full(int node, int nl, int nr, int l, int r){
    if (nr <= l || r <= nl) return;
    if (l <= nl && nr <= r){ t[node] = FULL_FLAG | NZ_FLAG; return; }
    uint32_t f = t[node];
    if (f == 0 || (f & FULL_FLAG)){ t[node<<1] = f; t[node<<1|1] = f; }
    int mid = (nl + nr) >> 1;
    range_full(node<<1, nl, mid, l, r);
    range_full(node<<1|1, mid, nr, l, r);
    t[node] = ((t[node<<1] & t[node<<1|1]) & FULL_FLAG) | ((t[node<<1] | t[node<<1|1]) & NZ_FLAG);
}

static inline void add_val(int q, int r, uint32_t a){
    uint32_t lo = (uint32_t)((uint64_t)a << r) & MASK;
    uint32_t hi = (r == 0) ? 0u : (uint32_t)(a >> (30 - r));
    int c0 = point_add(q, lo);
    int c1 = point_add(q + 1, hi + c0);
    if (c1){
        int start = q + 2;
        int p = has_lazy ? find_nf(1, 0, SZ, start) : find_nf_fast(start);
        if (p > start){ range_zero(1, 0, SZ, start, p); has_lazy = 1; }
        point_add(p, 1);
    }
}

static inline void sub_val(int q, int r, uint32_t a){
    uint32_t lo = (uint32_t)((uint64_t)a << r) & MASK;
    uint32_t hi = (r == 0) ? 0u : (uint32_t)(a >> (30 - r));
    int b0 = point_sub(q, lo);
    int b1 = point_sub(q + 1, hi + b0);
    if (b1){
        int start = q + 2;
        int p = has_lazy ? find_nz(1, 0, SZ, start) : find_nz_fast(start);
        if (p > start){ range_full(1, 0, SZ, start, p); has_lazy = 1; }
        point_sub(p, 1);
    }
}

static inline uint32_t read_limb(int q){
    if (!has_lazy) return t[SZ + q] & MASK;
    int node = 1;
    for (int i = 19; i >= 0; i--){
        uint32_t f = t[node];
        if (f == 0) return 0;
        if (f & FULL_FLAG) return MASK;
        node = (node << 1) | ((q >> i) & 1);
    }
    uint32_t f = t[node];
    if (f == 0) return 0;
    if (f & FULL_FLAG) return MASK;
    return t[node] & MASK;
}

/* ---- parse ---- */

static inline int rd(){
    while (*P <= ' ') P++;
    int v = 0;
    while (*P > ' ') v = v*10 + (*P - '0'), P++;
    return 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++;

    for (int i = 0; i < n; i++){
        int op = *P++ - '0';
        P++;
        if (op == 1){
            int neg = 0;
            if (*P == '-'){ neg = 1; P++; }
            int a = 0;
            while (*P > ' '){ a = a*10 + (*P - '0'); P++; }
            P++;
            int b = 0;
            while (*P > ' '){ b = b*10 + (*P - '0'); P++; }
            P++;
            int q = b / 30;
            int r = b % 30;
            if (neg) sub_val(q, r, (uint32_t)a);
            else if (a) add_val(q, r, (uint32_t)a);
        } else {
            int k = 0;
            while (*P > ' '){ k = k*10 + (*P - '0'); P++; }
            P++;
            int q = k / 30;
            int r = k % 30;
            uint32_t v = read_limb(q);
            out[O++] = (char)('0' + ((v >> r) & 1));
            out[O++] = '\n';
        }
    }
    done(O, di, out, use_di);
}

评测结果