代码

#include<bits/stdc++.h>
#define Rint register int
using namespace std;
const int len = 1e6, N = (len + 10) << 2, inf = (1 << 30) - 1;
int sor[N], sand[N], tag[N];
inline void pushup(int x){
	sor[x] = sor[x << 1] | sor[x << 1 | 1];
	sand[x] = sand[x << 1] & sand[x << 1 | 1];
}
inline void pushdown(int x){
	if(tag[x] != -1){
		sor[x << 1] = sand[x << 1] = tag[x << 1] = sor[x << 1 | 1] = sand[x << 1 | 1] = tag[x << 1 | 1] = tag[x];
		tag[x] = -1;
	}
}
inline void change(int x, int L, int R, int pos, int val){ // dan dian xiu gai
	if(L == R){
		sor[x] += val; sand[x] += val;
		return;
	}
	pushdown(x);
	int mid = L + R >> 1;
	if(pos <= mid) change(x << 1, L, mid, pos, val);
	else change(x << 1 | 1, mid + 1, R, pos, val);
	pushup(x);
}
inline void modify(int x, int L, int R, int l, int r, int val){ // qu jian fu zhi
	if(l <= L && R <= r){
		sor[x] = sand[x] = tag[x] = val;
		return;
	}
	int mid = L + R >> 1;
	pushdown(x);
	if(l <= mid) modify(x << 1, L, mid, l, r, val);
	if(mid < r) modify(x << 1 | 1, mid + 1, R, l, r, val);
	pushup(x);
}
inline int find0(int x, int L, int R, int pos){ // find0
	if(sand[x] == inf) return -1;
	if(L == R) return L;
	pushdown(x);
	int mid = L + R >> 1;
	if(pos <= mid){
		int tmp = find0(x << 1, L, mid, pos);
		if(tmp == -1) return find0(x << 1 | 1, mid + 1, R, pos);
		else return tmp;
	} else return find0(x << 1 | 1, mid + 1, R, pos);
}
inline int find1(int x, int L, int R, int pos){ // find1
	if(sor[x] == 0) return -1;
	if(L == R) return L;
	pushdown(x);
	int mid = L + R >> 1;
	if(pos <= mid){
		int tmp = find1(x << 1, L, mid, pos);
		if(tmp == -1) return find1(x << 1 | 1, mid + 1, R, pos);
		else return tmp;
	} else return find1(x << 1 | 1, mid + 1, R, pos);
}
inline int query(int x, int L, int R, int pos){ // dan dian cha xun
	if(L == R) return sor[x];
	int mid = L + R >> 1;
	pushdown(x);
	if(pos <= mid) return query(x << 1, L, mid, pos);
	else return query(x << 1 | 1, mid + 1, R, pos);
}
inline void add(int pos, int val){
	if(!val) return;
	int tmp = query(1, 0, len, pos);
//	printf("tmp = %d\n", tmp);
	if(tmp + val <= inf){change(1, 0, len, pos, val); return;}
	else {
		change(1, 0, len, pos, val - inf - 1);
		int p = find0(1, 0, len, pos + 1);
		if(p != pos + 1) modify(1, 0, len, pos + 1, p - 1, 0);
		change(1, 0, len, p, 1);
	}
}
inline void del(int pos, int val){
	if(!val) return;
	int tmp = query(1, 0, len, pos);
//	printf("tmp = %d\n", tmp);
	if(tmp - val >= 0){change(1, 0, len, pos, -val); return;}
	else {
		change(1, 0, len, pos, inf + 1 - val);
		int p = find1(1, 0, len, pos + 1);
		if(p != pos + 1) modify(1, 0, len, pos + 1, p - 1, inf);
		change(1, 0, len, p, -1);
	}
}
int n, t1, t2, t3, opt, a, b;
int main(){
	scanf("%d%d%d%d", &n, &t1, &t2, &t3);
	memset(tag, -1, sizeof tag);
	while(n --){
		scanf("%d%d", &opt, &a);
		if(opt == 1){
			scanf("%d", &b);
			int pos = b / 30;
			if(a > 0){
				add(pos, (a << (b - pos * 30)) & inf);
				add(pos + 1, a >> ((pos + 1) * 30 - b));
			} else {
				a = -a;
				del(pos, (a << (b - pos * 30)) & inf);
				del(pos + 1, a >> ((pos + 1) * 30 - b));
			}
		} else {
			int pos = a / 30;
			putchar((query(1, 0, len, pos) & (1 << (a - pos * 30))) ? '1' : '0');
			putchar('\n');
		}
	}
}

评测结果