代码

#include <set>
#include <cstdio>
#include <cctype>
#include <bitset>

const int ioSize = 1 << 21 | 1;
char iBuf[ioSize], *iS, *iE;
inline char getc() { return iS == iE ? iE = iBuf + fread(iS = iBuf, 1, ioSize, stdin), iS == iE ? EOF : *iS++ : *iS++; }
void readi(int &x)
{
	char c;
	bool isneg = false;
	for (c = getc(); !isdigit(c) && c != '-'; c = getc())
		;
	if (c == '-')
		isneg = true, c = getc();
	x = c ^ '0';
	for (c = getc(); isdigit(c); c = getc())
		(x *= 10) += c ^ '0';
	if (isneg)
		x = -x;
}

typedef unsigned long long ull;
const int base = 60, maxN = 1000005;
const ull MAX = (1ULL << 60) - 1;

ull A[maxN], B[maxN];
std::set<int> diffPos;

void add(int x)
{
	int block = x / base;
	x %= base;
	ull temp = 1ULL << x;
	while (temp)
	{
		ull old = A[block];
		A[block] += temp;
		temp = A[block] >> base;
		A[block] &= MAX;
		if (old == B[block] && A[block] != B[block])
			diffPos.insert(block);
		if (old != B[block] && A[block] == B[block])
			diffPos.erase(block);
		++block;
	}
}

void minus(int x)
{
	int block = x / base;
	x %= base;
	ull temp = 1ULL << x;
	while (temp)
	{
		ull old = B[block];
		B[block] += temp;
		temp = B[block] >> base;
		B[block] &= MAX;
		if (A[block] == old && A[block] != B[block])
			diffPos.insert(block);
		if (A[block] != old && A[block] == B[block])
			diffPos.erase(block);
		++block;
	}
}

int query(int x)
{
	int block = x / base;
	x %= base;
	int ans = (A[block] >> x & 1) ^ (B[block] >> x & 1);
	ull temp = A[block] ^ B[block];
	temp &= (1ULL << x) - 1;
	if (!temp)
	{
		auto it = diffPos.lower_bound(block);
		if (it != diffPos.begin())
		{
			--it;
			block = *it;
			temp = A[block] ^ B[block];
		}
	}
	if (temp)
	{
		int pos = 63 - __builtin_clzll(temp);
		if ((A[block] >> pos & 1) < (B[block] >> pos & 1))
			ans ^= 1;
	}
	return ans;
}

int main()
{
	int n, t1, t2, t3;

	readi(n), readi(t1), readi(t2), readi(t3);

	for (int o, a, b, k; n--;)
	{
		readi(o);
		if (o == 1)
		{
			readi(a), readi(b);
			if (a > 0)
			{
				for (int i = 0; i != 30; ++i)
					if (a >> i & 1)
						add(b + i);
			}
			else if (a < 0)
			{
				a = -a;
				for (int i = 0; i != 30; ++i)
					if (a >> i & 1)
						minus(b + i);
			}
		}
		else
		{
			readi(k);
			printf("%d\n", query(k));
		}
	}

	return 0;
}

评测结果