代码

#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 NL   (1<<20)          /* 1048576 limbs, base 2^30 */
#define CH   (16)             /* limbs per chunk */
#define NC   (NL>>4)          /* 65536 chunks */
#define N1   (NC>>6)          /* 1024 */
#define N2   (N1>>6)          /* 16 */
#define MASK 0x3FFFFFFFu
#define FULL MASK

static uint32_t limb[NL];
static uint64_t fm1[N1], nm1[N1];   /* chunk all-full / any-nonzero */
static uint64_t fm2[N2], nm2[N2];
static uint64_t fm3, nm3;           /* root (16 bits) */

static const char *P;
static uint64_t O;

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

/* bubble chunk c up */
static inline void bubble_chunk(int c){
    uint64_t b = 1ull << (c & 63);
    int l1 = c >> 6;
    if (fm1[l1] == ~0ull) fm2[l1>>6] |= (1ull << (l1 & 63));
    else fm2[l1>>6] &= ~(1ull << (l1 & 63));
    if (nm1[l1] != 0) nm2[l1>>6] |= (1ull << (l1 & 63));
    else nm2[l1>>6] &= ~(1ull << (l1 & 63));
    int l2 = l1 >> 6;
    uint64_t b2 = 1ull << (l2 & 63);
    if (fm2[l2] == ~0ull) fm3 |= b2; else fm3 &= ~b2;
    if (nm2[l2] != 0) nm3 |= b2; else nm3 &= ~b2;
}

/* materialize chunk c (make fm1/nm1 bit authoritative) */
static inline void materialize_chunk(int c){
    int l1 = c >> 6, l2 = l1 >> 6;
    uint64_t b2 = 1ull << l2;
    if (fm3 & b2){ fm2[l2] = ~0ull; nm2[l2] = ~0ull; }
    else if (!(nm3 & b2)){ fm2[l2] = 0; nm2[l2] = 0; }
    uint64_t b1 = 1ull << (l1 & 63);
    if (fm2[l2] & b1){ fm1[l1] = ~0ull; nm1[l1] = ~0ull; }
    else if (!(nm2[l2] & b1)){ fm1[l1] = 0; nm1[l1] = 0; }
    /* materialize the chunk's 16 limb VALUES if the chunk is lazy */
    uint64_t bc = 1ull << (c & 63);
    int base = c << 4;
    if (fm1[l1] & bc){
        for (int i = 0; i < 16; i++) limb[base + i] = FULL;
    } else if (!(nm1[l1] & bc)){
        for (int i = 0; i < 16; i++) limb[base + i] = 0;
    }
}

/* actual value of limb q */
static inline uint32_t read_actual(int q){
    int c = q >> 4;
    materialize_chunk(c);
    uint64_t b = 1ull << (c & 63);
    int l1 = c >> 6;
    if (fm1[l1] & b) return FULL;
    if (!(nm1[l1] & b)) return 0;
    return limb[q];
}

/* recompute chunk c's flags from its 16 limb values (chunk is mixed/authoritative) */
static inline void recompute_chunk(int c){
    int base = c << 4;
    uint32_t all_full = 1, any_nz = 0;
    for (int i = 0; i < 16; i++){
        uint32_t v = limb[base + i];
        if (v != FULL) all_full = 0;
        if (v != 0) any_nz = 1;
    }
    uint64_t b = 1ull << (c & 63);
    int l1 = c >> 6;
    if (all_full) fm1[l1] |= b; else fm1[l1] &= ~b;
    if (any_nz) nm1[l1] |= b; else nm1[l1] &= ~b;
    bubble_chunk(c);
}

static inline int point_add(int q, uint32_t v){
    int c = q >> 4;
    materialize_chunk(c);
    uint64_t b = 1ull << (c & 63);
    int l1 = c >> 6;
    int was_full = (fm1[l1] & b) != 0;
    int was_zero = (nm1[l1] & b) == 0;
    uint32_t old;
    if (was_full) old = FULL;
    else if (was_zero) old = 0;
    else old = limb[q];
    uint32_t nv = old + v;
    int carry = nv >> 30;
    uint32_t n30 = nv & MASK;
    limb[q] = n30;
    if (n30 != old){
        if (was_full){
            /* 15 full + n30(<FULL) -> mixed, any nonzero */
            fm1[l1] &= ~b; nm1[l1] |= b; bubble_chunk(c);
        } else if (was_zero){
            /* 15 zero + n30 -> mixed if n30 != 0 */
            if (n30 != 0){ fm1[l1] &= ~b; nm1[l1] |= b; bubble_chunk(c); }
        } else {
            int old_full = (old == FULL), new_full = (n30 == FULL);
            int old_zero = (old == 0), new_zero = (n30 == 0);
            if (old_full != new_full || old_zero != new_zero){
                int base = c << 4;
                uint32_t all_full = 1, any_nz = 0;
                for (int i = 0; i < 16; i++){
                    uint32_t w = limb[base + i];
                    if (w != FULL) all_full = 0;
                    if (w != 0) any_nz = 1;
                }
                if (all_full) fm1[l1] |= b; else fm1[l1] &= ~b;
                if (any_nz) nm1[l1] |= b; else nm1[l1] &= ~b;
                bubble_chunk(c);
            }
        }
    }
    return carry;
}

static inline int point_sub(int q, uint32_t v){
    int c = q >> 4;
    materialize_chunk(c);
    uint64_t b = 1ull << (c & 63);
    int l1 = c >> 6;
    int was_full = (fm1[l1] & b) != 0;
    int was_zero = (nm1[l1] & b) == 0;
    uint32_t old;
    if (was_full) old = FULL;
    else if (was_zero) old = 0;
    else old = limb[q];
    int32_t nv = (int32_t)old - (int32_t)v;
    int borrow = nv < 0;
    uint32_t res = borrow ? (uint32_t)(nv + (1<<30)) : (uint32_t)nv;
    limb[q] = res;
    if (res != old){
        if (was_full){
            /* 15 full + res -> all-full only if res == FULL */
            if (res == FULL){ /* unchanged */ }
            else { fm1[l1] &= ~b; nm1[l1] |= b; bubble_chunk(c); }
        } else if (was_zero){
            /* 15 zero + res -> mixed if res != 0 */
            if (res != 0){ fm1[l1] &= ~b; nm1[l1] |= b; bubble_chunk(c); }
        } else {
            int old_full = (old == FULL), new_full = (res == FULL);
            int old_zero = (old == 0), new_zero = (res == 0);
            if (old_full != new_full || old_zero != new_zero){
                int base = c << 4;
                uint32_t all_full = 1, any_nz = 0;
                for (int i = 0; i < 16; i++){
                    uint32_t w = limb[base + i];
                    if (w != FULL) all_full = 0;
                    if (w != 0) any_nz = 1;
                }
                if (all_full) fm1[l1] |= b; else fm1[l1] &= ~b;
                if (any_nz) nm1[l1] |= b; else nm1[l1] &= ~b;
                bubble_chunk(c);
            }
        }
    }
    return borrow;
}

/* first chunk >= c0 that is not all-full */
static inline int find_nonfull_chunk(int c0){
    int l1 = c0 >> 6, off = c0 & 63;
    materialize_chunk(c0);
    uint64_t m1 = ~fm1[l1] >> off;
    if (m1) return (l1 << 6) + off + ctz(m1);
    int sh2 = (l1 & 63) + 1;
    uint64_t m2 = (sh2 == 64) ? 0 : (~fm2[l1>>6] >> sh2);
    if (m2){
        int l1n = ((l1>>6) << 6) + sh2 + ctz(m2);
        uint64_t bb = 1ull << (l1n & 63);
        int l2 = l1n >> 6;
        if (fm2[l2] & bb){ fm1[l1n] = ~0ull; nm1[l1n] = ~0ull; }
        else if (!(nm2[l2] & bb)){ fm1[l1n] = 0; nm1[l1n] = 0; }
        return (l1n << 6) + ctz(~fm1[l1n]);
    }
    int sh3 = ((l1>>6) & 63) + 1;
    uint64_t m3 = (sh3 == 64) ? 0 : ((~fm3 & 0xFFFFull) >> sh3);
    if (m3){
        int l2n = sh3 + ctz(m3);
        uint64_t bb = 1ull << (l2n & 63);
        if (fm3 & bb){ fm2[l2n] = ~0ull; nm2[l2n] = ~0ull; }
        else if (!(nm3 & bb)){ fm2[l2n] = 0; nm2[l2n] = 0; }
        int r2 = ctz(~fm2[l2n]);
        int l1n = (l2n << 6) + r2;
        uint64_t b1 = 1ull << (l1n & 63);
        if (fm2[l2n] & b1){ fm1[l1n] = ~0ull; nm1[l1n] = ~0ull; }
        else if (!(nm2[l2n] & b1)){ fm1[l1n] = 0; nm1[l1n] = 0; }
        return (l1n << 6) + ctz(~fm1[l1n]);
    }
    return NC;
}

/* first chunk >= c0 that is not all-zero */
static inline int find_nonzero_chunk(int c0){
    int l1 = c0 >> 6, off = c0 & 63;
    materialize_chunk(c0);
    uint64_t m1 = nm1[l1] >> off;
    if (m1) return (l1 << 6) + off + ctz(m1);
    int sh2 = (l1 & 63) + 1;
    uint64_t m2 = (sh2 == 64) ? 0 : (nm2[l1>>6] >> sh2);
    if (m2){
        int l1n = ((l1>>6) << 6) + sh2 + ctz(m2);
        uint64_t bb = 1ull << (l1n & 63);
        int l2 = l1n >> 6;
        if (fm2[l2] & bb){ fm1[l1n] = ~0ull; nm1[l1n] = ~0ull; }
        else if (!(nm2[l2] & bb)){ fm1[l1n] = 0; nm1[l1n] = 0; }
        return (l1n << 6) + ctz(nm1[l1n]);
    }
    int sh3 = ((l1>>6) & 63) + 1;
    uint64_t m3 = (sh3 == 64) ? 0 : (nm3 >> sh3);
    if (m3){
        int l2n = sh3 + ctz(m3);
        uint64_t bb = 1ull << (l2n & 63);
        if (fm3 & bb){ fm2[l2n] = ~0ull; nm2[l2n] = ~0ull; }
        else if (!(nm3 & bb)){ fm2[l2n] = 0; nm2[l2n] = 0; }
        int r2 = ctz(nm2[l2n]);
        int l1n = (l2n << 6) + r2;
        uint64_t b1 = 1ull << (l1n & 63);
        if (fm2[l2n] & b1){ fm1[l1n] = ~0ull; nm1[l1n] = ~0ull; }
        else if (!(nm2[l2n] & b1)){ fm1[l1n] = 0; nm1[l1n] = 0; }
        return (l1n << 6) + ctz(nm1[l1n]);
    }
    return NC;
}

/* first limb >= l that is not full */
static inline int find_nonfull(int l){
    int c0 = l >> 4;
    materialize_chunk(c0);
    int base = c0 << 4;
    for (int i = l & 15; i < 16; i++){
        if (read_actual(base + i) != FULL) return base + i;
    }
    int c = find_nonfull_chunk(c0 + 1);
    if (c == NC) return NL;
    base = c << 4;
    for (int i = 0; i < 16; i++){
        if (read_actual(base + i) != FULL) return base + i;
    }
    return NL;
}

/* first limb >= l that is not zero */
static inline int find_nonzero(int l){
    int c0 = l >> 4;
    materialize_chunk(c0);
    int base = c0 << 4;
    for (int i = l & 15; i < 16; i++){
        if (read_actual(base + i) != 0) return base + i;
    }
    int c = find_nonzero_chunk(c0 + 1);
    if (c == NC) return NL;
    base = c << 4;
    for (int i = 0; i < 16; i++){
        if (read_actual(base + i) != 0) return base + i;
    }
    return NL;
}

/* bubble L1 word (index l1) up to fm3 */
static inline void bubble_l1word(int l1){
    uint64_t b = 1ull << (l1 & 63);
    int l2 = l1 >> 6;
    if (fm2[l2] == ~0ull) fm3 |= (1ull << (l2 & 63)); else fm3 &= ~(1ull << (l2 & 63));
    if (nm2[l2] != 0) nm3 |= (1ull << (l2 & 63)); else nm3 &= ~(1ull << (l2 & 63));
}

/* zero chunks [ca, cb] (inclusive, all full) lazily */
static inline void zero_chunks(int ca, int cb){
    while (ca <= cb && (ca & 63) != 0){
        int l1 = ca >> 6; uint64_t b = 1ull << (ca & 63);
        fm1[l1] &= ~b; nm1[l1] &= ~b; bubble_chunk(ca); ca++;
    }
    while (ca <= cb && (cb & 63) != 63){
        int l1 = cb >> 6; uint64_t b = 1ull << (cb & 63);
        fm1[l1] &= ~b; nm1[l1] &= ~b; bubble_chunk(cb); cb--;
    }
    if (ca > cb) return;
    int l1a = ca >> 6, l1b = cb >> 6;
    while (l1a <= l1b && (l1a & 63) != 0){
        uint64_t b = 1ull << (l1a & 63);
        int l2 = l1a >> 6;
        fm2[l2] &= ~b; nm2[l2] &= ~b; bubble_l1word(l1a); l1a++;
    }
    while (l1a <= l1b && (l1b & 63) != 63){
        uint64_t b = 1ull << (l1b & 63);
        int l2 = l1b >> 6;
        fm2[l2] &= ~b; nm2[l2] &= ~b; bubble_l1word(l1b); l1b--;
    }
    if (l1a > l1b) return;
    int l2a = l1a >> 6, l2b = l1b >> 6;
    for (int l2 = l2a; l2 <= l2b; l2++){
        fm2[l2] = 0; nm2[l2] = 0;
        uint64_t b2 = 1ull << (l2 & 63);
        fm3 &= ~b2; nm3 &= ~b2;
    }
}

/* full chunks [ca, cb] (inclusive, all zero) lazily */
static inline void full_chunks(int ca, int cb){
    while (ca <= cb && (ca & 63) != 0){
        int l1 = ca >> 6; uint64_t b = 1ull << (ca & 63);
        fm1[l1] |= b; nm1[l1] |= b; bubble_chunk(ca); ca++;
    }
    while (ca <= cb && (cb & 63) != 63){
        int l1 = cb >> 6; uint64_t b = 1ull << (cb & 63);
        fm1[l1] |= b; nm1[l1] |= b; bubble_chunk(cb); cb--;
    }
    if (ca > cb) return;
    int l1a = ca >> 6, l1b = cb >> 6;
    while (l1a <= l1b && (l1a & 63) != 0){
        uint64_t b = 1ull << (l1a & 63);
        int l2 = l1a >> 6;
        fm2[l2] |= b; nm2[l2] |= b; bubble_l1word(l1a); l1a++;
    }
    while (l1a <= l1b && (l1b & 63) != 63){
        uint64_t b = 1ull << (l1b & 63);
        int l2 = l1b >> 6;
        fm2[l2] |= b; nm2[l2] |= b; bubble_l1word(l1b); l1b--;
    }
    if (l1a > l1b) return;
    int l2a = l1a >> 6, l2b = l1b >> 6;
    for (int l2 = l2a; l2 <= l2b; l2++){
        fm2[l2] = ~0ull; nm2[l2] = ~0ull;
        uint64_t b2 = 1ull << (l2 & 63);
        fm3 |= b2; nm3 |= b2;
    }
}

static inline void zero_range(int l, int r){
    /* [l, r) all full -> zero */
    int ca = l >> 4, cb = (r - 1) >> 4;
    if (ca == cb){
        materialize_chunk(ca);
        int base = ca << 4;
        for (int i = l & 15; i <= ((r - 1) & 15); i++) limb[base + i] = 0;
        recompute_chunk(ca);
        return;
    }
    /* first chunk */
    materialize_chunk(ca);
    int base = ca << 4;
    for (int i = l & 15; i < 16; i++) limb[base + i] = 0;
    recompute_chunk(ca);
    /* last chunk */
    materialize_chunk(cb);
    base = cb << 4;
    for (int i = 0; i <= ((r - 1) & 15); i++) limb[base + i] = 0;
    recompute_chunk(cb);
    /* middle chunks (all full -> lazy zero) */
    if (ca + 1 <= cb - 1) zero_chunks(ca + 1, cb - 1);
}

static inline void full_range(int l, int r){
    int ca = l >> 4, cb = (r - 1) >> 4;
    if (ca == cb){
        materialize_chunk(ca);
        int base = ca << 4;
        for (int i = l & 15; i <= ((r - 1) & 15); i++) limb[base + i] = FULL;
        recompute_chunk(ca);
        return;
    }
    materialize_chunk(ca);
    int base = ca << 4;
    for (int i = l & 15; i < 16; i++) limb[base + i] = FULL;
    recompute_chunk(ca);
    materialize_chunk(cb);
    base = cb << 4;
    for (int i = 0; i <= ((r - 1) & 15); i++) limb[base + i] = FULL;
    recompute_chunk(cb);
    if (ca + 1 <= cb - 1) full_chunks(ca + 1, cb - 1);
}

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 = find_nonfull(start);
        if (p > start) zero_range(start, p);
        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 = find_nonzero(start);
        if (p > start) full_range(start, p);
        point_sub(p, 1);
    }
}

/* ---- 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_actual(q);
            out[O++] = (char)('0' + ((v >> r) & 1));
            out[O++] = '\n';
        }
    }
    done(O, di, out, use_di);
}

评测结果