代码

// luogu-judger-enable-o2
#include<iostream>
#include<cstring>
#include<cstdlib>
#include<cstdio>
#include<algorithm>
#define ll long long
using namespace std;
const int maxn=1000010, inf=(1<<30)-1;
struct sgt{int tag, sum, st[2];}tree[maxn<<2];
int n, ans, mx, x, ty, a, b;
char buf[80000010],*ptr=buf-1;
 
template<typename T>
inline void read(T &k)
{
    char c=*++ptr; int f=1; k=0;
    while(c<'0' || c>'9') c=='-'&&(f=-1), c=*++ptr;
    while(c<='9' && c>='0') k=k*10+c-'0', c=*++ptr;
    k*=f;   
}
 
inline void changeone(int x, int delta)
{
    tree[x].sum=tree[x].tag=delta;
    tree[x].st[0]=(tree[x].sum==0);
    tree[x].st[1]=(tree[x].sum==inf);
}
 
inline void addone(int x, int delta)
{
    tree[x].sum+=delta;
    tree[x].st[0]=(tree[x].sum==0);
    tree[x].st[1]=(tree[x].sum==inf);
}
 
inline void up(int x)
{
    tree[x].st[0]=tree[x<<1].st[0]&tree[x<<1|1].st[0];
    tree[x].st[1]=tree[x<<1].st[1]&tree[x<<1|1].st[1];
}
 
inline void down(int x)
{
    if(tree[x].tag!=-1)
    {
        changeone(x<<1, tree[x].tag);
        changeone(x<<1|1, tree[x].tag);
        tree[x].tag=-1;
    }
}
 
void change(int x, int l, int r, int cl, int cr, int delta)
{
    if(cl<=l && r<=cr){changeone(x, delta); return;}
    int mid=(l+r)>>1; down(x);
    if(cl<=mid) change(x<<1, l, mid, cl, cr, delta);
    if(cr>mid) change(x<<1|1, mid+1, r, cl, cr, delta);
    up(x);
}
 
void update(int x, int l, int r, int cx, int delta)
{
    if(l==r){addone(x, delta); return;}
    int mid=(l+r)>>1; down(x);
    if(cx<=mid) update(x<<1, l, mid, cx, delta);
    else update(x<<1|1, mid+1, r, cx, delta);
    up(x);
}
 
int query(int x, int l, int r, int cx)
{
    if(l==r) return tree[x].sum;
    int mid=(l+r)>>1; down(x);
    if(cx<=mid) return query(x<<1, l, mid, cx);
    else return query(x<<1|1, mid+1, r, cx);
}
 
int queryr(int x, int l, int r, int cx, int k)
{
    if(l==r) return ans=tree[x].st[k^1], l;
    int mid=(l+r)>>1; down(x);
    if(cx>mid) return queryr(x<<1|1, mid+1, r, cx, k);
    else
    {
        int pos=queryr(x<<1, l, mid, cx, k);
        if(!ans) return pos;
        if(tree[x<<1|1].st[k^1]) return r;
        return queryr(x<<1|1, mid+1, r, cx, k);
    }
}
 
inline void add(int pos, int delta)
{
    int x=query(1, 1, mx, pos);
    if(x+delta<=inf) update(1, 1, mx, pos, delta);
    else
    {
        update(1, 1, mx, pos, delta-inf-1);
        ans=0; int nxt=queryr(1, 1, mx, pos+1, 0);
        update(1, 1, mx, nxt, 1);
        if(nxt!=pos+1) change(1, 1, mx, pos+1, nxt-1, 0);
    }
}
 
inline void del(int pos, int delta)
{
    int x=query(1, 1, mx, pos);
    if(x-delta>=0) update(1, 1, mx, pos, -delta);
    else
    {
        update(1, 1, mx, pos, inf+1-delta);
        ans=0; int nxt=queryr(1, 1, mx, pos+1, 1);
        update(1, 1, mx, nxt, -1);
        if(nxt!=pos+1) change(1, 1, mx, pos+1, nxt-1, inf);
    }
}
 
void build(int x, int l, int r)
{
    tree[x].st[0]=1; tree[x].tag=-1;
    if(l==r) return;
    int mid=(l+r)>>1;
    build(x<<1, l, mid); build(x<<1|1, mid+1, r);
}
  
int main()
{
    fread(buf, 1,sizeof(buf), stdin);
    read(n); read(x); read(x); read(x); mx=n+233;
    build(1, 1, mx);
    for(int i=1;i<=n;i++)
    {
        read(ty);
        if(ty==1)
        {
            read(a); read(b); int p=b/30;
            if(a>0)
            {
                add(p+1, (1ll*a<<(b-p*30))&inf);
                add(p+2, a>>(30-(b-p*30)));
            }
            else
            {
                a=-a;
                del(p+1, (1ll*a<<(b-p*30))&inf);
                del(p+2, a>>(30-(b-p*30)));
            }
        }
        else read(x), printf("%d\n", (query(1, 1, mx, x/30+1)>>(x%30))&1);
    }
}

评测结果