代码

// This code is AI-generated. (AI 生成的代码)
// NOI2017 整数.  Keep the huge integer as signed base-2^32 limbs.  A three-level
// hierarchy of 64-bit "limb is nonzero" masks lets us find the previous nonzero
// limb in O(1) so querying a bit only needs the borrow from that limb.
#include <sys/auxv.h>
#include <stdint.h>
#include <stdlib.h>
#include <string.h>
#include <stdio.h>

typedef long long i64;
typedef unsigned long long u64;

enum { D = 1000000 };
enum { 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 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 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 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 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 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 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 inline unsigned query(unsigned k) {
    int p = k >> 5;
    int q = previous_nonzero(p - 1);
    u64 borrow = q >= 0 && digit[q] < 0;
    unsigned word = (unsigned)(digit[p] - (i64)borrow);
    return (word >> (k & 31)) & 1;
}

struct DuckInfo {
    u64 abi; const char *stdin_ptr; u64 stdin_size;
    char *stdout_ptr; u64 stdout_limit; u64 stdout_size;
    char *stderr_ptr; u64 stderr_limit; u64 stderr_size;
    const char *IB_ptr; u64 IB_limit;
    char *OB_ptr; u64 OB_limit; u64 tsc;
} __attribute__((packed));

static inline u64 rd(const char **pp) {
    const char *p = *pp;
    while ((unsigned char)(*p - '0') > 9) ++p;
    u64 v = 0;
    do { v = v * 10 + (u64)(*p - '0'); ++p; } while ((unsigned char)(*p - '0') <= 9);
    *pp = p;
    return v;
}
static inline i64 rdi(const char **pp) {
    const char *p = *pp;
    while (*p != '-' && (unsigned char)(*p - '0') > 9) ++p;
    int neg = *p == '-';
    p += neg;
    u64 v = 0;
    do { v = v * 10 + (u64)(*p - '0'); ++p; } while ((unsigned char)(*p - '0') <= 9);
    *pp = p;
    return neg ? -(i64)v : (i64)v;
}

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

#ifdef LOCAL
int main(void) {
    static char in[1 << 25], out[1 << 25];
    struct DuckInfo info;
    memset(&info, 0, sizeof(info));
    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);
    return 0;
}
#else
int main(void) { return 0; }

__attribute__((noreturn))
void __libc_start_main(int (*mf)(int, char **, char **), int ac, char **av) {
    (void)mf;
    struct DuckInfo *info = (struct DuckInfo *)((u64 *)av)[29];
    solve(info);
    __asm__ volatile("mov $60, %%eax; xor %%edi, %%edi; syscall" ::: "rax", "rdi", "memory");
    __builtin_unreachable();
}
#endif

评测结果