代码

#include<cstdio>
typedef long long ll;
const int inf=1<<30;
int firz[1<<16];
unsigned A[1<<21];
int T[1<<21][2];
bool tag[1<<21];
#define Def int node,int L,int R
#define Mid (L+R>>1)
#define Ls node<<1,L,Mid
#define Rs node<<1|1,Mid,R
inline int min(int a,int b){return a<b?a:b;}
inline int fir0(unsigned x){return firz[x&65535]<16?firz[x&65535]:firz[x>>16]+16;}
void build(Def){
	T[node][0]=L<<5;
	T[node][1]=inf;
	if(R-L>1)build(Ls),build(Rs);
}
inline void pushup(int node){
	bool ty=tag[node];
	T[node][0]=min(T[node<<1][ty],T[node<<1|1][ty]);
	T[node][1]=min(T[node<<1][!ty],T[node<<1|1][!ty]);
}
unsigned modify(Def,int i,unsigned x,bool ty,bool y=0){
///*noi*/printf("modify [%d,%d) %d %u %d %d\n",L,R,i,x,ty,y);
	if(R-L==1){
		unsigned o=A[i],res;
		if(y)o=~o;
		if(ty){
			res=o<x?1:0;
			o-=x;
		}
		else{
			res=o>~x?1:0;
			o+=x;
		}
		A[i]=y?~o:o;
		(T[node][y]=fir0(o))==32?T[node][y]=inf:T[node][y]+=L<<5;
		(T[node][!y]=fir0(~o))==32?T[node][!y]=inf:T[node][!y]+=L<<5;
///*noi*/printf("T={%d,%d} res=%u\n",T[node][0],T[node][1],res);
		return res;
	}
	y^=tag[node];
	unsigned res=i<Mid?modify(Ls,i,x,ty,y):modify(Rs,i,x,ty,y);
	pushup(node);
	return res;
}
void reverse(Def,int l,int r){
	if(l==L&&r==R){
		if(R-L==1)A[l]=~A[l];
		else tag[node]=!tag[node];
		int t=T[node][0];T[node][0]=T[node][1];T[node][1]=t;
		return;
	}
	if(r<=Mid)reverse(Ls,l,r);
	else if(l>=Mid)reverse(Rs,l,r);
	else reverse(Ls,l,Mid),reverse(Rs,Mid,r);
	pushup(node);
}
int find(Def,int i,bool ty){
	if(T[node][ty]>=inf)return inf;
	if(i==L)return T[node][ty];
	ty^=tag[node];
	if(i>=Mid)return find(Rs,i,ty);
	int x=find(Ls,i,ty);
	if(x<inf)return x;
	return find(Rs,Mid,ty);
}
unsigned query(Def,int i){
///*noi*/printf("query [%d,%d) %d tag=%d\n",L,R,i,tag[node]);
	if(R-L==1)return A[i];
	unsigned x=i<Mid?query(Ls,i):query(Rs,i);
	if(tag[node])x=~x;
	return x;
}
int main(){
	int n,t1,t2,t3;scanf("%d%d%d%d",&n,&t1,&t2,&t3);
	for(int i=1;i<1<<16;i++)firz[i]=i%2?firz[i/2]+1:0;
	build(1,0,1<<20);
	while(n--){
		int op;scanf("%d",&op);
		if(op==1){
			int a,b;scanf("%d%d",&a,&b);
			int k=b>>5,pos=b&31;
			bool neg=(a<0);
			if(neg)a=-a;
			unsigned vl=(unsigned)(((ll)a)<<pos),vr=(unsigned)(((ll)a)>>32-pos);
			if(vl)vr+=modify(1,0,1<<20,k,vl,neg);
			if(vr&&modify(1,0,1<<20,k+1,vr,neg)){
				int fir=find(1,0,1<<20,k+2,neg);
				if(k+2<fir/32)reverse(1,0,1<<20,k+2,fir/32);
				modify(1,0,1<<20,fir/32,1,neg);
			}
		}
		else{
			int k,s;scanf("%d",&k);
			s=query(1,0,1<<20,k>>5)>>(k&31)&1;
			printf("%d\n",s);
		}
	}
}

评测结果