代码

#include<cstdio>
#include<cctype>
#include<cstring>
#include<algorithm>
#include<iostream>
using namespace std;
#define N 1000010
#define lc (x<<1)
#define rc (x<<1|1)
int n0=30;
const int full=(1<<n0)-1;
inline char gc(){
    static char now[1<<16],*S,*T;
    if (T==S){T=(S=now)+fread(now,1,1<<16,stdin);if (T==S) return EOF;}
    return *S++;
}
inline int read(){
    int x=0,f=1;char ch=gc();
    while(!isdigit(ch)) {if (ch=='-') f=-1;ch=gc();}
    while(isdigit(ch)) x=x*10+ch-'0',ch=gc();
    return x*f;
}
const int OUT_LEN = 1024 * 1024;
char obuf[OUT_LEN], *oh = obuf;
inline void write_char(char c) {
    if (oh == obuf + OUT_LEN) fwrite(obuf, 1, OUT_LEN, stdout), oh = obuf;
    *oh++ = c;
}
template<class T>
inline void W(T x) {
    static int buf[30], cnt;
    if (x == 0) write_char('0');
    else {
        if (x < 0) write_char('-'), x = -x;
        for (cnt = 0; x; x /= 10) buf[++cnt] = x % 10 + 48;
        while (cnt) write_char(buf[cnt--]);
    }
}
inline void flush() {
    fwrite(obuf, 1, oh - obuf, stdout);
}
struct node{
    int len0,len1,v,tag;//tag=-1->0 tag=1->full
}tree[N<<2];
inline void update(int x,int l,int r,int mid){
    int len=mid-l+1;
    tree[x].len0=(tree[lc].len0==len)*tree[rc].len0+tree[lc].len0;
    tree[x].len1=(tree[lc].len1==len)*tree[rc].len1+tree[lc].len1;
}
inline void dochange(int x,int l,int r,int v){
    if (v==full){
        tree[x].v=full;tree[x].len0=0;tree[x].len1=r-l+1;tree[x].tag=2;return;
    }tree[x].v=0;tree[x].len1=0;tree[x].len0=r-l+1;tree[x].tag=-1;
}
inline void pushdown(int x,int l,int r){
    if (!tree[x].tag) return;int mid=l+r>>1;
    dochange(lc,l,mid,tree[x].tag==-1?0:full);
    dochange(rc,mid+1,r,tree[x].tag==-1?0:full);
    tree[x].tag=0;
}
inline bool modify(int x,int l,int r,int l1,int r1,int v){
    if (l1<=l&&r1>=r){
        tree[x].v+=v;bool flag=0;tree[x].len0=tree[x].len1=0;
        if (tree[x].v>full) tree[x].v&=full,flag=1;
        if (tree[x].v<0) tree[x].v+=full+1,flag=1;
        if (tree[x].v==full) tree[x].tag=2,tree[x].len1=r-l+1;
        if (!tree[x].v) tree[x].tag=-1,tree[x].len0=r-l+1;return flag;
    }int mid=l+r>>1;pushdown(x,l,r);bool tmp=0;
    if (l1<=mid) tmp|=modify(lc,l,mid,l1,r1,v);
    if (r1>mid) tmp|=modify(rc,mid+1,r,l1,r1,v);update(x,l,r,mid);return tmp;
}
inline void change(int x,int l,int r,int l1,int r1,int v){
    if (l1>r1) return;
    if (l1<=l&&r1>=r) {dochange(x,l,r,v);return;}
    int mid=l+r>>1;pushdown(x,l,r);
    if (l1<=mid) change(lc,l,mid,l1,r1,v);
    if (r1>mid) change(rc,mid+1,r,l1,r1,v);update(x,l,r,mid);
}
inline bool query(int x,int l,int r,int p,int k){
    if(l==r) return (tree[x].v>>k)&1;int mid=l+r>>1;pushdown(x,l,r);
    if (p<=mid) return query(lc,l,mid,p,k);
    else return query(rc,mid+1,r,p,k);
}
inline int lg(int x){
    static int cnt;cnt=0;while(x) ++cnt,x>>=1;return cnt;
}
inline int qr1(int x,int l,int r,int p,int len){
    if (l==r) return tree[x].len1==0?0:tree[x].len1+len;int mid=l+r>>1;pushdown(x,l,r);
    if(p<=mid){
        if (tree[rc].len1==r-mid) return qr1(lc,l,mid,p,len+tree[rc].len1);
        return qr1(lc,l,mid,p,tree[rc].len1);
    }return qr1(rc,mid+1,r,p,len);      
}
inline int qr0(int x,int l,int r,int p,int len){
    if (l==r) return tree[x].len0==0?0:tree[x].len0+len;int mid=l+r>>1;pushdown(x,l,r);
    if(p<=mid){
        if (tree[rc].len0==r-mid) return qr0(lc,l,mid,p,len+tree[rc].len0);
        return qr0(lc,l,mid,p,tree[rc].len0);
    }return qr0(rc,mid+1,r,p,len);
}
inline int abs(int x){return x<0?-x:x;}
int n,t1,t2,t3,bin[30];
int main(){
    //freopen("bzoj4942.in","r",stdin);
    //freopen("bzoj4942.out","w",stdout);
    n=read();t1=read();t2=read();t3=read();dochange(1,0,1e6,0);
    for (int i=0;i<=29;++i) bin[i]=(1<<i+1)-1;
    for (int i=1;i<=n;++i){
        static int op,a,b,k,b1,r,b2;static bool tmp;op=read();
        if (op==1){
            a=read(),b=read();b1=b/n0,b2=b%n0;
            if (a>0){
                tmp=modify(1,0,1e6,b1,b1,(a&(bin[n0-b2-1]))*(1<<b2));
                a>>=n0-b2;a+=tmp;if (!a) continue;
                tmp=modify(1,0,1e6,b1+1,b1+1,a);if (!tmp) continue;
                r=qr1(1,0,1e6,b1+2,0);change(1,0,1e6,b1+2,b1+2+r-1,0);
                modify(1,0,1e6,b1+2+r,b1+2+r,1);
            }else{a=abs(a);
                tmp=modify(1,0,1e6,b1,b1,-(a&(bin[n0-b2-1]))*(1<<b2));
                a>>=n0-b2;a+=tmp;if (!a) continue;
                tmp=modify(1,0,1e6,b1+1,b1+1,-a);if (!tmp) continue;
                r=qr0(1,0,1e6,b1+2,0);change(1,0,1e6,b1+2,b1+2+r-1,full);
                modify(1,0,1e6,b1+2+r,b1+2+r,-1);
            }
        }else{
            k=read();static int tmp;
            tmp=k/n0;k%=n0;W(query(1,0,1e6,tmp,k));write_char('\n');
        }
    }flush();
    return 0;
}

评测结果