代码

#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
#include<ctime>
#include<cstdlib>
using namespace std;
typedef long long ll;
void read(int &s)
{
	int c;
	int b=0;
	while(((c=getchar())<'0'||c>'9')&&c!='-');
	if(c=='-')
	{
		b=1;
		s=0;
	}
	else
		s=c-'0';
	while((c=getchar())>='0'&&c<='9')
		s=s*10+c-'0';
	if(b)
		s=-s;
}
const int b30=(1<<30)-1;
const int all=1000000;
int bitcount(int x)
{
	int s=0;
	for(;x;x-=x&-x,s++);
	return s;
}
#define ls(x) ((x)<<1)
#define rs(x) (((x)<<1)|1)
int t[5000010];
int s[5000010];
int a[5000010];
void addt(int p,int v,int l,int r)
{
	t[p]=v;
	s[p]=v*(r-l+1);
	if(v)
		a[p]=b30;
	else
		a[p]=0;
}
void push(int p,int l,int mid,int r)
{
	if(t[p]==-1)
		return;
	addt(ls(p),t[p],l,mid);
	addt(rs(p),t[p],mid+1,r);
	t[p]=-1;
}
void change(int p,int x,int v,int l,int r)
{
	if(l==r)
	{
		a[p]=v;
		s[p]=bitcount(v);
		return;
	}
	int mid=(l+r)>>1;
	if(~t[p])
		push(p,l,mid,r);
	if(x<=mid)
		change(ls(p),x,v,l,mid);
	else
		change(rs(p),x,v,mid+1,r);
	s[p]=s[ls(p)]+s[rs(p)];
}
int query(int p,int x,int l,int r)
{
	if(l==r)
		return a[p];
	int mid=(l+r)>>1;
	if(~t[p])
		push(p,l,mid,r);
	if(x<=mid)
		return query(ls(p),x,l,mid);
	else
		return query(rs(p),x,mid+1,r);
}
//int query(int p,int ll,int rr,int l,int r)
//{
//	if(ll<=l&&rr>=r)
//		return s[p];
//	int mid=(l+r)>>1;
//	if(~t[p])
//		push(p,l,mid,r);
//	int s=0;
//	if(ll<=mid)
//		s+=query(ls(p),ll,rr,l,mid);
//	if(rr>mid)
//		s+=query(rs(p),ll,rr,mid+1,r);
//	return s;
//}
void find1(int p,int l,int r)
{
	if(l==r)
	{
		a[p]++;
		s[p]=bitcount(a[p]);
		return;
	}
	int mid=(l+r)>>1;
	if(~t[p])
		push(p,l,mid,r);
	if(s[ls(p)]<30*(mid-l+1))
		find1(ls(p),l,mid);
	else
	{
		addt(ls(p),0,l,mid);
		find1(rs(p),mid+1,r);
	}
	s[p]=s[ls(p)]+s[rs(p)];
}
void find2(int p,int l,int r)
{
	if(l==r)
	{
		a[p]--;
		s[p]=bitcount(a[p]);
		return;
	}
	int mid=(l+r)>>1;
	if(~t[p])
		push(p,l,mid,r);
	if(s[ls(p)])
		find2(ls(p),l,mid);
	else
	{
		addt(ls(p),30,l,mid);
		find2(rs(p),mid+1,r);
	}
	s[p]=s[ls(p)]+s[rs(p)];
}
int solve1(int p,int x,int l,int r)
{
	if(l==r)
		return 0;
	int mid=(l+r)>>1;
	if(~t[p])
		push(p,l,mid,r);
	if(x>mid)
	{
		int b=solve1(rs(p),x,mid+1,r);
		s[p]=s[ls(p)]+s[rs(p)];
		return b;
	}
	if(solve1(ls(p),x,l,mid))
	{
		s[p]=s[ls(p)]+s[rs(p)];
		return 1;
	}
	if(s[rs(p)]<30*(r-mid))
	{
		find1(rs(p),mid+1,r);
		s[p]=s[ls(p)]+s[rs(p)];
		return 1;
	}
	addt(rs(p),0,mid+1,r);
	s[p]=s[ls(p)]+s[rs(p)];
	return 0;
}
int solve2(int p,int x,int l,int r)
{
	if(l==r)
		return 0;
	int mid=(l+r)>>1;
	if(~t[p])
		push(p,l,mid,r);
	if(x>mid)
	{
		int b=solve2(rs(p),x,mid+1,r);
		s[p]=s[ls(p)]+s[rs(p)];
		return b;
	}
	if(solve2(ls(p),x,l,mid))
	{
		s[p]=s[ls(p)]+s[rs(p)];
		return 1;
	}
	if(s[rs(p)])
	{
		find2(rs(p),mid+1,r);
		s[p]=s[ls(p)]+s[rs(p)];
		return 1;
	}
	addt(rs(p),30,mid+1,r);
	s[p]=s[ls(p)]+s[rs(p)];
	return 0;
}
void add(int x,int v)
{
	int s=query(1,x,1,all);
	s=s+v;
	if(s>b30)
	{
		solve1(1,x,1,all);
		s-=1<<30;
	}
	change(1,x,s,1,all);
}
void del(int x,int v)
{
	int s=query(1,x,1,all);
	s=s-v;
	if(s<0)
	{
		solve2(1,x,1,all);
		s+=1<<30;
	}
	change(1,x,s,1,all);
}
int main()
{
	memset(t,-1,sizeof t);
	memset(s,0,sizeof s);
	memset(a,0,sizeof a);
	int n,t1,t2,t3;
	scanf("%d%d%d%d",&n,&t1,&t2,&t3);
	int c,x,y;
	int i;
	for(i=1;i<=n;i++)
	{
//		scanf("%d",&c);
		read(c);
		if(c==1)
		{
//			scanf("%d%d",&x,&y);
			read(x);
			read(y);
			if(x>0)
			{
				int bl=y/30+1;
				int t=y%30;
				ll s=ll(x)<<t;
				int s1=s&b30;
				int s2=s>>30;
				if(s1)
					add(bl,s1);
				if(s2)
					add(bl+1,s2);
			}
			else if(x<0)
			{
				x=-x;
				int bl=y/30+1;
				int t=y%30;
				ll s=ll(x)<<t;
				int s1=s&b30;
				int s2=s>>30;
				if(s1)
					del(bl,s1);
				if(s2)
					del(bl+1,s2);
			}
		}
		else
		{
//			scanf("%d",&x);
			read(x);
			int bl=x/30+1;
			int t=x%30;
			int s=query(1,bl,1,all);
			s=(s>>t)&1;
			printf("%d\n",s);
		}
	}
	return 0;
}

评测结果