C++11(clang++ 3.9) 解法, 执行用时: 1257ms, 内存消耗: 448076K, 提交时间: 2020-03-08 13:43:17

#include<cstdio>
#include<cstring>
#include<algorithm>
#include<cmath>
#define LL long long
using namespace std;
const int M=3e7+31,N=1<<25;
int read()
{
	int ans=0,f=1,c=getchar();
     while(c<'0'||c>'9') 
     {
     	if(c=='-') f=-1;c=getchar();
	 }
	 while(c>='0'&&c<='9')
	 {
	 	ans=ans*10+(c-'0');
	 	c=getchar();
	 }
	 return ans*f;
}
int s1[M],s2[M],cnt;
int l,r,a,b,n,k;
void prepare(int x)
{
	if(!x) return;
	int v=x>0?x:-x,w[31];
	cnt=0;
	for(int i=30;i>=0;i--)
	{
		int now=1<<i;
		if(now&v) v-=now,w[++cnt]=i;
		if(!v) break;
	}
	l=w[cnt]+b;r=w[1]+b;
	if(x>0)
	for(int i=1;i<=cnt;i++)
	{
		int now=w[i]+b;
		while(s1[now]) s1[now++]=0,r=max(r,now);
		s1[now]=1;
	}
	else
    for(int i=1;i<=cnt;i++)
    {
    	int now=w[i]+b;
    	while(s2[now]) s2[now++]=0,r=max(r,now);
    	s2[now]=1;
	}
	
}
int tr[2*N],T,now;
void modify()
{
	for(int i=l;i<=r;i++) tr[i+N]=s1[i]^s2[i];
	for(l=(l+N)>>1,r=(r+N)>>1;l;l>>=1,r>>=1)
	for(int i=l;i<=r;i++) tr[i]=tr[i<<1]|tr[i<<1^1];
}
int find(int k)
{
	for(k+=N;k;k>>=1) if(k&1&tr[k^1])
	{
		for(k^=1;k<N;k=k<<1^tr[k<<1^1]);
		return k-N;
	}
	return -1;
}
int main()
{
	n=read();T=read();T=read();T=read();
	for(int i=1;i<=n;i++)
	{
		k=read();
		if(k==1)
		{
			a=read();b=read();
			prepare(a);
			modify();
		}
		else
		{
			a=read();
			now=find(a);
			if(s1[now]>s2[now]||now==-1) printf("%d\n",s1[a]^s2[a]);
			else printf("%d\n",s1[a]==s2[a]);
		}
	}
	return 0;
}