代码

#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

#if defined(LOCAL) || defined(DEBUG)
#include <stdio.h>
#endif

typedef unsigned long u64;
typedef long i64;

enum {
    LIMB_BITS = 60,
    BLOCK_SHIFT = 8,
    BLOCK_SIZE = 1 << BLOCK_SHIFT,
    MAX_BLOCKS = (30000050 / (LIMB_BITS * BLOCK_SIZE)) + 2,
    MAX_LIMBS = MAX_BLOCKS * BLOCK_SIZE
};

static const u64 LIMB_MASK = (1UL << LIMB_BITS) - 1;
static u64 limb[MAX_LIMBS];
/* 1 = implicit zero block, 2 = implicit all-one block, 3 = materialized. */
static unsigned char block_state[MAX_BLOCKS];
static int limb_count;

static __attribute__((always_inline)) inline unsigned classify_limb(u64 value) {
    return value == 0 ? 1u : value == LIMB_MASK ? 2u : 3u;
}

static __attribute__((always_inline)) inline void materialize(int pos) {
    int b = pos >> BLOCK_SHIFT;
    unsigned state = block_state[b];
    if (state == 3) return;
    u64 value = state == 1 ? 0 : LIMB_MASK;
    int end = (b + 1) << BLOCK_SHIFT;
    for (int i = b << BLOCK_SHIFT; i < end; ++i) limb[i] = value;
    block_state[b] = 3;
}

static __attribute__((noinline)) void carry_positive(int pos, u64 carry) {
    while (carry) {
        int b = pos >> BLOCK_SHIFT;
        if (pos == (b << BLOCK_SHIFT) && block_state[b] == 2 && carry == 1) {
            block_state[b] = 1;
            pos += BLOCK_SIZE;
            continue;
        }
        materialize(pos);
        int start = pos;
        int end = ((b + 1) << BLOCK_SHIFT) - 1;
        if (end >= limb_count) end = limb_count - 1;
        unsigned traversed = 0;
        limb[pos] += carry;
        while (pos < end && limb[pos] > LIMB_MASK) {
            limb[pos + 1] += limb[pos] >> LIMB_BITS;
            limb[pos] &= LIMB_MASK;
            traversed |= classify_limb(limb[pos]);
            ++pos;
        }
        if (pos == end) {
            carry = limb[pos] >> LIMB_BITS;
            limb[pos] &= LIMB_MASK;
            unsigned state = traversed;
            for (int i = b << BLOCK_SHIFT; i < start && state != 3; ++i)
                state |= classify_limb(limb[i]);
            state |= classify_limb(limb[pos]);
            block_state[b] = (unsigned char)state;
            pos = end + 1;
        } else {
            break;
        }
    }
}

static __attribute__((noinline)) void carry_negative(int pos, u64 borrow) {
    while (borrow) {
        int b = pos >> BLOCK_SHIFT;
        if (pos == (b << BLOCK_SHIFT) && block_state[b] == 1 && borrow == 1) {
            block_state[b] = 2;
            pos += BLOCK_SIZE;
            continue;
        }
        materialize(pos);
        int start = pos;
        int end = ((b + 1) << BLOCK_SHIFT) - 1;
        if (end >= limb_count) end = limb_count - 1;
        unsigned traversed = 0;
        u64 old = limb[pos];
        limb[pos] = (old - borrow) & LIMB_MASK;
        borrow = old < borrow;
        while (borrow && pos < end) {
            traversed |= classify_limb(limb[pos]);
            ++pos;
            old = limb[pos];
            limb[pos] = (old - 1) & LIMB_MASK;
            borrow = old == 0;
        }
        if (pos == end) {
            unsigned state = traversed;
            for (int i = b << BLOCK_SHIFT; i < start && state != 3; ++i)
                state |= classify_limb(limb[i]);
            state |= classify_limb(limb[pos]);
            block_state[b] = (unsigned char)state;
            pos = end + 1;
        } else {
            break;
        }
    }
}

static __attribute__((always_inline)) inline void add_shifted(i64 value, int bit) {
    if (!value) return;
    u64 magnitude = value < 0 ? (u64)(-value) : (u64)value;
    int pos = bit / LIMB_BITS;
    unsigned shift = (unsigned)(bit % LIMB_BITS);
    unsigned room = LIMB_BITS - shift;
    u64 low = (magnitude & ((1UL << room) - 1)) << shift;
    u64 high = magnitude >> room;
    materialize(pos);
    if (value > 0) {
        limb[pos] += low;
        high += limb[pos] >> LIMB_BITS;
        limb[pos] &= LIMB_MASK;
        carry_positive(pos + 1, high);
    } else {
        u64 old = limb[pos];
        limb[pos] = (old - low) & LIMB_MASK;
        high += old < low;
        carry_negative(pos + 1, high);
    }
}

static void solve(DuckInfo *info) {
    const char *in = info->stdin_ptr;
    int operations = (int)duck_read_u64(&in);
    (void)duck_read_u64(&in);
    int t2 = (int)duck_read_u64(&in);
    (void)duck_read_u64(&in);
    int bits = t2 == 1 ? 30 : t2 == 2 ? 100 : t2 == 3 ? operations : 30 * operations;
    int blocks = (bits + 50) / (LIMB_BITS * BLOCK_SIZE) + 1;
    limb_count = blocks * BLOCK_SIZE;
    for (int i = 0; i < blocks; ++i) block_state[i] = 1;

    char *out = info->stdout_ptr;
    for (int q = 0; q < operations; ++q) {
        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);
            int pos = bit / LIMB_BITS;
            unsigned state = block_state[pos >> BLOCK_SHIFT];
            unsigned answer = state == 3 ? (unsigned)((limb[pos] >> (bit % LIMB_BITS)) & 1) : state - 1;
#ifdef DEBUG
            if (q > 992970 && q < 992990) fprintf(stderr, "qop=%d bit=%d pos=%d block=%d state=%u limb=%lx ans=%u\n", q, bit, pos, pos >> BLOCK_SHIFT, state, limb[pos], answer);
#endif
            *out++ = (char)('0' + answer);
            *out++ = '\n';
        }
    }
    info->stdout_size = (u64)(out - info->stdout_ptr);
}

#ifdef LOCAL
int main(void) {
    static char input[20000000], output[2000000];
    DuckInfo info = {0};
    info.stdin_ptr = input;
    info.stdin_size = fread(input, 1, sizeof input, stdin);
    info.stdout_ptr = output;
    info.stdout_limit = sizeof 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

评测结果