代码

// noi17a 【NOI2017】整数
// x += a*2^b  (|a| <= 1e9, b <= 30n), query bit k of x.
// Representation: bit array over words + 2-level summary for "next zero / next one".
// Decompose a into its set bits and do single-bit add/sub with amortised carry runs.
#include <cstdio>
#include <cstring>
#include <cstdlib>

typedef unsigned long long u64;

#ifdef TEST_IO
static char *IN; static u64 INSZ; static char *OUT; static u64 OUTSZ = 0; static u64 OUTLIM = 1u<<28;
#else
struct DI { u64 abi; const char*in; u64 insz; char*out; u64 outlim; u64 outsz; char*err;
            u64 errlim; u64 errsz; const char*IB; u64 IBlim; char*OB; u64 OBlim; u64 tscfreq; }
            __attribute__((packed));
#define DUCKINFO 0x243FFF90ULL
static struct DI *di;
static const char *IN; static u64 INSZ; static char *OUT; static u64 OUTSZ = 0; static u64 OUTLIM;
#endif

static const int NW = 468800;      // 64-bit words = 30e6 bits + slack (multiple of 64)
static const int NG = 7325;        // groups of 64 words
static const int NG3 = 115;        // groups of 64 groups

static u64 wds[NW];
static u64 gz[NG], go[NG];
static u64 gz3[NG3], go3[NG3];

static inline void updWord(u64 i) {
    u64 w = wds[i];
    u64 g = i >> 6; unsigned t = (unsigned)(i & 63);
    u64 bit = 1ULL << t;
    if (w) go[g] |= bit; else go[g] &= ~bit;
    if (w != ~0ULL) gz[g] |= bit; else gz[g] &= ~bit;
    u64 b = g >> 6; unsigned u = (unsigned)(g & 63);
    u64 bit2 = 1ULL << u;
    if (go[g]) go3[b] |= bit2; else go3[b] &= ~bit2;
    if (gz[g]) gz3[b] |= bit2; else gz3[b] &= ~bit2;
}

static inline int getBit(u64 p) { return (int)((wds[p >> 6] >> (p & 63)) & 1ULL); }

static inline void setBit(u64 p, int v) {
    u64 i = p >> 6;
    u64 m = 1ULL << (p & 63);
    if (v) wds[i] |= m; else wds[i] &= ~m;
    updWord(i);
}

static inline void setRange(u64 p, u64 q, int v) {   // [p,q)
    if (p >= q) return;
    u64 i0 = p >> 6, i1 = (q - 1) >> 6;
    if (i0 == i1) {
        u64 lo = p & 63, hi = (q - 1) & 63;
        u64 m = (~0ULL << lo) & (hi == 63 ? ~0ULL : ((1ULL << (hi + 1)) - 1));
        if (v) wds[i0] |= m; else wds[i0] &= ~m;
        updWord(i0);
        return;
    }
    {   // first partial word
        u64 lo = p & 63;
        u64 m = ~0ULL << lo;
        if (v) wds[i0] |= m; else wds[i0] &= ~m;
        updWord(i0);
    }
    for (u64 i = i0 + 1; i < i1; i++) { wds[i] = v ? ~0ULL : 0ULL; updWord(i); }
    {   // last partial word
        u64 hi = (q - 1) & 63;
        u64 m = (hi == 63) ? ~0ULL : ((1ULL << (hi + 1)) - 1);
        if (v) wds[i1] |= m; else wds[i1] &= ~m;
        updWord(i1);
    }
}

// smallest group index >= g with a zero available (or NG)
static inline u64 nextZeroGroup(u64 g) {
    if (g >= (u64)NG) return NG;
    u64 b = g >> 6; unsigned off = (unsigned)(g & 63);
    u64 m = gz3[b] & (~0ULL << off);
    if (m) return (b << 6) + (u64)__builtin_ctzll(m);
    for (u64 bb = b + 1; bb < (u64)NG3; bb++) if (gz3[bb]) return (bb << 6) + (u64)__builtin_ctzll(gz3[bb]);
    return NG;
}
static inline u64 nextOneGroup(u64 g) {
    if (g >= (u64)NG) return NG;
    u64 b = g >> 6; unsigned off = (unsigned)(g & 63);
    u64 m = go3[b] & (~0ULL << off);
    if (m) return (b << 6) + (u64)__builtin_ctzll(m);
    for (u64 bb = b + 1; bb < (u64)NG3; bb++) if (go3[bb]) return (bb << 6) + (u64)__builtin_ctzll(go3[bb]);
    return NG;
}

static inline u64 findZero(u64 p) {          // first index >= p with bit == 0
    u64 wi = p >> 6; unsigned bo = (unsigned)(p & 63);
    u64 m = ~wds[wi] & (~0ULL << bo);
    if (m) return (wi << 6) + (u64)__builtin_ctzll(m);
    {
        u64 cg = wi >> 6; unsigned wo = (unsigned)(wi & 63);
        if (wo != 63) {
            u64 m2 = gz[cg] & (~0ULL << (wo + 1));
            if (m2) { u64 j = (cg << 6) + (u64)__builtin_ctzll(m2); return (j << 6) + (u64)__builtin_ctzll(~wds[j]); }
        }
    }
    u64 g = nextZeroGroup((wi >> 6) + 1);
    while (g < (u64)NG) {
        u64 mask = gz[g];
        if (mask) {
            u64 j = (g << 6) + (u64)__builtin_ctzll(mask);
            if (j < (u64)NW) return (j << 6) + (u64)__builtin_ctzll(~wds[j]);
        }
        g = nextZeroGroup(g + 1);
    }
    return ~0ULL;
}
static inline u64 findOne(u64 p) {           // first index >= p with bit == 1
    u64 wi = p >> 6; unsigned bo = (unsigned)(p & 63);
    u64 m = wds[wi] & (~0ULL << bo);
    if (m) return (wi << 6) + (u64)__builtin_ctzll(m);
    {
        u64 cg = wi >> 6; unsigned wo = (unsigned)(wi & 63);
        if (wo != 63) {
            u64 m2 = go[cg] & (~0ULL << (wo + 1));
            if (m2) { u64 j = (cg << 6) + (u64)__builtin_ctzll(m2); return (j << 6) + (u64)__builtin_ctzll(wds[j]); }
        }
    }
    u64 g = nextOneGroup((wi >> 6) + 1);
    while (g < (u64)NG) {
        u64 mask = go[g];
        if (mask) {
            u64 j = (g << 6) + (u64)__builtin_ctzll(mask);
            if (j < (u64)NW) return (j << 6) + (u64)__builtin_ctzll(wds[j]);
        }
        g = nextOneGroup(g + 1);
    }
    return ~0ULL;
}

static inline void addOneAt(u64 p) {
    if (!getBit(p)) { setBit(p, 1); return; }
    u64 q = findZero(p + 1);
    setRange(p, q, 0);
    setBit(q, 1);
}
static inline void subOneAt(u64 p) {
    if (getBit(p)) { setBit(p, 0); return; }
    u64 q = findOne(p + 1);
    setRange(p, q, 1);
    setBit(q, 0);
}

static inline void initSummary() {
    for (int g = 0; g < NG; g++) { gz[g] = ~0ULL; go[g] = 0ULL; }
    for (int b = 0; b < NG3; b++) {
        u64 m = 0;
        for (int t = 0; t < 64; t++) { int g = b * 64 + t; if (g < NG) m |= 1ULL << t; }
        gz3[b] = m; go3[b] = 0;
    }
}

int main() {
#ifdef TEST_IO
    static char inbuf[1 << 26];
    INSZ = fread(inbuf, 1, sizeof(inbuf), stdin);
    IN = inbuf;
    static char outbuf[1 << 24];
    OUT = outbuf; OUTLIM = sizeof(outbuf);
#else
    di = (struct DI *)DUCKINFO;
    IN = di->in; INSZ = di->insz;
    OUT = di->out; OUTLIM = di->outlim;
#endif
    initSummary();

    const char *p = IN, *pend = IN + INSZ;
    auto readInt = [&]() -> long long {
        while (p < pend && (*p < '0' || *p > '9') && *p != '-') p++;
        int neg = 0;
        if (p < pend && *p == '-') { neg = 1; p++; }
        long long v = 0;
        while (p < pend && *p >= '0' && *p <= '9') v = v * 10 + (*p++ - '0');
        return neg ? -v : v;
    };
    long long n = readInt();
    (void)readInt(); (void)readInt(); (void)readInt();   // t1 t2 t3
    for (long long op = 0; op < n; op++) {
        long long t = readInt();
        if (t == 1) {
            long long a = readInt();
            long long b = readInt();
            if (a > 0) {
                u64 m = (u64)a;
                while (m) {
                    int j = __builtin_ctzll(m);
                    addOneAt((u64)b + (u64)j);
                    m &= m - 1;
                }
            } else if (a < 0) {
                u64 m = (u64)(-a);
                while (m) {
                    int j = __builtin_ctzll(m);
                    subOneAt((u64)b + (u64)j);
                    m &= m - 1;
                }
            }
        } else {
            long long k = readInt();
            if (OUTSZ + 2 <= OUTLIM) {
                OUT[OUTSZ++] = (char)('0' + getBit((u64)k));
                OUT[OUTSZ++] = '\n';
            }
        }
    }
#ifdef TEST_IO
    fwrite(outbuf, 1, OUTSZ, stdout);
#else
    di->outsz = OUTSZ;
    register long rax __asm__("rax") = 60;
    register long rdi __asm__("rdi") = 0;
    __asm__ volatile("syscall" :: "a"(rax), "D"(rdi) : "rcx", "r11", "memory");
    __builtin_unreachable();
#endif
    return 0;
}

评测结果