代码

// integer segtree1.cpp by wys @2017-06-24

#include <stdio.h>
#include <stdint.h>

const int MAXN = 1000005;
const int MAXM = MAXN * 30;
const int MAXLEN = MAXM / 32;

struct node {
	node *l, *r;
	uint32_t val;
	int tag;
	
	void down() {
		if (tag != 233) {
			l->val = l->tag = tag;
			r->val = r->tag = tag;
		}
	}
	
	void update() {
		if (l->tag == r->tag) {
			tag = l->tag;
		} else {
			tag = 233;
		}
	}
};

inline int get_tag(uint32_t x) {
	return x == 0 ? 0 : x == -1 ? -1 : 233;
}

node _nodes[MAXLEN * 2], *_next_node = _nodes;

int len;

node * build(int l, int r) {
	node *ret = _next_node++;
	
	if (l < r) {
		int mid = (l + r) >> 1;
		ret->l = build(l, mid);
		ret->r = build(mid + 1, r);
	}
	
	return ret;
}

bool add1(node *root, int l, int r) {
	if (l == r) {
		bool ret = (++root->val) == 0;
		root->tag = get_tag(root->val);
		return ret;
	}
	if (root->tag == -1) {
		root->tag = 0;
		return 1;
	}
	root->down();
	int mid = (l + r) >> 1;
	add1(root->l, l, mid) && add1(root->r, mid + 1, r);
	root->update();
	return 0;
}

bool sub1(node *root, int l, int r) {
	if (l == r) {
		bool ret = (--root->val) == -1;
		root->tag = get_tag(root->val);
		return ret;
	}
	if (root->tag == 0) {
		root->tag = -1;
		return 1;
	}
	root->down();
	int mid = (l + r) >> 1;
	sub1(root->l, l, mid) && sub1(root->r, mid + 1, r);
	root->update();
	return 0;
}

bool add(node *root, uint32_t a, int pos, int l, int r) {
	if (l == r) {
		bool ret = (root->val += a) < a;
		root->tag = get_tag(root->val);
		return ret;
	}
	root->down();
	int mid = (l + r) >> 1;
	bool ret;
	if (pos <= mid) {
		ret = add(root->l, a, pos, l, mid) && add1(root->r, mid + 1, r);
	} else {
		ret = add(root->r, a, pos, mid + 1, r);
	}
	root->update();
	return ret;
}

bool sub(node *root, uint32_t a, int pos, int l, int r) {
	if (l == r) {
		bool ret = root->val < a;
		root->val -= a;
		root->tag = get_tag(root->val);
		return ret;
	}
	root->down();
	int mid = (l + r) >> 1;
	bool ret;
	if (pos <= mid) {
		ret = sub(root->l, a, pos, l, mid) && sub1(root->r, mid + 1, r);
	} else {
		ret = sub(root->r, a, pos, mid + 1, r);
	}
	root->update();
	return ret;
}

void _add(node *root, uint32_t a, int pos) {
	add(root, a, pos, 0, len);
}

void _sub(node *root, uint32_t a, int pos) {
	sub(root, a, pos, 0, len);
}

void add(node *root, int _a, int b) {
	if (_a == 0) return;
	bool neg = _a < 0;
	uint32_t a = neg ? -_a : _a;
	
	int pos = b >> 5;
	int off = b & 31;
	int len = 32 - off;
	
	uint32_t part1 = len >= 30 ? a : (a & ((1u << len) - 1));
	uint32_t part2 = len >= 30 ? 0 : (a >> len);
	
	if (part1) (neg ? _sub : _add)(root, part1 << off, pos);
	if (part2) (neg ? _sub : _add)(root, part2, pos + 1);
}

uint32_t query(node *root, int pos, int l, int r) {
	if (l == r) {
		return root->val;
	}
	root->down();
	int mid = (l + r) >> 1;
	if (pos <= mid) {
		return query(root->l, pos, l, mid);
	} else {
		return query(root->r, pos, mid + 1, r);
	}
}

int query(node *root, int k) {
	return (query(root, k >> 5, 0, len) >> (k & 31)) & 1;
}

int main() {
	
	int n, t1, t2, t3;
	scanf("%d%d%d%d", &n, &t1, &t2, &t3);
	
	int m;
	if (t2 == 1) {
		m = 30;
	} else if (t2 == 2) {
		m = 100;
	} else if (t2 == 3) {
		m = n;
	} else {
		m = 30 * n;
	}
	m += 100;
	
	len = m / 32 + 1;
	
	node *root = build(0, len);
	
	for (int i = 0; i < n; i++) {
		int op, a, b, k;
		scanf("%d", &op);
		
		if (op == 1) {
			scanf("%d%d", &a, &b);
			add(root, a, b);
		} else {
			scanf("%d", &k);
			putchar("01"[query(root, k)]);
			putchar('\n');
		}
	}
}

评测结果