代码

#include<cstdio>
#include<algorithm>
#include<cstring>
using namespace std;
const int ch_top=5e7+3;
char ch[ch_top],*now_r=ch-1,*now_w=ch-1;
inline int read(){
	register int f=1;
	while(*now_r<'0'){
		if (*now_r=='-') f=-1;
		++now_r;
	};
	register int x=*now_r-'0';
	while(*++now_r>='0')x=x*10+*now_r-'0';
	return x*f;
}
const int N=1000010,K=30,MX=(1<<K)-1;
int sum0[N<<2],sum1[N<<2],setv[N<<2],val[N],n;
void create(int o,int l,int r){
	sum0[o]=1,setv[o]=-1;
	if (l==r) return;
	int mid=(l+r)>>1;
	create(o<<1,l,mid);
	create(o<<1|1,mid+1,r);
}
inline void pushup(int o){
	sum0[o]=sum0[o<<1]&sum0[o<<1|1];
	sum1[o]=sum1[o<<1]&sum1[o<<1|1];
}
inline void pushdown(int o,int l,int r){
	if (~setv[o]){
		setv[o<<1]=setv[o<<1|1]=setv[o];
		sum0[o<<1]=sum0[o<<1|1]=setv[o]^1;
		sum1[o<<1]=sum1[o<<1|1]=setv[o]&1;
		int mid=(l+r)>>1;
		if (l==mid) val[l]=setv[o]?MX:0;
		if (mid+1==r) val[r]=setv[o]?MX:0;
		setv[o]=-1;
	}
}
void access(int o,int l,int r,int x){
	if (l==r) return;
	pushdown(o,l,r);
	int mid=(l+r)>>1;
	if (x<=mid) return access(o<<1,l,mid,x);
	else return access(o<<1|1,mid+1,r,x);
}
void qset(int o,int l,int r,int x,int y,int v){
	if (x<=l&&r<=y){
		setv[o]=v;
		sum0[o]=v^1,sum1[o]=v&1;
		if (l==r) val[l]=v?MX:0;
		return;
	}
	pushdown(o,l,r);
	int mid=(l+r)>>1;
	if (y<=mid) qset(o<<1,l,mid,x,y,v);
	else if (x>mid) qset(o<<1|1,mid+1,r,x,y,v);
	else qset(o<<1,l,mid,x,mid,v),qset(o<<1|1,mid+1,r,mid+1,y,v);
	pushup(o);
}
void qchange(int o,int l,int r,int x){
	if (l==r){
		sum0[o]=val[x]==0;
		sum1[o]=val[x]==MX;
		return;
	}
	pushdown(o,l,r);
	int mid=(l+r)>>1;
	if (x<=mid) qchange(o<<1,l,mid,x);
	else qchange(o<<1|1,mid+1,r,x);
	pushup(o);
}
int get0(int o,int l,int r,int x){
	if (sum0[o]) return -1;
	if (l==r) return l+sum0[o];
	pushdown(o,l,r);
	int mid=(l+r)>>1;
	if (x<mid){
		int t=get0(o<<1,l,mid,x);
		return (~t)?t:get0(o<<1|1,mid+1,r,x);
	}
	else return get0(o<<1|1,mid+1,r,x);
}
int get1(int o,int l,int r,int x){
	if (sum1[o]) return -1;
	if (l==r) return l+sum1[o];
	pushdown(o,l,r);
	int mid=(l+r)>>1;
	if (x<mid){
		int t=get1(o<<1,l,mid,x);
		return (~t)?t:get1(o<<1|1,mid+1,r,x);
	}
	else return get1(o<<1|1,mid+1,r,x);
}
void qadd(int x,int v){
	if (!v||x>n) return;
	access(1,1,n,x);
	val[x]+=v;
	int type=val[x]>MX;
	val[x]&=MX;
	qchange(1,1,n,x);
	if (type){
		int to=get1(1,1,n,x);
		if (to<=n){
			access(1,1,n,to);
			++val[to],qchange(1,1,n,to);
			if (to>x+1) qset(1,1,n,x+1,to-1,0);
		}
	}
}
void qminu(int x,int v){
	if (!v||x>n) return;
	access(1,1,n,x);
	val[x]-=v;
	int type=val[x]<0;
	if (type) val[x]+=MX+1;
	qchange(1,1,n,x);
	if (type){
		int to=get0(1,1,n,x);
		if (to<=n){
			access(1,1,n,to);
			--val[to],qchange(1,1,n,to);
			if (to>x+1) qset(1,1,n,x+1,to-1,1);
		}
	}
}
int main(){
	fread(ch,1,ch_top,stdin);
	n=read()+1,read(),read(),read();
	create(1,1,n);
	for (int i=2;i<=n;++i){
		int opt=read();
		if (opt==1){
			int a=read(),b=read();
			int id=b/K+1,id2=b%K;
			unsigned int v=a<0?-a:a;
			v=(v<<id2)&MX;
			if (a>=0) qadd(id,v);
			else qminu(id,v);
			v=a<0?-a:a,v=(v>>(K-id2))&MX;
			if (a>=0) qadd(id+1,v);
			else qminu(id+1,v);
		}
		else{
			int b=read();
			int id=b/K+1,id2=b%K;
			access(1,1,n,id);
			int v=(val[id]>>id2)&1;
			*++now_w=v+'0';
			*++now_w='\n';
		}
	}
	fwrite(ch,1,now_w-ch,stdout);
	return 0;
}

评测结果