记录编号	439387	评测结果	AWEWWTEEEEETEETEEEETTEEEE
题目名称	[NOI 2017]整数	最终得分	4
用户昵称	albertxwz	是否通过	未通过
代码语言	C++	运行时间	11.296 s
提交时间	2017-08-20 10:04:19	内存使用	46.07 MiB

#include <cstdio>
#include <cstring>
#include <algorithm>

using namespace std;

const int maxn = 1000005;
const int base = 32;
long long number[maxn];
int mark[maxn*5];
int lazytag[maxn*5];
int n;

void pushdown(int o)
{
	int lc = o<<1, rc = lc+1;
	if (lazytag[o] != 0)
	{
		lazytag[lc] = lazytag[rc] = lazytag[o];
		mark[lc] = mark[rc] = mark[o];
		lazytag[o] = 0;
	}
}

void maintain(int o, int L, int R)
{
	if (L == R)
	{
		if (lazytag[o] != 0)
		{
			number[L] = lazytag[o]==1?(1ll<<base)-1:0;
			lazytag[o] = 0;
		}
		if (number[L] == (1ll<<base)-1) mark[o] = 1;
		else if (number[L] == 0) mark[o] = 0;
			else mark[o] = -1;
	}
	else
	{
		int lc = o<<1, rc = lc+1;
		if (lazytag[o] == 1) mark[o] = 1;
		else if (lazytag[o] == -1) mark[o] = 0;
			else if (mark[lc] == mark[rc]) mark[o] = mark[lc];
				else mark[o] = -1;
	}
}

void modifypoint(int o, int L, int R, int p, long long delta)
{
	if (L == R)
	{
		if (lazytag[o] == 1) number[p] = (1ll << base)-1;
		else if (lazytag[o] == -1) number[p] = 0;
		number[p] += delta;
		number[p] &= (1ll << base)-1;
		lazytag[o] = 0;
	}
	else
	{
		pushdown(o);
		int mid = (L+R) >> 1;
		int lc = o << 1, rc = lc+1;
		if (p <= mid) modifypoint(lc, L, mid, p, delta);
		if (p > mid) modifypoint(rc, mid+1, R, p, delta);
	}
	maintain(o, L, R);
}

void modifyrange(int o, int L, int R, int y1, int y2, int num)
{
	if (y1 <= L && R <= y2)
	{
		lazytag[o] = num?1:-1;
		if (L == R) number[L] = num?(1ll<<base)-1:0;	
	}
	else
	{
		pushdown(o);
		int mid = (L+R) >> 1;
		int lc = o << 1, rc = lc + 1;
		if (y1 <= mid) modifyrange(lc, L, mid, y1, y2, num);
		if (mid+1 <= y2) modifyrange(rc, mid+1, R, y1, y2, num);
	}
	maintain(o, L, R);
}

int query(int o, int L, int R, int y1, int y2, int find_obj)
{
	if (mark[o] == find_obj) return max(L, y1);
	else if (mark[o] != -1) return R+1;
	int mid = (L+R) >> 1;
	int lc = o << 1, rc = lc+1;
	int res;
	if (y1 <= L && R <= y2)
	{
		if (L == R) return L;
		if (mark[lc] == -1 || (find_obj == mark[lc]))
			return query(lc, L, mid, y1, y2, find_obj);
		else return query(rc, mid+1, R, y1, y2, find_obj);
	}
	res = R+1;
	if (y1 <= mid) res = min(res, query(lc, L, mid, y1, y2, find_obj));
	if (res <= mid && res >= y1) return res;
	if (mid+1 <= y2) return query(rc, mid+1, R, y1, y2, find_obj);
	return R+1;
}

long long querynum(int o, int L, int R, int p)
{
	if (mark[o] != -1) return mark[o] == 1 ? (1ll<<base)-1 : 0;
	if (L == R) return number[p];
	int mid = (L+R) >> 1;
	int lc = o<<1, rc = lc+1;
	if (p <= mid) return querynum(lc, L, mid, p);
	return querynum(rc, mid+1, R, p);
}

void add(long long num, int loc, int find_obj)
{
	long long num0 = querynum(1, 1, n, loc);
	if (((find_obj == 0 && num0 + num >= (1ll << base)) || 
		(find_obj == 1 && num0 < num)))
	{
		int locx = query(1, 1, n, loc+1, n, find_obj);
		if (locx <= n) modifypoint(1, 1, n, locx, find_obj?-1:1);
		if (loc+1 <= locx-1) modifyrange(1, 1, n, loc+1, min(locx-1, n), find_obj);
	}
	modifypoint(1, 1, n, loc, find_obj?-num:num);
}



int main()
{
	freopen("2017integer.in", "r", stdin);
	freopen("2017integer.out", "w", stdout);
	int t1, t2, t3;
	scanf("%d%d%d%d", &n, &t1, &t2, &t3);
	memset(number, 0, sizeof(number));
	memset(mark, 0, sizeof(mark));
	memset(lazytag, 0, sizeof(lazytag));
	printf("\n\n");
	for (int i = 0; i < n; ++i)
	{
		int cmd;
		scanf("%d", &cmd);
		if (cmd == 1)
		{
			int a, b;
			bool find_obj = 0;
			scanf("%d%d", &a, &b);
			if (a < 0)
			{
				find_obj = 1;
				a = -a;
			}
			int st = b/base+1;
			int k = b % base;
			long long tmp = (long long)a << k;
			for (int j = 0; tmp; ++j, tmp >>= base)
			{
				long long part = tmp & ((1ll << base)-1);
				add(part, st+j, find_obj);
			}
		}
		else
		{
			int k;
			scanf("%d", &k);
			long long num = querynum(1, 1, n, k/base+1);
			printf("%lld\n", (num >> (k % base)) & 1);
		}
	}
	return 0;
}