题意
思路
拆分成每个二进制位的加减来考虑，维护那个整数的二进制位。不难发现，进位就是找右边第一个 \(0\) 的位置，并将其赋值为 \(1\) ，之间的数全部赋值为 \(0\) ，退位就是找右边第一个 \(1\) 的位置，并将其赋值为 \(0\) ，之间的数全部赋值为 \(1\)，这个可以通过在线段树上二分实现。
当然直接搞的话复杂度 \(O(30n\log 30n)\) 当然是过不去的，但是我们一个位置只维护一个二进制数也太不值得了，数据范围中的 \(30n\) 已经在暗示，需要将每 \(30\) 二进制数一起维护。进位退位仍然是一样的找法，有一点细节，具体实现请参考代码。
代码
#include<bits/stdc++.h>
#define FOR(i,x,y) for(int i=(x),i##END=(y);i<=i##END;++i)
#define DOR(i,x,y) for(int i=(x),i##END=(y);i>=i##END;--i)
using namespace std;
template<typename T,typename _T>inline bool chk_min(T &x,const _T y){return y<x?x=y,1:0;}
template<typename T,typename _T>inline bool chk_max(T &x,const _T y){return x<y?x=y,1:0;}
typedef long long ll;
const int N=1.1e6+5;
const int B=30;
int w[N<<2],tag[N<<2],flg[N<<2];
int n,t1,t2,t3,LB,RB;
inline void Read(int &x)
{
x=0;char ch=getchar();bool f=0;
for(;!isdigit(ch);ch=getchar())if(ch=='-')f=1;
for(;isdigit(ch);ch=getchar())x=(x<<3)+(x<<1)+(ch^48);
if(f)x=~x+1;
}
void tag_up(int k,int val,int l,int r)
{
tag[k]=val;
flg[k]=val;
if(l==r)w[k]=val*((1<<B)-1);
}
void push_down(int k,int l,int r)
{
if(tag[k]==-1)return;
int mid=(l+r)>>1;
tag_up(k<<1,tag[k],l,mid);
tag_up(k<<1|1,tag[k],mid+1,r);
tag[k]=-1;
}
void push_up(int k)
{
flg[k]=(flg[k<<1]==flg[k<<1|1]?flg[k<<1]:-1);
}
void update(int k,int L,int R,int val,int l=LB,int r=RB)//[L,R] 赋值为val*(2^B)
{
if(L<=l&&r<=R){tag_up(k,val,l,r);return;}
push_down(k,l,r);
int mid=(l+r)>>1;
if(L<=mid)update(k<<1,L,R,val,l,mid);
if(R>mid)update(k<<1|1,L,R,val,mid+1,r);
push_up(k);
}
int modify(int k,int x,int val,int l=LB,int r=RB) //x位置加上val，返回进退位信息
{
if(l==r)
{
w[k]+=val;
int res=0;
if(w[k]>=(1<<B))
{
w[k]-=(1<<B);
res=1;
}
else if(w[k]<0)
{
w[k]+=(1<<B);
res=-1;
}
if(w[k]==0)flg[k]=0;
else if(w[k]==(1<<B)-1)flg[k]=1;
else flg[k]=-1;
return res;
}
push_down(k,l,r);
int mid=(l+r)>>1,res;
if(x<=mid)res=modify(k<<1,x,val,l,mid);
else res=modify(k<<1|1,x,val,mid+1,r);
push_up(k);
return res;
}
int query(int k,int x,int l=LB,int r=RB) //查询x位置的数
{
if(l==r)return w[k];
push_down(k,l,r);
int mid=(l+r)>>1;
if(x<=mid)return query(k<<1,x,l,mid);
else return query(k<<1|1,x,mid+1,r);
}
int deal(int k,int x,bool val,int l=LB,int r=RB) //修改x及x以右第一个二进制位出现val的为!val，并将数二进制位之前的赋为val，返回这个数的位置
{
if(flg[k]==!val)return -1;
if(l==r)
{
if(val)FOR(i,0,B-1)
{
if(w[k]&(1<<i))
{
w[k]^=1<<i;
break;
}else w[k]|=1<<i;
}
else FOR(i,0,B-1)
{
if(~w[k]&(1<<i))
{
w[k]|=1<<i;
break;
}else w[k]^=1<<i;
}
if(w[k]==0)flg[k]=0;
else if(w[k]==(1<<B)-1)flg[k]=1;
else flg[k]=-1;
return l;
}
int mid=(l+r)>>1;
push_down(k,l,r);
if(x>mid)
{
int res=deal(k<<1|1,x,val,mid+1,r);
push_up(k);
return res;
}
else
{
int res=deal(k<<1,x,val,l,mid);
if(res!=-1)
{
push_up(k);
return res;
}
else
{
res=deal(k<<1|1,x,val,mid+1,r);
push_up(k);
return res;
}
}
}
void Update(int val,int pos)
{
int res=modify(1,pos,val);
if(res==1)
{
res=deal(1,pos+1,0);
if(pos+1<=res-1)update(1,pos+1,res-1,0);
}
else if(res==-1)
{
res=deal(1,pos+1,1);
if(pos+1<=res-1)update(1,pos+1,res-1,1);
}
}
int Query(int a){return query(1,a);}
int main()
{
memset(tag,-1,sizeof(tag));
Read(n),Read(t1),Read(t2),Read(t3);
LB=0,RB=n+1000;
update(1,LB,RB,0);
FOR(i,1,n)
{
int op,a,b;
Read(op);
if(op==1)
{
Read(a),Read(b);
int l=b%B,r=B-l;
if(a>0)
{
Update((a&((1<<r)-1))<<l,b/B);
Update(a>>r,b/B+1);
}
else if(a<0)
{
a=-a;
Update(-((a&((1<<r)-1))<<l),b/B);
Update(-(a>>r),b/B+1);
}
}
else
{
Read(a);
printf("%d\n",Query(a/B)>>(a%B)&1);
}
}
return 0;
}