代码

#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

typedef unsigned long u64; typedef long i64;
enum { W=470000, G1=(W+63)/64, G2=(G1+63)/64, G3=(G2+63)/64 };
static u64 positive[W],negative[W],summary1[G1],summary2[G2],summary3[G3];

static __attribute__((always_inline)) inline void change_summary(int wi,u64 old){
    u64 now=positive[wi]|negative[wi];if((!old)==(!now))return;
    int a=wi>>6,b=wi&63;u64 old1=summary1[a];
    if(now)summary1[a]|=1UL<<b;else summary1[a]&=~(1UL<<b);
    if((!old1)==(!summary1[a]))return;
    int c=a>>6,d=a&63;u64 old2=summary2[c];
    if(summary1[a])summary2[c]|=1UL<<d;else summary2[c]&=~(1UL<<d);
    if((!old2)==(!summary2[c]))return;
    int e=c>>6,f=c&63;
    if(summary2[c])summary3[e]|=1UL<<f;else summary3[e]&=~(1UL<<f);
}
static __attribute__((noinline)) void add_digit(int pos){int wi=pos>>6,off=pos&63;
    for(;;){u64 old=positive[wi]|negative[wi],tail=positive[wi]>>off,inv=~tail;
        int room=64-off,c=inv?__builtin_ctzl(inv):64;
        if(c<room){positive[wi]&=~(((1UL<<c)-1)<<off);pos+=c;change_summary(wi,old);break;}
        positive[wi]&=off?((1UL<<off)-1):0;change_summary(wi,old);++wi;off=0;pos=wi<<6;}
    wi=pos>>6;off=pos&63;u64 old=positive[wi]|negative[wi],bit=1UL<<off;
    if(negative[wi]&bit)negative[wi]^=bit;else positive[wi]|=bit;change_summary(wi,old);
}
static __attribute__((noinline)) void sub_digit(int pos){int wi=pos>>6,off=pos&63;
    for(;;){u64 old=positive[wi]|negative[wi],tail=negative[wi]>>off,inv=~tail;
        int room=64-off,c=inv?__builtin_ctzl(inv):64;
        if(c<room){negative[wi]&=~(((1UL<<c)-1)<<off);pos+=c;change_summary(wi,old);break;}
        negative[wi]&=off?((1UL<<off)-1):0;change_summary(wi,old);++wi;off=0;pos=wi<<6;}
    wi=pos>>6;off=pos&63;u64 old=positive[wi]|negative[wi],bit=1UL<<off;
    if(positive[wi]&bit)positive[wi]^=bit;else negative[wi]|=bit;change_summary(wi,old);
}
static __attribute__((always_inline)) inline void add_shifted(i64 x,int bit){u64 a=x<0?-x:x;
    while(a){int b=__builtin_ctzl(a);if(x>0)add_digit(bit+b);else sub_digit(bit+b);a&=a-1;}}

static __attribute__((always_inline)) inline int previous_word(int wi){
    if(wi<0)return-1;int a=wi>>6,b=wi&63;u64 x=summary1[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=summary2[c]&(~0UL>>(63-d));
    if(!x){if(--c<0)return-1;int e=c>>6,f=c&63;x=summary3[e]&(~0UL>>(63-f));
        if(!x){if(--e<0)return-1;x=summary3[e];if(!x)return-1;}c=(e<<6)+(63-__builtin_clzl(x));x=summary2[c];}
    a=(c<<6)+(63-__builtin_clzl(x));x=summary1[a];return(a<<6)+(63-__builtin_clzl(x));
}
static __attribute__((always_inline)) inline int next_word(int wi){
    if(wi>=W)return-1;int a=wi>>6,b=wi&63;u64 x=summary1[a]&(~0UL<<b);
    if(x)return(a<<6)+__builtin_ctzl(x);
    ++a;if(a>=G1)return-1;int c=a>>6,d=a&63;x=summary2[c]&(~0UL<<d);
    if(!x){++c;if(c>=G2)return-1;int e=c>>6,f=c&63;x=summary3[e]&(~0UL<<f);
        if(!x){++e;if(e>=G3)return-1;x=summary3[e];if(!x)return-1;}c=(e<<6)+__builtin_ctzl(x);x=summary2[c];}
    a=(c<<6)+__builtin_ctzl(x);x=summary1[a];return(a<<6)+__builtin_ctzl(x);
}
static __attribute__((always_inline)) inline unsigned query(int bit){int wi=bit>>6,off=bit&63;u64 nz=positive[wi]|negative[wi],at=(nz>>off)&1;
    if(!at){u64 higher=off==63?0:nz&(~0UL<<(off+1));if(!higher&&next_word(wi+1)<0)return 0;}
    u64 lower=off?nz&((1UL<<off)-1):0;if(lower){int b=63-__builtin_clzl(lower);return at^((negative[wi]>>b)&1);}
    int w=previous_word(wi-1);if(w<0)return at;int b=63-__builtin_clzl(positive[w]|negative[w]);return at^((negative[w]>>b)&1);
}
static void solve(DuckInfo*i){const char*p=i->stdin_ptr;int n=duck_read_u64(&p);duck_read_u64(&p);duck_read_u64(&p);duck_read_u64(&p);char*o=i->stdout_ptr;
 while(n--){unsigned t=duck_read_u64(&p);if(t==1){i64 x=duck_read_i64(&p);int b=duck_read_u64(&p);if(x)add_shifted(x,b);}else{int b=duck_read_u64(&p);*o++='0'+query(b);*o++='\n';}}i->stdout_size=o-i->stdout_ptr;}
#ifdef LOCAL
#include<stdio.h>
int main(){static char in[20000000],out[2000000];DuckInfo i={0};i.stdin_size=fread(in,1,sizeof in,stdin);i.stdin_ptr=in;i.stdout_ptr=out;solve(&i);fwrite(out,1,i.stdout_size,stdout);}
#else
__attribute__((noreturn))void __libc_start_main(void*x,long n,char**v){DuckInfo*i=duck_info(n,v);solve(i);duck_exit();}int main(){}
#endif

评测结果