代码

#include<bits/stdc++.h>
#define lc (x<<1)
#define rc (x<<1|1)
#define ll long long
using namespace std;
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 N=1e6+10;
const int g=30;
const int rt=1e6;
bool tag[N<<2][2];int len[N<<2][2],v[N<<2];
int n,t1,t2,t3,bin[33];
inline void pushdown(int x,int l,int r){
    int mid=l+r>>1;
    if (tag[x][0]){
        tag[lc][0]=1;tag[lc][1]=0;v[lc]=v[rc]=0;len[lc][0]=mid-l+1;len[lc][1]=0;
        tag[rc][0]=1;tag[rc][1]=0;len[rc][0]=r-mid;len[rc][1]=0;tag[x][0]=0;
    }
    if (tag[x][1]){
        tag[lc][1]=1;tag[lc][0]=0;v[lc]=v[rc]=bin[30]-1;len[lc][1]=mid-l+1;len[lc][0]=0;
        tag[rc][1]=1;tag[rc][0]=0;len[rc][1]=r-mid;len[rc][0]=0;tag[x][1]=0;
    }
}
inline void update(int x,int l,int r){
    int mid=l+r>>1;
    len[x][0]=(len[lc][0]==mid-l+1?1:0)*len[rc][0]+len[lc][0];
    len[x][1]=(len[lc][1]==mid-l+1?1:0)*len[rc][1]+len[lc][1];
}
inline void modify(int x,int l,int r,int l1,int r1,int op){
    if(l1<=l&&r1>=r){
        if (op==1) v[x]=bin[g]-1;else v[x]=0;
        tag[x][op]=1;tag[x][op^1]=0;len[x][op]=r-l+1;len[x][op^1]=0;return;
    }int mid=l+r>>1;pushdown(x,l,r);
    if (l1<=mid) modify(lc,l,mid,l1,r1,op);
    if (r1>mid) modify(rc,mid+1,r,l1,r1,op);update(x,l,r);
}
inline int insert1(int x,int l,int r,int p,int v1){
    if (l==r){
        v[x]+=v1;int flag=0;len[x][0]=len[x][1]=0;
        if (v[x]>=bin[g]){flag=1;v[x]%=bin[g];}
        if (v[x]<0){flag=-1;v[x]+=bin[g];}
        if (v[x]==bin[g]-1) len[x][1]=1;if (!v[x]) len[x][0]=1;
        return flag;
    }int mid=l+r>>1;pushdown(x,l,r);int flag=0;
    if(p<=mid) flag=insert1(lc,l,mid,p,v1);
    else flag=insert1(rc,mid+1,r,p,v1);update(x,l,r);return flag;
}
inline int qr(int x,int l,int r,int p,int op){
    if (l==r) return len[x][op];
    int mid=l+r>>1;pushdown(x,l,r);
    if (p>mid) return qr(rc,mid+1,r,p,op);
    else{
        int leno=qr(lc,l,mid,p,op);
        if(leno==mid-p+1) 
            if (len[rc][op]==r-mid) return leno+r-mid;else return leno+len[rc][op];
        else return leno;
    }
}
inline int query(int x,int l,int r,int p){
    if(l==r) return v[x];
    int mid=l+r>>1;pushdown(x,l,r);
    if (p<=mid) return query(lc,l,mid,p);
    else return query(rc,mid+1,r,p);
}
inline void build(int x,int l,int r){
    if (l==r) {len[x][0]=1;return;}
    int mid=l+r>>1;build(lc,l,mid);
    build(rc,mid+1,r);update(x,l,r);
}
int main(){
//  freopen("a.in","r",stdin);
    n=read();t1=read();t2=read();t3=read();
    for (int i=0;i<=31;++i) bin[i]=1<<i;build(1,0,rt);
    for (int owo=1;owo<=n;++owo){
        int op=read();
        if(op==1){
            int a=read(),b=read();
            int pos=b/g,st=b%g,fi;
            if (a<0) {
                a=-a;fi=a%bin[(g-1)-st+1],a>>=(g-1)-st+1;fi=-fi;a=-a;
            }else fi=a%bin[(g-1)-st+1],a>>=(g-1)-st+1;
            fi=fi*bin[st];a+=insert1(1,0,rt,pos,fi);
            if (!a) continue;int flag=insert1(1,0,rt,pos+1,a);if(!flag) continue;
            if (flag==1){
                int len1=qr(1,0,rt,pos+2,1);if (len1>=1) modify(1,0,rt,pos+2,pos+2+len1-1,0);
                insert1(1,0,rt,pos+2+len1,1);
            }else{
                int len0=qr(1,0,rt,pos+2,0);if (len0>=1) modify(1,0,rt,pos+2,pos+2+len0-1,1);
                insert1(1,0,rt,pos+2+len0,-1);
            }
        }else{
            int b=read(),pos=b/g,st=b%g;printf("%d\n",(query(1,0,rt,pos)&bin[st])?1:0);
        }
    }
    return 0;
}

评测结果