看到题目很容易想到压位+线段树，但是因为我太懒了这不太好写，我上网查了查发现了另一个很有意思的做法.
这道题的难点在于处理进位和退位，更准确地说应该是处理退位，因为如果只有进位的话，可以暴力处理，进位的次数是摊还$\mathcal O(1)$的. 那么我们可以把正的数和负的数分开加起来，假设和分别为$s _1$和$s _2$，每次询问就是要求$s _1-s _2$第$k$位上的数.
为了求这个，我们需要知道做减法的时候在第$k$位上是否出现了退位，判断方法很简单，只需要比较两个数最低的$k-1$位的大小即可. 用zkw维护$s _1$异或$s _2$，找出第$k$位以下第一个为$1$的位，然后检查一下$s _1$和$s _2$具体哪一个这位为$1$就可以了. 当然要特判一下异或的结果全都是$0$的情况.
具体实现加法的时候，我是先把从第$b$位开始的$30$位拿出来跟$a$相加，维护$s _1$异或$s _2$，再处理一次进位，不知道这么做有没有减小常数.
代码：1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
using namespace std;
const ele M0=1<<25;
const ele size=M0<<1;
ele n,M,t1,t2,t3;
bool a[2][maxm];
bool b[size];
inline void maintain(ele i){
b[i]=b[i<<1]|b[i<<1|1];
}
inline void upd(ele i){
i+=M;
b[i]^=1;
while (i>1) maintain(i>>=1);
}
ele _getl(ele i){
return i>=M?i-M:(b[i<<1|1]?_getl(i<<1|1):_getl(i<<1));
}
ele getl(ele i){
return i==1?-1:((i&1) && b[i^1]?_getl(i^1):getl(i>>1));
}
int main(){
scanf("%d%d%d%d",&n,&t1,&t2,&t3);
M=1;
while (M<=n*K) M<<=1;
while (n--){
ele op,u,v;
scanf("%d%d",&op,&u);
if (op==1){
scanf("%d",&v);
ele r=0;
if (u<0) u=-u,r=1;
ele tmp=0;
for (int i=v+K-1; i>=v; --i) tmp<<=1,tmp|=a[r][i];
ele t1=tmp;
tmp+=u;
for (int i=v; i<v+K; ++i){
a[r][i]=(tmp>>(i-v))&1;
if ((tmp>>(i-v)&1)!=(t1>>(i-v)&1)) upd(i);
}
if (tmp>=(1<<K)){
ele j;
for (j=v+K; a[r][j]; ++j) a[r][j]=0,upd(j);
a[r][j]=1; upd(j);
}
}
else{
ele ans=a[0][u]^a[1][u];
ele i=getl(u+M);
if (~i && a[0][i]<a[1][i]) ans^=1;
printf("%d\n",ans);
}
}
return 0;
}