代码

#include <bits/stdc++.h>
#define Pb push_back
using namespace std;
typedef long long ll;
const int MAXN = 1e6 + 17;
const int Mx = 1 << 30;

inline int R()
{
    int rt = 0; char ch = getchar(); bool isn = false;
    for ( ; ch < '0' || ch > '9'; ch = getchar() ) isn = ch == '-' ? true : isn;
    for ( ; ch >= '0' && ch <= '9'; ch = getchar() ) rt = rt * 10 + ch - '0';
    return isn ? -rt : rt;
}

int n;

struct Node
{
	int l, r;
	int s[2];
	ll val[2];
	int la;
}t[MAXN << 1];
int nu = 1;

inline void Maintain ( int nf )
{
	t[nf].val[0] = t[t[nf].s[0]].val[0] | t[t[nf].s[1]].val[0];
	t[nf].val[1] = t[t[nf].s[0]].val[1] & t[t[nf].s[1]].val[1];
}

inline void Upd ( int nf )
{
	if ( t[nf].la == 1 )
	{
		t[t[nf].s[0]].la = 1, t[t[nf].s[1]].la = 1;
		t[t[nf].s[0]].val[0] = Mx - 1, t[t[nf].s[0]].val[1] = Mx - 1;
		t[t[nf].s[1]].val[0] = Mx - 1, t[t[nf].s[1]].val[1] = Mx - 1;
		t[nf].la = 0;
	}
	if ( t[nf].la == -1 )
	{
		t[t[nf].s[0]].la = -1, t[t[nf].s[1]].la = -1;
		t[t[nf].s[0]].val[0] = 0, t[t[nf].s[0]].val[1] = 0;
		t[t[nf].s[1]].val[0] = 0, t[t[nf].s[1]].val[1] = 0;
		t[nf].la = 0;
	}
}

void Build ( int nl, int nr, int na )
{
	t[na].l = nl, t[na].r = nr;
	if ( nl == nr )
		return;
	int mid = nl + nr >> 1;
	t[na].s[0] = ++nu;
	Build ( nl, mid, nu );
	t[na].s[1] = ++nu;
	Build ( mid + 1, nr, nu );
}

int Query ( int np, int nf )
{
	if ( t[nf].l == t[nf].r )
		return t[nf].val[0];
	Upd ( nf );
	return Query ( np, t[t[nf].s[0]].r >= np ? t[nf].s[0] : t[nf].s[1] );
}

void Mod ( int np, int na, int nf )
{
	if ( t[nf].l == t[nf].r )
	{
		t[nf].val[0] += na, t[nf].val[1] += na;
		return;
	}
	Upd ( nf );
	Mod ( np, na, t[t[nf].s[0]].r >= np ? t[nf].s[0] : t[nf].s[1] );
	Maintain ( nf );
}

void Finde ( int nl, int nr, int &ep, int nf )
{
	if ( t[nf].l > nr || t[nf].r < nl )
		return;
	if ( t[nf].val[1] == Mx - 1 )
		return;
	if ( t[nf].l == t[nf].r )
	{
		ep = t[nf].l, ++t[nf].val[0], ++t[nf].val[1];
		return;
	}
	Upd ( nf );
	if ( t[nf].l >= nl && t[nf].r <= nr )
	{
		if ( t[t[nf].s[0]].val[1] != Mx - 1 )
			Finde ( nl, nr, ep, t[nf].s[0] );
		else
			Finde ( nl, nr, ep, t[nf].s[1] );
		Maintain ( nf );
		return;
	}
	Finde ( nl, nr, ep, t[nf].s[0] );
	if ( ep )
	{
		Maintain ( nf );
		return;
	}
	Finde ( nl, nr, ep, t[nf].s[1] );
	Maintain ( nf );
}

void Findf ( int nl, int nr, int &ep, int nf )
{
	if ( t[nf].l > nr || t[nf].r < nl )
		return;
	if ( !t[nf].val[0] )
		return;
	if ( t[nf].l == t[nf].r )
	{
		ep = t[nf].l, --t[nf].val[0], --t[nf].val[1];
		return;
	}
	Upd ( nf );
	if ( t[nf].l >= nl && t[nf].r <= nr )
	{
		if ( t[t[nf].s[0]].val[0] )
			Findf ( nl, nr, ep, t[nf].s[0] );
		else
			Findf ( nl, nr, ep, t[nf].s[1] );
		Maintain ( nf );
		return;
	}
	Findf ( nl, nr, ep, t[nf].s[0] );
	if ( ep )
	{
		Maintain ( nf );
		return;
	}
	Findf ( nl, nr, ep, t[nf].s[1] );
	Maintain ( nf );
}

void Clr ( int nl, int nr, int nf )
{
	if ( t[nf].l > nr || t[nf].r < nl )
		return;
	if ( t[nf].l >= nl && t[nf].r <= nr )
	{
		t[nf].val[0] = 0, t[nf].val[1] = 0, t[nf].la = -1;
		return;
	}
	Upd ( nf );
	Clr ( nl, nr, t[nf].s[0] ), Clr ( nl, nr, t[nf].s[1] );
	Maintain ( nf );
}

void Add ( int np, int na )
{
	if ( !na )
		return;
	int ov = Query ( np, 1 );
	if ( ov + na < Mx )
		Mod ( np, na, 1 );
	else
	{
		Mod ( np, ( ov + na ) % Mx - ov, 1 );
		int ep = 0;
		Finde ( np + 1, t[1].r, ep, 1 );
		if ( np + 1 <= ep - 1 )
			Clr ( np + 1, ep - 1, 1 );
	}
}

void Fil ( int nl, int nr, int nf )
{
	if ( t[nf].l > nr || t[nf].r < nl )
		return;
	if ( t[nf].l >= nl && t[nf].r <= nr )
	{
		t[nf].val[0] = Mx - 1, t[nf].val[1] = Mx - 1, t[nf].la = 1;
		return;
	}
	Upd ( nf );
	Fil ( nl, nr, t[nf].s[0] ), Fil ( nl, nr, t[nf].s[1] );
	Maintain ( nf );
}

void Min ( int np, int na )
{
	if ( !na )
		return;
	int ov = Query ( np, 1 );
	if ( ov - na >= 0 )
		Mod ( np, -na, 1 );
	else
	{
		Mod ( np, Mx + ( ov - na ) - ov, 1 );
		int ep = 0;
		Findf ( np + 1, t[1].r, ep, 1 );
		if ( np + 1 <= ep - 1 )
			Fil ( np + 1, ep - 1, 1 );
	}
}

int main()
{
	n = R();
	R(), R(), R();
	Build ( 0, n + 10, 1 );
	for ( int i = 1; i <= n; ++i )
	{
		if ( R() == 1 )
		{
			int a = R(), b = R();
			if ( a > 0 )
			{
				int pos = b / 30, rem = b % 30;
				Add ( pos, ( a & ( ( 1 << ( 30 - rem ) ) - 1 ) ) << rem );
				Add ( pos + 1, a >> ( 30 - rem ) );
			}
			else
			{
				a = -a;
				int pos = b / 30, rem = b % 30;
				Min ( pos, ( a & ( ( 1 << ( 30 - rem ) ) - 1 ) ) << rem );
				Min ( pos + 1, a >> ( 30 - rem ) );
			}
		}
		else
		{
			int k = R();
			int pos = k / 30, rem = k % 30;
			puts ( ( Query ( pos, 1 ) & ( 1 << rem ) ) ? "1" : "0" );
		}
	}
	return 0;
}

评测结果