代码

#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

#ifdef DEBUG
#include <stdio.h>
#endif

typedef unsigned long u64;
typedef long i64;

enum {
    D = 937510,
    S1 = (D + 63) / 64,
    S2 = (S1 + 63) / 64,
    S3 = (S2 + 63) / 64
};
static i64 digit[D];
static u64 nz[S1], nz2[S2], nz3[S3];

static __attribute__((always_inline)) inline void set_digit(int p, i64 v) {
    int a = p >> 6, b = p & 63;
    u64 bit = 1UL << b;
    int was = digit[p] != 0;
    int now = v != 0;
    digit[p] = v;
    if (was == now) return;
    u64 old1 = nz[a];
    if (now) nz[a] |= bit;
    else nz[a] &= ~bit;
    if ((!old1) == (!nz[a])) return;
    int c = a >> 6, d = a & 63;
    u64 old2 = nz2[c], bit2 = 1UL << d;
    if (nz[a]) nz2[c] |= bit2;
    else nz2[c] &= ~bit2;
    if ((!old2) == (!nz2[c])) return;
    int e = c >> 6, f = c & 63;
    if (nz2[c]) nz3[e] |= 1UL << f;
    else nz3[e] &= ~(1UL << f);
}

static __attribute__((noinline)) void add_unit(int p) {
    const i64 BASE = 1LL << 32;
    for (;;) {
        i64 v = digit[p] + 1;
        if (v != BASE) {
            set_digit(p, v);
            return;
        }
        set_digit(p++, 0);
    }
}

static __attribute__((noinline)) void sub_unit(int p) {
    const i64 BASE = 1LL << 32;
    for (;;) {
        i64 v = digit[p] - 1;
        if (v != -BASE) {
            set_digit(p, v);
            return;
        }
        set_digit(p++, 0);
    }
}

static __attribute__((always_inline)) inline void add_chunk(int p, i64 v) {
    const i64 BASE = 1LL << 32;
    i64 x = digit[p] + v;
    if (x >= BASE) {
        set_digit(p, x - BASE);
        add_unit(p + 1);
    } else if (x <= -BASE) {
        set_digit(p, x + BASE);
        sub_unit(p + 1);
    } else {
        set_digit(p, x);
    }
}

static __attribute__((always_inline)) inline void add_shifted(i64 x, unsigned b) {
    if (!x) return;
    u64 a = x < 0 ? (u64)-x : (u64)x;
    int p = b >> 5;
    unsigned off = b & 31;
    u64 shifted = a << off;
    i64 lo = (unsigned)shifted;
    i64 hi = off ? (i64)(a >> (32 - off)) : 0;
    if (x < 0) lo = -lo, hi = -hi;
    if (lo) add_chunk(p, lo);
    if (hi) add_chunk(p + 1, hi);
}

static __attribute__((always_inline)) inline int previous_nonzero(int p) {
    if (p < 0) return -1;
    int a = p >> 6, b = p & 63;
    u64 x = nz[a] & (~0UL >> (63 - b));
    if (x) return (a << 6) + 63 - __builtin_clzl(x);
    if (--a < 0) return -1;
    int c = a >> 6, d = a & 63;
    x = nz2[c] & (~0UL >> (63 - d));
    if (!x) {
        if (--c < 0) return -1;
        int e = c >> 6, f = c & 63;
        x = nz3[e] & (~0UL >> (63 - f));
        while (!x) {
            if (--e < 0) return -1;
            x = nz3[e];
        }
        c = (e << 6) + 63 - __builtin_clzl(x);
        x = nz2[c];
    }
    a = (c << 6) + 63 - __builtin_clzl(x);
    x = nz[a];
    return (a << 6) + 63 - __builtin_clzl(x);
}

static __attribute__((always_inline)) inline unsigned query(unsigned k) {
    int p = k >> 5;
    int q = previous_nonzero(p - 1);
#ifdef DEBUG
    if (k == 16929043) {
        int slow = p - 1;
        while (slow >= 0 && !digit[slow]) --slow;
        fprintf(stderr, "p=%d fast=%d slow=%d fd=%ld sd=%ld cur=%ld\n",
                p, q, slow, q < 0 ? 0 : digit[q],
                slow < 0 ? 0 : digit[slow], digit[p]);
    }
#endif
    u64 borrow = q >= 0 && digit[q] < 0;
    unsigned word = (unsigned)(digit[p] - (i64)borrow);
    return (word >> (k & 31)) & 1;
}

static void solve(DuckInfo *info) {
    const char *p = info->stdin_ptr;
    unsigned n = duck_read_u64(&p);
    duck_read_u64(&p);
    duck_read_u64(&p);
    duck_read_u64(&p);
    char *out = info->stdout_ptr;
    while (n--) {
        if (duck_read_u64(&p) == 1) {
            i64 a = duck_read_i64(&p);
            unsigned b = duck_read_u64(&p);
            add_shifted(a, b);
        } else {
            *out++ = '0' + query(duck_read_u64(&p));
            *out++ = '\n';
        }
    }
    info->stdout_size = out - info->stdout_ptr;
}

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

评测结果