代码

#include "../../include/duck_fastio.h"
#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

评测结果