裸做的话是 $O(n log^2 n)$ 的，即将 $a$ 进行二进制拆分，然后暴力更新.
考虑进行压位，即线段树的每一个叶节点维护长度为 $30$ 的状态.
加法操作如果需要进位的话就找到其后面的块中第一个 0 所在位置.
减法操作如果需要借位的话就找第一个 1.
第一个 0 与第一个 1 都可以用线段树维护，即 $f0,f1$ 分别表示前缀 0/1 的长度.
然后进位的话会让一些区间整体变 0/1，这个可以打 lazy 标记维护.
细节比较多，实现的时候要精细一点.
另外，这道题有点卡常，一定加读入优化，inline 之类的，会快很多.
code:
#include <cstdio>
#include <cstring>
#include <algorithm>
#define N 1000007
#define ll long long
#define lson now<<1
#define rson now<<1|1
#define setIO(s) freopen(s".in","r",stdin)
using namespace std;
const int uni=(1<<30)-1;
int bin[33],tag[N<<2],val[N<<2],n;
struct data {
int f0,f1,len;
data() {f0=0,f1=0;}
data operator+(const data &b) const {
data c;
c.len=len+b.len;
c.f0=f0,c.f1=f1;
if(f0==len) c.f0+=b.f0;
if(f1==len) c.f1+=b.f1;
return c;
}
}s[N<<2];
inline void mark(int now,int v) {
tag[now]=v;
if(v==1) {
s[now].f0=0;
s[now].f1=s[now].len;
}
else {
s[now].f0=s[now].len;
s[now].f1=0;
}
if(s[now].len==1) {
val[now]=(v?uni:0);
}
}
inline void pushdown(int now) {
if(tag[now]!=-1) {
mark(lson,tag[now]);
mark(rson,tag[now]);
tag[now]=-1;
}
}
void build(int l,int r,int now) {
s[now].len=r-l+1;
s[now].f0=s[now].len;
s[now].f1=0;
tag[now]=-1;
if(l==r) {
return;
}
int mid=(l+r)>>1;
build(l,mid,lson),build(mid+1,r,rson);
}
void uptag(int l,int r,int now,int L,int R,int v) {
if(l>=L&&r<=R) {
mark(now,v);
return;
}
pushdown(now);
int mid=(l+r)>>1;
if(L<=mid) uptag(l,mid,lson,L,R,v);
if(R>mid) uptag(mid+1,r,rson,L,R,v);
s[now]=s[lson]+s[rson];
}
void upval(int l,int r,int now,int p,int v) {
if(l==r) {
val[now]+=v;
if(val[now]<0) {
val[now]+=bin[30];
}
val[now]&=uni;
int flag=(val[now]&1),p;
s[now].f0=s[now].f1=0;
for(int i=1;i<=29;++i) {
p=((val[now]&(1<<i))>0?1:0);
if(p^flag) { flag=-1; break;}
}
if(flag!=-1) {
if(flag) s[now].f1=1;
else s[now].f0=1;
}
return;
}
pushdown(now);
int mid=(l+r)>>1;
if(p<=mid) upval(l,mid,lson,p,v);
else upval(mid+1,r,rson,p,v);
s[now]=s[lson]+s[rson];
}
int qval(int l,int r,int now,int p) {
if(l==r) return val[now];
pushdown(now);
int mid=(l+r)>>1;
if(p<=mid) return qval(l,mid,lson,p);
else return qval(mid+1,r,rson,p);
}
data query(int l,int r,int now,int L,int R) {
if(l>=L&&r<=R) {
return s[now];
}
pushdown(now);
int mid=(l+r)>>1;
if(L<=mid&&R>mid) return query(l,mid,lson,L,R)+query(mid+1,r,rson,L,R);
else if(L<=mid) return query(l,mid,lson,L,R);
else return query(mid+1,r,rson,L,R);
}
void init() {
n=1000006;
for(int i=0;i<31;++i) bin[i]=1<<i;
}
void ADD(int x,int y) {
int ori=qval(1,n,1,x);
upval(1,n,1,x,y);
if(ori+y>uni) {
data p=query(1,n,1,x+1,n);
if(p.f1) {
uptag(1,n,1,x+1,x+p.f1,0);
}
upval(1,n,1,x+1+p.f1,1);
}
}
void DEC(int x,int y) {
int ori=qval(1,n,1,x);
upval(1,n,1,x,-y);
if(ori-y<0) {
data p=query(1,n,1,x+1,n);
if(p.f0) {
uptag(1,n,1,x+1,x+p.f0,1);
}
upval(1,n,1,x+1+p.f0,-1);
}
}
char *p1,*p2,buf[100000];
#define nc() (p1==p2&&(p2=(p1=buf)+fread(buf,1,100000,stdin),p1==p2)?EOF:*p1++)
int rd() {
int x=0,flag=1; char c;
do {
c=nc();
if(c=='-') flag=-1;
}while(c<48);
while(c>47) x=(((x<<2)+x)<<1)+(c^48),c=nc();
return x*flag;
}
int main() {
// setIO("input");
init();
int m,x,y,z;
m=rd(),x=rd(),y=rd(),z=rd();
build(1,n,1);
for(int i=1;i<=m;++i) {
z=rd();
if(z==1) {
x=rd(),y=rd();
if(!x) continue;
int rx=abs(x);
int id=(y+30)/30,rw=rx>>(id*30-y);
if(x<0) {
DEC(id,bin[y-(id-1)*30]*(rx&(bin[id*30-y]-1)));
if(rw) DEC(id+1,rw);
}
if(x>0) {
ADD(id,bin[y-(id-1)*30]*(rx&(bin[id*30-y]-1)));
if(rw) ADD(id+1,rw);
}
}
if(z==2) {
x=rd();
int id=(x+30)/30;
int rm=x-(id-1)*30;
int p=qval(1,n,1,id);
printf("%d
",(p&bin[rm])>0);
}
}
return 0;
}