I wrote an evening commemorating a title \(NOI~d1t1\).
Title link: link
Title: Maintains a non-negative integer \x\ with a long length of tinea, supporting two operations:

1. Add or subtract \(a\cdot2^b\) to (x\), where \(ale10^9, ble30n).
2. Ask for the value of bit \(k\) where \(k\le30n).

Analysis:

• Let's start with an interesting question: Why is the range of \(b\) and \(k\) in \? How did this \(30\) come about?
• Does this inspire us to divide into n segments, each with 30 bits to maintain?
• And what does every \(30\) digit mean? Can I just use an \(int\) variable to store it?
• Take another look at the operation the title requires to support. Does the operation \(1\) equal adding or subtracting two adjacent paragraphs?
• The general idea is to maintain these \(n\) in a way that supports single-point modifications when viewed as \(2^{30}\).
• Unfortunately, it is a headache to move in and out.
• For example, if each of the following consecutive sections is \(1\), it would be equivalent to turning this section into \(0\) and then moving to the higher position.
• It can be equivalent to an interval assignment of \(0\), a single point \(+1\).
• What about abdication? Is the interval assignment \(1\), single point \(-1\)?
• Did you think of anything?
• I can segment tree! But I still wrote overnight.
• It is important to note that the segment tree is now maintained not by how many bits per line but by how many bits per \(30\), so our carry skips start at the place where the carry occurs, and each successive bit is a 1 segment.
• Another question follows. How do we know where the advance will end?
• There are segment trees, can't you just make a segment tree two?
• Simple to say, full of details.
• First, we need to know if each bit of an interval is all \(0\) or all \(1\), which can be achieved by maintaining intervals and intervals or by maintaining them.
• Due to the interval coverage operation, we also need to maintain a \(cov\) marker, but this is a minor problem. How to write the segment tree dichotomy is the key point.
• For example, now we want the first position not to be 2^{30}-1 after a \((pos)\).
• If we can enter the left interval query (that is, the left interval is not completely blocked by \(pos\), we will first query the left interval.
• If it exists, everything will be fine. If it doesn't exist, let's go into the right interval query.
• It looks like the complexity is quite wrong, because it is possible for each node to have its left and right intervals recursive?
• But it's okay, because this process is equivalent to asking for information on the interval \([pos,n]\), similar to a regular segment tree, where the complexity of a single operation is \(O(nlogn)\).
• Take note of the boundary conditions. If rounding occurs in paragraph \(n\), do we have paragraph \(n+1\) to receive this information?
• As I write below, the second branch of the segment tree returns to \(n\), for obvious reasons, let alone say.
• In another case, if each bit of each segment between \([pos,n]\), the second branch of the segment tree returns \(-1\).
• Special judgment of these two cases can be, the specific details or look at the code, there are notes anyway.
• Maybe \(140\) isn't that long? Welcome to your stepping on the bones.

Click to view the code

#include<iostream>
#include<cstdio>
using namespace std;
const int maxn=1e6+5,all=(1<<30)-1;
int i,m,n;
struct node
{
    int l,r,cov;///cov is an interval coverage marker (-1 means no marker)
    int sum[2];///sum[0] for interval and sum[1] for interval or
}f[4*maxn];
int read()
{
    int q=0,f=1;char ch=getchar();
    while(ch<'0'||ch>'9'){if(ch=='-') f=-1;ch=getchar();}
    while(ch>='0'&&ch<='9') q=10*q+ch-'0',ch=getchar();
    return q*f;
}
void pushup(int p)
{
    f[p].sum[0]=f[2*p].sum[0]&f[2*p+1].sum[0];
    f[p].sum[1]=f[2*p].sum[1]|f[2*p+1].sum[1];
}
void pushdown(int p)
{
    if(f[p].cov==-1) return ;
    f[2*p].cov=f[2*p].sum[0]=f[2*p].sum[1]=f[p].cov;
    f[2*p+1].cov=f[2*p+1].sum[0]=f[2*p+1].sum[1]=f[p].cov;
    f[p].cov=-1;
}
void build(int p,int l,int r)
{
    f[p].l=l,f[p].r=r,f[p].cov=-1;
    if(l==r) return ;
    int mid=(l+r)/2;
    build(2*p,l,mid);
    build(2*p+1,mid+1,r);
    pushup(p);
}
void cover(int p,int l,int r,int val)
{///Interval Coverage
    if(l<=f[p].l&&f[p].r<=r)
    {
        f[p].cov=f[p].sum[0]=f[p].sum[1]=val;
        return ;
    }
    if(l>f[p].r||r<f[p].l) return ;
    pushdown(p);
    cover(2*p,l,r,val);
    cover(2*p+1,l,r,val);
    pushup(p);
}
void modify(int p,int pos,int val)
{///dot plus
    if(f[p].l==f[p].r)
    {
        f[p].sum[0]+=val,f[p].sum[1]+=val;
        return ;
    }
    pushdown(p);
    int mid=(f[p].l+f[p].r)/2;
    if(pos<=mid) modify(2*p,pos,val);
    else modify(2*p+1,pos,val);
    pushup(p);
}
int query(int p,int pos)
{///Single point query
    if(f[p].l==f[p].r) return f[p].sum[0];
    pushdown(p);
    int mid=(f[p].l+f[p].r)/2;
    if(pos<=mid) return query(2*p,pos);
    else return query(2*p+1,pos);
}
int find_nxt(int p,int pos,int opt)
{///Segment Tree Binary, opt=0/1 means to look for the first non-all/0 position after POS (including pos), and -1 means it does not exist
    if(opt==0&&f[p].sum[0]==all) return -1;
    if(opt==1&&f[p].sum[1]==0) return -1;
    if(f[p].l==f[p].r) return f[p].l;
    pushdown(p);
    int mid=(f[p].l+f[p].r)/2;
    if(pos>=mid+1) return find_nxt(2*p+1,pos,opt);///Defined behind pos
    int res=find_nxt(2*p,pos,opt);///Advanced left subtree search
    if(res!=-1) return res;///Return directly if left subtree exists
    return find_nxt(2*p+1,pos,opt);///Otherwise go into the right subtree to find
}
void add(int pos,int val)
{///In pos first position+val
    if(val==0) return ;
    int cur=query(1,pos);///The value in this bit before the operation is cur
    if(cur+val<=all) modify(1,pos,val);///No carry
    else
    {
        modify(1,pos,val-(1<<30));///Modify the current bit value first
        int nxt=find_nxt(1,pos+1,0);
        if(nxt>=pos+2) cover(1,pos+1,nxt-1,0);///Intermediate progression equals interval coverage
        modify(1,nxt,1);///last one digit 1
    }
}
void dec(int pos,int val)
{
    if(val==0) return ;
    int cur=query(1,pos);
    if(cur>=val) modify(1,pos,-val);
    else
    {
        modify(1,pos,(1<<30)-val);
        int nxt=find_nxt(1,pos+1,1);
        if(nxt>=pos+2) cover(1,pos+1,nxt-1,all);
        modify(1,nxt,-1);
    }
}
int main()
{
    n=read(),read(),read(),read();
    build(1,0,n);
    for(i=1;i<=n;i++)
    {
        int opt=read();
        if(opt==1)
        {
            int a=read(),b=read(),pos=b/30,num=b%30;
            if(a>0)
            {
                add(pos,a<<num&all);///impact on pos position
                add(pos+1,a>>(30-num));///effect on pos+1 bit
            }
            else
            {
                a*=-1;
                dec(pos,a<<num&all);///impact on pos position
                dec(pos+1,a>>(30-num));///effect on pos+1 bit
            }
        }
        else
        {
            int k=read(),pos=k/30,num=k%30;
            printf("%d\n",query(1,pos)>>num&1);
        }
    }
    return 0;
}