首先把每32位压成一个unsigned int（当然只要压起来能过就行）。如果不考虑进/退位的话，每次只要将加/减上去的数拆成两部分直接单点修改就好了。那么考虑如何维护进/退位。可以发现进位的过程其实就是将一段连续的inf改为0，并把之后一位+1，也就是说只要找到某一位之后第一个不是inf的位就好了。我们用线段树维护这个东西，记录一下某个节点表示的区间是否全为inf。查询时先从叶子节点往上爬，直到当前节点代表的区间中在该叶子节点右边的位不全为inf时停止，之后再往下找最左的非inf位。退位类似。这样的话复杂度就是O(nlogn)。
写起来挺烦的，注意一下各种细节，码力极弱选手表示调了快一天……惨惨。
// luogu-judger-enable-o2
#include<iostream>
#include<cstdio>
#include<cmath>
#include<cstdlib>
#include<cstring>
#include<algorithm>
using namespace std;
int read()
{
int x=,f=;char c=getchar();
while (c<''||c>'') {if (c=='-') f=-;c=getchar();}
while (c>=''&&c<='') x=(x<<)+(x<<)+(c^),c=getchar();
return x*f;
}
#define N 1000010
#define ui unsigned int
#define inf 4294967295
#define lson (k<<1)
#define rson (k<<1|1)
#define getmid; int mid=tree[k].l+tree[k].r>>1;
int n;
struct data{int l,r,tag,size,sumzero,suminf;ui num;
}tree[N<<];
bool isleaf(int k){return tree[k].size==;}
void build(int k,int l,int r)
{
tree[k].l=l,tree[k].r=r,tree[k].size=r-l+;
tree[k].sumzero=tree[k].size,tree[k].suminf=;
if (isleaf(k)) return;
getmid;
build(lson,l,mid);
build(rson,mid+,r);
}
void up(int k)
{
tree[k].sumzero=tree[lson].sumzero+tree[rson].sumzero;
tree[k].suminf=tree[lson].suminf+tree[rson].suminf;
}
void update(int k,int tag)
{
if (tag>) tree[k].sumzero=tree[k].size,tree[k].suminf=;
else tree[k].sumzero=,tree[k].suminf=tree[k].size;
tree[k].tag=tag;
if (isleaf(k)) tree[k].num=tag>?:inf;
}
void down(int k)
{
if (tree[k].tag)
{
update(lson,tree[k].tag);
update(rson,tree[k].tag);
tree[k].tag=;
}
}
int find(int k,int x)
{
if (isleaf(k)) return k;
down(k);
getmid;
int ans;
if (x<=mid) ans=find(lson,x);
else ans=find(rson,x);
up(k);
return ans;
}
void modify(int k,int l,int r,int tag)
{
if (tree[k].l==l&&tree[k].r==r)
{
update(k,tag);
return;
}
down(k);
getmid;
if (r<=mid) modify(lson,l,r,tag);
else if (l>mid) modify(rson,l,r,tag);
else modify(lson,l,mid,tag),modify(rson,mid+,r,tag);
up(k);
}
int add(int k,int p,ui x)
{
if (isleaf(k))
{
int v=inf-tree[k].num<x;
tree[k].num+=x;
tree[k].sumzero=(tree[k].num==);
tree[k].suminf=(tree[k].num==inf);
return v;
}
down(k);
getmid;
int ans;
if (p<=mid) ans=add(lson,p,x);
else ans=add(rson,p,x);
up(k);
return ans;
}
int dec(int k,int p,ui x)
{
if (isleaf(k))
{
int v=tree[k].num<x;
tree[k].num-=x;
tree[k].sumzero=(tree[k].num==);
tree[k].suminf=(tree[k].num==inf);
return v;
}
down(k);
getmid;
int ans;
if (p<=mid) ans=dec(lson,p,x);
else ans=dec(rson,p,x);
up(k);
return ans;
}
void pushup(int k)
{
if (tree[k].suminf)
{
int t=k,cnt=;
while (tree[k].suminf-cnt==tree[k].r-tree[t].l+)
{
if (k&) cnt+=tree[k-].suminf;
k>>=;
}
k=rson;
while (!isleaf(k))
{
down(k);
if (tree[lson].suminf==tree[lson].size) k=rson;
else k=lson;
}
modify(,tree[t].l,tree[k].l-,);
}
add(,tree[k].l,);
}
void pushdown(int k)
{
if (tree[k].sumzero)
{
int t=k,cnt=;
while (tree[k].sumzero-cnt==tree[k].r-tree[t].l+)
{
if (k&) cnt+=tree[k-].sumzero;
k>>=;
}
k=rson;
while (!isleaf(k))
{
down(k);
if (tree[lson].sumzero==tree[lson].size) k=rson;
else k=lson;
}
modify(,tree[t].l,tree[k].l-,-);
}
dec(,tree[k].l,);
}
int query(int k,int p,int x)
{
if (isleaf(k)) return tree[k].num>>x&;
down(k);
getmid;
int ans;
if (p<=mid) ans=query(lson,p,x);
else ans=query(rson,p,x);
up(k);
return ans;
}
int main()
{
n=read();read(),read(),read();
build(,,n+);
for (int i=;i<=n;i++)
{
int op=read();
if (op==)
{
int x=read(),y=read();
if (x>)
{
ui v=x;
ui a=v<<(y&),b=(y&)?(v>>(-(y&))):;
if (a>) b+=add(,(y>>)+,a);
if (b>)
{
a=add(,(y>>)+,b);
if (a>) pushup(find(,(y>>)+));
}
}
else
{
ui v=abs(x);
ui a=v<<(y&),b=(y&)?(v>>(-(y&))):;
if (a>) b+=dec(,(y>>)+,a);
if (b>)
{
a=dec(,(y>>)+,b);
if (a>) pushdown(find(,(y>>)+));
}
}
}
else
{
int x=read();
printf("%d\n",query(,(x>>)+,x&));
}
}
return ;
}