ORZYYB
题目大意：你需要维护一个有$3\times 10^7$个二进制位的数，有一种修改方式和一种询问方式
对这个数加上$a\times2^b$，其中$|a|≤10^9$，$b≤3\times 10^7$，保证需要维护的这个数始终非负
询问这个数第k个二进制位的值
总共有$10^6$次询问/修改操作
我们不难发现，如果只有加法操作的话，对任意一个位执行加法操作，均摊进位次数是1。
证明是显然的（我貌似之前在MC里面用红石电路模拟过二进制进位过程。。。。）
也就是说暴力加暴力进位的复杂度是正确的。
但是这里有a并不保证非负，这样一来通过精心（大雾）的构造方式，可以让你疯狂进位/退位，所以并不能单纯暴力模拟。
我们考虑对加法部分和减法部分分开维护（设A为加法的部分，B为减法的部分），这样的进位复杂度显然就是对的。
考虑到$A≥B$，那么显然有$\frac{A}{2^k}≥\frac{B}{2^k}$。
对于每次查询操作，我们分别找出A的第k位和B的第k位
现在对答案会产生影响的显然是A的末k-1位和B的末k-1位相减后，A的第k位是否需要退位。
我们考虑开一个set，若A的第i位和B的第i位不同，那么我们就把i丢入set中。
我们考虑在set中找到满足<k的i，直接判断A的第i位和B的第i位的大小关系，就可以判出是否会产生退位。
set的维护在对大数做修改的时候去更新。
考虑到这个数非常大，直接维护会超时，我们不妨做一波压位，然后再来维护，这样就跑得快很多了。
注意！对于一个32位的数，左移32位的操作会直接被忽略。
当然之前还有一些比较菜的想法，维护整个数的差分序列，若差分序列某个位置不为0就丢入set中，然后也来压位一波，不过代码估计长很多。
时间复杂度：$O(n\ log\ n)$
#include<bits/stdc++.h>
#define M 500005
#define S 64
#define L unsigned long long
using namespace std; int n,t1,t2,t3;
L a[M]={},b[M]={},P=-;
set<int> s; void upd(int x){
if(a[x]!=b[x]) s.insert(x);
else{
if(s.find(x)!=s.end()) s.erase(x);
}
} int main(){
scanf("%d%d%d%d",&n,&t1,&t2,&t3);
while(n--){
int op,B; scanf("%d",&op); L A;
int aa;
if(op==){
scanf("%d%d",&aa,&B);
if(aa>){
A=aa;
int x=B/S,y=B%S;
L s1=(A<<y)&P,s2=y?(A>>(S-y)):;
a[x]=a[x]+s1; upd(x);
if(a[x]<s1) s2++;
while(s2){
x++;
a[x]=a[x]+s2; upd(x);
s2=(a[x]<s2);
}
}else{
A=-aa;
int x=B/S,y=B%S;
L s1=(A<<y)&P,s2=y?(A>>(S-y)):;
b[x]=b[x]+s1; upd(x);
if(b[x]<s1) s2++;
while(s2){
x++;
b[x]=b[x]+s2; upd(x);
s2=(b[x]<s2);
}
}
}else{
scanf("%d",&B);
int x=B/S,y=B%S;
int ans=(((a[x]>>y)^(b[x]>>y))&);
A=y?(a[x]<<(S-y)):;
L BB=y?(b[x]<<(S-y)):;
if(A<BB) ans^=;
if(A==BB){
set<int>::iterator it=s.lower_bound(x);
if(it!=s.begin()){
it--; x=*it;
if(a[x]<b[x]) ans^=;
}
}
printf("%d\n",ans);
}
}
}