代码

#ifndef DUCK_FASTIO_H
#define DUCK_FASTIO_H

typedef unsigned long duck_u64;
typedef long duck_i64;

typedef struct {
    duck_u64 abi_version;
    const char *stdin_ptr;
    duck_u64 stdin_size;
    char *stdout_ptr;
    duck_u64 stdout_limit;
    duck_u64 stdout_size;
    char *stderr_ptr;
    duck_u64 stderr_limit;
    duck_u64 stderr_size;
    const char *ib_ptr;
    duck_u64 ib_limit;
    char *ob_ptr;
    duck_u64 ob_limit;
    duck_u64 tsc_frequency;
} __attribute__((packed)) DuckInfo;

static __attribute__((always_inline)) inline DuckInfo *duck_info(long argc, char **argv) {
    char **p = argv + argc + 1;
    while (*p) ++p;
    duck_u64 *aux = (duck_u64 *)(p + 1);
    while (aux[0]) {
        if (aux[0] == 0x6b637564UL) return (DuckInfo *)aux[1];
        aux += 2;
    }
    return (DuckInfo *)0;
}

static __attribute__((always_inline)) inline duck_u64 duck_read_u64(const char **cursor) {
    const char *p = *cursor;
    while ((unsigned char)(*p - '0') > 9) ++p;
    duck_u64 value = 0;
    do {
        value = value * 10 + (unsigned char)(*p - '0');
        ++p;
    } while ((unsigned char)(*p - '0') <= 9);
    *cursor = p;
    return value;
}

static __attribute__((always_inline)) inline duck_i64 duck_read_i64(const char **cursor) {
    const char *p = *cursor;
    while (*p != '-' && (unsigned char)(*p - '0') > 9) ++p;
    int negative = *p == '-';
    p += negative;
    duck_u64 value = 0;
    do {
        value = value * 10 + (unsigned char)(*p - '0');
        ++p;
    } while ((unsigned char)(*p - '0') <= 9);
    *cursor = p;
    return negative ? -(duck_i64)value : (duck_i64)value;
}

static __attribute__((always_inline)) inline char *duck_write_u64(char *out, duck_u64 value) {
    char tmp[24];
    unsigned n = 0;
    do {
        tmp[n++] = (char)('0' + value % 10);
        value /= 10;
    } while (value);
    do *out++ = tmp[--n]; while (n);
    return out;
}

static __attribute__((always_inline)) inline char *duck_write_i64(char *out, duck_i64 value) {
    if (value < 0) {
        *out++ = '-';
        return duck_write_u64(out, (duck_u64)(-value));
    }
    return duck_write_u64(out, (duck_u64)value);
}

static __attribute__((always_inline, noreturn)) inline void duck_exit(void) {
    __asm__ volatile("mov $60,%%eax;xor %%edi,%%edi;syscall" ::: "rax", "rdi", "rcx", "r11", "memory");
    __builtin_unreachable();
}

#endif


typedef unsigned long u64;
typedef long i64;
enum { WORDS = 1 << 19 };
static u64 word[WORDS];
/* 0 = uniformly zero, 1 = uniformly all-one, 2 = mixed/nonuniform. */
static unsigned char state[WORDS << 1];

static __attribute__((always_inline)) inline void push(int node) {
    unsigned s = state[node];
    if (s < 2) {
        state[node + node] = state[node + node + 1] = (unsigned char)s;
        state[node] = 2;
    }
}
static __attribute__((always_inline)) inline void pull(int node) {
    unsigned a = state[node + node], b = state[node + node + 1];
    state[node] = (unsigned char)(a == b && a < 2 ? a : 2);
}

static __attribute__((noinline)) int add_one(int node, int left, int right) {
    unsigned s = state[node];
    if (s == 1) { state[node] = 0; return 1; }
    if (right - left == 1) {
        u64 x = s == 0 ? 0 : word[left];
        ++x; word[left] = x; state[node] = (unsigned char)(x == ~(u64)0 ? 1 : 2);
        return 0;
    }
    push(node);
    int mid = (left + right) >> 1;
    int carry = add_one(node + node, left, mid);
    if (carry) carry = add_one(node + node + 1, mid, right);
    pull(node); return carry;
}

static __attribute__((noinline)) int sub_one(int node, int left, int right) {
    unsigned s = state[node];
    if (s == 0) { state[node] = 1; return 1; }
    if (right - left == 1) {
        u64 x = s == 1 ? ~(u64)0 : word[left];
        --x; word[left] = x; state[node] = (unsigned char)(x == 0 ? 0 : 2);
        return 0;
    }
    push(node);
    int mid = (left + right) >> 1;
    int borrow = sub_one(node + node, left, mid);
    if (borrow) borrow = sub_one(node + node + 1, mid, right);
    pull(node); return borrow;
}

static __attribute__((noinline)) int add_at(int node, int left, int right,
                                            int pos, u64 amount) {
    if (right - left == 1) {
        unsigned s = state[node]; u64 old = s == 0 ? 0 : s == 1 ? ~(u64)0 : word[left];
        u64 x = old + amount; word[left] = x;
        state[node] = (unsigned char)(x == 0 ? 0 : x == ~(u64)0 ? 1 : 2);
        return x < old;
    }
    push(node); int mid = (left + right) >> 1, carry;
    if (pos < mid) {
        carry = add_at(node + node, left, mid, pos, amount);
        if (carry) carry = add_one(node + node + 1, mid, right);
    } else carry = add_at(node + node + 1, mid, right, pos, amount);
    pull(node); return carry;
}

static __attribute__((noinline)) int sub_at(int node, int left, int right,
                                            int pos, u64 amount) {
    if (right - left == 1) {
        unsigned s = state[node]; u64 old = s == 0 ? 0 : s == 1 ? ~(u64)0 : word[left];
        u64 x = old - amount; word[left] = x;
        state[node] = (unsigned char)(x == 0 ? 0 : x == ~(u64)0 ? 1 : 2);
        return old < amount;
    }
    push(node); int mid = (left + right) >> 1, borrow;
    if (pos < mid) {
        borrow = sub_at(node + node, left, mid, pos, amount);
        if (borrow) borrow = sub_one(node + node + 1, mid, right);
    } else borrow = sub_at(node + node + 1, mid, right, pos, amount);
    pull(node); return borrow;
}

static __attribute__((always_inline)) inline void add_shifted(i64 signed_value, int bit) {
    u64 magnitude = signed_value < 0 ? (u64)(-signed_value) : (u64)signed_value;
    int pos = bit >> 6; unsigned shift = (unsigned)bit & 63;
    u64 low = magnitude << shift, high = shift ? magnitude >> (64 - shift) : 0;
    if (signed_value > 0) {
        if (low) add_at(1, 0, WORDS, pos, low);
        if (high) add_at(1, 0, WORDS, pos + 1, high);
    } else if (signed_value < 0) {
        if (low) sub_at(1, 0, WORDS, pos, low);
        if (high) sub_at(1, 0, WORDS, pos + 1, high);
    }
}

static __attribute__((noinline)) u64 get_word(int node, int left, int right, int pos) {
    unsigned s = state[node]; if (s < 2) return s ? ~(u64)0 : 0;
    if (right - left == 1) return word[left];
    int mid = (left + right) >> 1;
    return pos < mid ? get_word(node + node, left, mid, pos)
                     : get_word(node + node + 1, mid, right, pos);
}

static void solve(DuckInfo *info) {
    const char *in = info->stdin_ptr; int n = (int)duck_read_u64(&in);
    (void)duck_read_u64(&in); (void)duck_read_u64(&in); (void)duck_read_u64(&in);
    char *out = info->stdout_ptr;
    for (int i = 0; i < n; ++i) {
        unsigned op = (unsigned)duck_read_u64(&in);
        if (op == 1) { i64 x=duck_read_i64(&in); int b=(int)duck_read_u64(&in); add_shifted(x,b); }
        else { int b=(int)duck_read_u64(&in); u64 x=get_word(1,0,WORDS,b>>6);
            *out++=(char)('0'+((x>>(b&63))&1)); *out++='\n'; }
    }
    info->stdout_size=(u64)(out-info->stdout_ptr);
}

#ifdef LOCAL
#include <stdio.h>
int main(void){static char input[20000000],output[2000000];DuckInfo info={0};
 info.stdin_size=fread(input,1,sizeof input,stdin);info.stdin_ptr=input;info.stdout_ptr=output;
 solve(&info);fwrite(output,1,info.stdout_size,stdout);return 0;}
#else
__attribute__((noreturn)) void __libc_start_main(void*u,long argc,char**argv){(void)u;DuckInfo*i=duck_info(argc,argv);solve(i);duck_exit();}
int main(void){}
#endif

评测结果