代码

#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<algorithm>
#include<bitset>
#include<set>
#define N 30000005
using namespace std;
const int L=2333333;
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(){
	char ch=gc();
	int x=0,f=1;
	for (;ch<'0'||ch>'9';ch=gc())
		if (ch=='-') f=-1;
	for (;ch>='0'&&ch<='9';ch=gc())
		x=x*10-48+ch;
	return x*f;
}
int n,x,y;
bool fl;
bitset<N> a,b;
struct CMP{
	bool operator ()(const int &x,const int &y){
		return x>y;
	}
};
struct SET{
	int cnt[(N>>4)+1];
	set<int,CMP> s;
	SET(){
		s.insert(-1);
		memset(cnt,0,sizeof(cnt));
	}
	void insert(int x){
		x+=16; x>>=4;
		if (!(cnt[x]++)) s.insert(x);
	}
	void erase(int x){
		x+=16; x>>=4;
		if (!(--cnt[x])) s.erase(x);
	}
	int query(int x){
		if (x<0) return -2;
		for (int i=x;i>=((x>>4)<<4)&&i>=0;i--)
			if (a[i]^b[i]) return i;
		int y=*s.lower_bound(x>>4);
		if (y==-1) return -2; y=(y-1)<<4;
		for (int i=y+15;i>=y&&i>=0;i--)
			if (a[i]^b[i]) return i;
		return -2;	
	}
}Set;
void add(){
	register bool tg=0;
	for (register int i=y;tg||x;i++,x>>=1)
		if (tg^(x&1)){
			a[i]^b[i]?Set.erase(i):Set.insert(i);
			tg=(fl?a[i]:b[i]);
			fl?a[i]=1-a[i]:b[i]=1-b[i];
		}
		else
			tg&=(x&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("");
	}
}

评测结果