代码

#include<bits/stdc++.h>
#define N 30000005
using namespace std;
const int L=200005;
char LZH[L],*S=LZH,*T=LZH;
inline char gc(){
    if (S==T){
        T=(S=LZH)+fread(LZH,1,L,stdin);
        if (S==T) return EOF;
    }
    return *S++;
}
inline int read(){
    int x=0,f=1;
    char c=gc();
    for (;c<'0'||c>'9';c=gc())
        if (c=='-') f=-1;
    for (;c>='0'&&c<='9';c=gc())
        x=(x<<1)+(x<<3)+c-48;
    return x*f;
}
int n,x,y;
bool fl,a[N],b[N];
struct ZYY_CMP{
    bool operator ()(const int &x,const int &y){
        return x>y;
    }
};
struct ZYY_SET{
    int cnt[2000005];
    set<int,ZYY_CMP> S;
    ZYY_SET(){
        S.insert(-1);
        memset(cnt,0,sizeof(cnt));
    }
    void insert(int x){
        x+=16;
        if (!cnt[x>>4]) S.insert(x>>4);
        cnt[x>>4]++;
    }
    void erase(int x){
        x+=16;
        cnt[x>>4]--;
        if (!cnt[x>>4]) S.erase(x>>4);
    }
    int query(int x){
        if (x<0) return -2;
        x+=16;
        for (int i=x;i>=((x>>4)<<4)&&i>=16;i--)
            if (a[i-16]^b[i-16]) return i-16;
        int y=*S.lower_bound((x>>4)-1);
        if (y==-1) return -2;
        for (int i=(y<<4)+15;i>=(y<<4)&&i>=16;i--)
            if (a[i-16]^b[i-16]) return i-16;
        return -2;
    }
}Set;
inline void add(){
    bool tg=1;
    for (int i=y;i<=n*30&&((tg^1)||x);i++,x/=2){
        if ((tg^1)^(x&1)){
            if (a[i]^b[i]) Set.erase(i);
            else Set.insert(i);
            if (fl) tg=(a[i]^=1);
            else tg=(b[i]^=1);
        }
        else
            tg=((tg^1)&&(x&1))^1;
    }
}
int main(){
    n=read(); read(); read(); read();
    Set.insert(-2);
    for (int i=1;i<=n;i++){
        if (read()==1){
            x=read(); y=read();
            fl=(x>0); x=x<0?-x:x;
            add();
        }
        else{
            x=read(); y=Set.query(x-1);
            putchar((a[x]^b[x]^(y!=-2&&!a[y]))+'0'); puts("");
        }
    }
}

评测结果