代码

#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, TREE_NODES = WORDS << 1 };
static u64 words[WORDS];
/* 0 = all zero, 1 = all one, 2 = mixed/nonuniform. */
static unsigned char state[TREE_NODES];

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)) 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 words[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 __attribute__((noinline)) void set_word(int node, int left, int right, int pos, u64 value) {
    if (right - left == 1) {
        words[left] = value;
        state[node] = (unsigned char)(value == 0 ? 0 : value == ~(u64)0 ? 1 : 2);
        return;
    }
    push(node);
    int mid = (left + right) >> 1;
    if (pos < mid) set_word(node + node, left, mid, pos, value);
    else set_word(node + node + 1, mid, right, pos, value);
    pull(node);
}

static __attribute__((noinline)) int first_not(int node, int left, int right,
                                                int start, unsigned target) {
    if (right <= start || state[node] == target) return -1;
    if (right - left == 1) return left;
    push(node);
    int mid = (left + right) >> 1;
    int result = first_not(node + node, left, mid, start, target);
    return result >= 0 ? result : first_not(node + node + 1, mid, right, start, target);
}

static __attribute__((noinline)) void assign_range(int node, int left, int right,
                                                    int from, int to, unsigned value) {
    if (from <= left && right <= to) {
        state[node] = (unsigned char)value;
        return;
    }
    push(node);
    int mid = (left + right) >> 1;
    if (from < mid) assign_range(node + node, left, mid, from, to, value);
    if (to > mid) assign_range(node + node + 1, mid, right, from, to, value);
    pull(node);
}

static __attribute__((always_inline)) inline void propagate(int start, unsigned target) {
    int pos = first_not(1, 0, WORDS, start, target);
    if (pos > start) assign_range(1, 0, WORDS, start, pos, target ^ 1);
    u64 value = get_word(1, 0, WORDS, pos);
    set_word(1, 0, WORDS, pos, target ? value + 1 : value - 1);
}

static __attribute__((always_inline)) inline void add_shifted(i64 signed_value, int bit) {
    if (!signed_value) return;
    u64 magnitude = signed_value < 0 ? (u64)(-signed_value) : (u64)signed_value;
    int pos = bit >> 6;
    unsigned shift = (unsigned)bit & 63;
    u64 low = magnitude << shift;
    u64 high = shift ? magnitude >> (64 - shift) : 0;
    u64 old = get_word(1, 0, WORDS, pos);
    if (signed_value > 0) {
        u64 value = old + low;
        u64 carry = value < old;
        set_word(1, 0, WORDS, pos, value);
        old = get_word(1, 0, WORDS, pos + 1);
        value = old + high;
        u64 overflow = value < old;
        old = value;
        value += carry;
        carry = overflow | (value < old);
        set_word(1, 0, WORDS, pos + 1, value);
        if (carry) propagate(pos + 2, 1);
    } else {
        u64 value = old - low;
        u64 borrow = old < low;
        set_word(1, 0, WORDS, pos, value);
        old = get_word(1, 0, WORDS, pos + 1);
        value = old - high;
        u64 underflow = old < high;
        old = value;
        value -= borrow;
        borrow = underflow | (old < borrow);
        set_word(1, 0, WORDS, pos + 1, value);
        if (borrow) propagate(pos + 2, 0);
    }
}

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 value = duck_read_i64(&in);
            int bit = (int)duck_read_u64(&in);
            add_shifted(value, bit);
        } else {
            int bit = (int)duck_read_u64(&in);
            u64 value = get_word(1, 0, WORDS, bit >> 6);
            *out++ = (char)('0' + ((value >> (bit & 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 *unused, long argc, char **argv) {
    (void)unused; DuckInfo *info = duck_info(argc, argv); solve(info); duck_exit();
}
int main(void) {}
#endif

评测结果