代码

#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<<19)     /* 524288 limbs of 64 bits = 33.5M bits >= 30n=30M */
#define N1 (NL>>6)     /* 8192 */
#define N2 (N1>>6)     /* 128 */
#define N3 (N2>>6)     /* 2 */

static uint64_t limb[NL];
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 const char *P;
static uint64_t O;
static int has_lazy;

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

static inline __attribute__((always_inline)) void bubble_l3(int l3){
    uint64_t b = 1ull << l3;
    if (fm3[l3] == ~0ull) fm4 |= b; else fm4 &= ~b;
    if (nm3[l3] != 0) nm4 |= b; else nm4 &= ~b;
}

static inline __attribute__((always_inline)) void bubble_l2(int l2){
    uint64_t b = 1ull << (l2 & 63);
    int l3 = l2 >> 6;
    if (fm2[l2] == ~0ull) fm3[l3] |= b; else fm3[l3] &= ~b;
    if (nm2[l2] != 0) nm3[l3] |= b; else nm3[l3] &= ~b;
    bubble_l3(l3);
}

static inline __attribute__((always_inline)) void bubble_l1(int l1){
    uint64_t b = 1ull << (l1 & 63);
    int l2 = l1 >> 6;
    if (fm1[l1] == ~0ull) fm2[l2] |= b; else fm2[l2] &= ~b;
    if (nm1[l1] != 0) nm2[l2] |= b; else nm2[l2] &= ~b;
    bubble_l2(l2);
}

static inline __attribute__((always_inline)) void materialize_word(int l1){
    int l2 = l1 >> 6, l3 = l2 >> 6;
    uint64_t b3 = 1ull << l3;
    if (fm4 & b3){ fm3[l3] = ~0ull; nm3[l3] = ~0ull; }
    else if (!(nm4 & b3)){ fm3[l3] = 0; nm3[l3] = 0; }
    uint64_t b2 = 1ull << (l2 & 63);
    if (fm3[l3] & b2){ fm2[l2] = ~0ull; nm2[l2] = ~0ull; }
    else if (!(nm3[l3] & 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; }
}

static inline __attribute__((always_inline)) int point_add(int pos, uint64_t v){
    int l1 = pos >> 6;
    uint64_t b = 1ull << (pos & 63);
    uint64_t old_fm, old_nm;
    if (has_lazy) materialize_word(l1);
    old_fm = fm1[l1]; old_nm = nm1[l1];
    uint64_t old;
    if (old_fm & b) old = ~0ull;
    else if (!(old_nm & b)) old = 0;
    else old = limb[pos];
    uint64_t nv = old + v;
    int ovf = nv < old;
    limb[pos] = nv;
    if (nv == ~0ull) fm1[l1] |= b; else fm1[l1] &= ~b;
    if (nv != 0) nm1[l1] |= b; else nm1[l1] &= ~b;
    if ((old_fm == ~0ull) != (fm1[l1] == ~0ull) || (old_nm == 0) != (nm1[l1] == 0))
        bubble_l1(l1);
    return ovf;
}

static inline __attribute__((always_inline)) int point_sub(int pos, uint64_t v){
    int l1 = pos >> 6;
    uint64_t b = 1ull << (pos & 63);
    uint64_t old_fm, old_nm;
    if (has_lazy) materialize_word(l1);
    old_fm = fm1[l1]; old_nm = nm1[l1];
    uint64_t old;
    if (old_fm & b) old = ~0ull;
    else if (!(old_nm & b)) old = 0;
    else old = limb[pos];
    int borrow = old < v;
    uint64_t res = old - v;
    limb[pos] = res;
    if (res == ~0ull) fm1[l1] |= b; else fm1[l1] &= ~b;
    if (res != 0) nm1[l1] |= b; else nm1[l1] &= ~b;
    if ((old_fm == ~0ull) != (fm1[l1] == ~0ull) || (old_nm == 0) != (nm1[l1] == 0))
        bubble_l1(l1);
    return borrow;
}

static inline __attribute__((always_inline)) int find_nonfull(int p){
    int l1 = p >> 6, l2 = p >> 12, l3 = p >> 18, off = p & 63;
    if (has_lazy) materialize_word(l1);
    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[l2] >> sh2);
    if (m2){
        int l1n = (l2 << 6) + sh2 + ctz(m2);
        uint64_t b = 1ull << (l1n & 63);
        if (fm2[l2] & b){ fm1[l1n] = ~0ull; nm1[l1n] = ~0ull; }
        else if (!(nm2[l2] & b)){ fm1[l1n] = 0; nm1[l1n] = 0; }
        return (l1n << 6) + ctz(~fm1[l1n]);
    }
    int sh3 = (l2 & 63) + 1;
    uint64_t m3 = (sh3 == 64) ? 0 : (~fm3[l3] >> sh3);
    if (m3){
        int l2n = (l3 << 6) + sh3 + ctz(m3);
        uint64_t b2 = 1ull << (l2n & 63);
        if (fm3[l3] & b2){ fm2[l2n] = ~0ull; nm2[l2n] = ~0ull; }
        else if (!(nm3[l3] & b2)){ 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]);
    }
    uint64_t m4 = ~fm4 >> (l3 + 1);
    if (m4){
        int l3n = l3 + 1 + ctz(m4);
        uint64_t b3 = 1ull << l3n;
        if (fm4 & b3){ fm3[l3n] = ~0ull; nm3[l3n] = ~0ull; }
        else if (!(nm4 & b3)){ fm3[l3n] = 0; nm3[l3n] = 0; }
        int r3 = ctz(~fm3[l3n]);
        int l2n = (l3n << 6) + r3;
        uint64_t b2 = 1ull << (l2n & 63);
        if (fm3[l3n] & b2){ fm2[l2n] = ~0ull; nm2[l2n] = ~0ull; }
        else if (!(nm3[l3n] & b2)){ 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 NL;
}

static inline __attribute__((always_inline)) int find_nonzero(int p){
    int l1 = p >> 6, l2 = p >> 12, l3 = p >> 18, off = p & 63;
    if (has_lazy) materialize_word(l1);
    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[l2] >> sh2);
    if (m2){
        int l1n = (l2 << 6) + sh2 + ctz(m2);
        uint64_t b = 1ull << (l1n & 63);
        if (fm2[l2] & b){ fm1[l1n] = ~0ull; nm1[l1n] = ~0ull; }
        else if (!(nm2[l2] & b)){ fm1[l1n] = 0; nm1[l1n] = 0; }
        return (l1n << 6) + ctz(nm1[l1n]);
    }
    int sh3 = (l2 & 63) + 1;
    uint64_t m3 = (sh3 == 64) ? 0 : (nm3[l3] >> sh3);
    if (m3){
        int l2n = (l3 << 6) + sh3 + ctz(m3);
        uint64_t b2 = 1ull << (l2n & 63);
        if (fm3[l3] & b2){ fm2[l2n] = ~0ull; nm2[l2n] = ~0ull; }
        else if (!(nm3[l3] & b2)){ 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]);
    }
    uint64_t m4 = nm4 >> (l3 + 1);
    if (m4){
        int l3n = l3 + 1 + ctz(m4);
        uint64_t b3 = 1ull << l3n;
        if (fm4 & b3){ fm3[l3n] = ~0ull; nm3[l3n] = ~0ull; }
        else if (!(nm4 & b3)){ fm3[l3n] = 0; nm3[l3n] = 0; }
        int r3 = ctz(nm3[l3n]);
        int l2n = (l3n << 6) + r3;
        uint64_t b2 = 1ull << (l2n & 63);
        if (fm3[l3n] & b2){ fm2[l2n] = ~0ull; nm2[l2n] = ~0ull; }
        else if (!(nm3[l3n] & b2)){ 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 NL;
}

static inline __attribute__((always_inline)) void zero_mid(int a, int b){
    while (a <= b && (a & 63) != 0){
        fm1[a] = 0; nm1[a] = 0; bubble_l1(a); a++;
    }
    while (a <= b && (b & 63) != 63){
        fm1[b] = 0; nm1[b] = 0; bubble_l1(b); b--;
    }
    if (a > b) return;
    while (a <= b && (a & 4095) != 0){
        fm2[a >> 6] = 0; nm2[a >> 6] = 0; bubble_l2(a >> 6); a += 64;
    }
    while (a <= b && (b & 4095) != 4095){
        fm2[b >> 6] = 0; nm2[b >> 6] = 0; bubble_l2(b >> 6); b -= 64;
    }
    if (a > b) return;
    for (int l3 = a >> 12; l3 <= (b >> 12); l3++){
        fm3[l3] = 0; nm3[l3] = 0; bubble_l3(l3);
    }
}

static inline __attribute__((always_inline)) void full_mid(int a, int b){
    while (a <= b && (a & 63) != 0){
        fm1[a] = ~0ull; nm1[a] = ~0ull; bubble_l1(a); a++;
    }
    while (a <= b && (b & 63) != 63){
        fm1[b] = ~0ull; nm1[b] = ~0ull; bubble_l1(b); b--;
    }
    if (a > b) return;
    while (a <= b && (a & 4095) != 0){
        fm2[a >> 6] = ~0ull; nm2[a >> 6] = ~0ull; bubble_l2(a >> 6); a += 64;
    }
    while (a <= b && (b & 4095) != 4095){
        fm2[b >> 6] = ~0ull; nm2[b >> 6] = ~0ull; bubble_l2(b >> 6); b -= 64;
    }
    if (a > b) return;
    for (int l3 = a >> 12; l3 <= (b >> 12); l3++){
        fm3[l3] = ~0ull; nm3[l3] = ~0ull; bubble_l3(l3);
    }
}

static inline __attribute__((always_inline)) void zero_range(int l, int r){
    int l1a = l >> 6, l1b = (r - 1) >> 6;
    if (l1a == l1b){
        materialize_word(l1a);
        int lo = l & 63, hi = (r - 1) & 63;
        uint64_t mask = (lo == 0 && hi == 63) ? ~0ull : ((1ull << (hi - lo + 1)) - 1) << lo;
        fm1[l1a] &= ~mask;
        nm1[l1a] &= ~mask;
        bubble_l1(l1a);
        return;
    }
    materialize_word(l1a);
    fm1[l1a] &= ~(~0ull << (l & 63));
    nm1[l1a] &= ~(~0ull << (l & 63));
    bubble_l1(l1a);
    materialize_word(l1b);
    int hi = (r - 1) & 63;
    uint64_t maskb = (hi == 63) ? ~0ull : ((1ull << (hi + 1)) - 1);
    fm1[l1b] &= ~maskb;
    nm1[l1b] &= ~maskb;
    bubble_l1(l1b);
    zero_mid(l1a + 1, l1b - 1);
}

static inline __attribute__((always_inline)) void full_range(int l, int r){
    int l1a = l >> 6, l1b = (r - 1) >> 6;
    if (l1a == l1b){
        materialize_word(l1a);
        int lo = l & 63, hi = (r - 1) & 63;
        uint64_t mask = (lo == 0 && hi == 63) ? ~0ull : ((1ull << (hi - lo + 1)) - 1) << lo;
        fm1[l1a] |= mask;
        nm1[l1a] |= mask;
        bubble_l1(l1a);
        return;
    }
    materialize_word(l1a);
    fm1[l1a] |= ~0ull << (l & 63);
    nm1[l1a] |= ~0ull << (l & 63);
    bubble_l1(l1a);
    materialize_word(l1b);
    int hi = (r - 1) & 63;
    uint64_t maskb = (hi == 63) ? ~0ull : ((1ull << (hi + 1)) - 1);
    fm1[l1b] |= maskb;
    nm1[l1b] |= maskb;
    bubble_l1(l1b);
    full_mid(l1a + 1, l1b - 1);
}

static inline __attribute__((always_inline)) void add_val(int q, int r, uint64_t a){
    uint64_t lo = a << r;
    uint64_t hi = (r == 0) ? 0ull : (a >> (64 - 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); has_lazy = 1; }
        point_add(p, 1);
    }
}

static inline __attribute__((always_inline)) void sub_val(int q, int r, uint64_t a){
    uint64_t lo = a << r;
    uint64_t hi = (r == 0) ? 0ull : (a >> (64 - 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); has_lazy = 1; }
        point_sub(p, 1);
    }
}

static inline __attribute__((always_inline)) uint64_t read_limb(int pos){
    if (!has_lazy) return limb[pos];
    int l1 = pos >> 6, l2 = pos >> 12, l3 = pos >> 18;
    uint64_t b3 = 1ull << l3;
    if (fm4 & b3) return ~0ull;
    if (!(nm4 & b3)) return 0;
    uint64_t b2 = 1ull << (l2 & 63);
    if (fm3[l3] & b2) return ~0ull;
    if (!(nm3[l3] & b2)) return 0;
    uint64_t b1 = 1ull << (l1 & 63);
    if (fm2[l2] & b1) return ~0ull;
    if (!(nm2[l2] & b1)) return 0;
    uint64_t b = 1ull << (pos & 63);
    if (fm1[l1] & b) return ~0ull;
    if (!(nm1[l1] & b)) return 0;
    return limb[pos];
}

/* ---- 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 >> 6;
            int r = b & 63;
            if (neg) (void)0;
            else (void)0;
        } else {
            int k = 0;
            while (*P > ' '){ k = k*10 + (*P - '0'); P++; }
            P++;
            int q = k >> 6;
            int r = k & 63;
            uint64_t v = read_limb(q);
            out[O++] = (char)('0' + ((v >> r) & 1));
            out[O++] = '\n';
        }
    }
    done(O, di, out, use_di);
}

评测结果