代码

// duck test
// integer segtree2.cpp by wys @2017-06-25

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

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

int len;

struct node {
	node *l, *r;
	int val;
	
	void update() {
		val = l->val || r->val;
	}
};

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

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;
}

uint32_t A[MAXLEN], B[MAXLEN];

int min_pos, max_pos;

void add1(int pos) {
	while (A[pos >> 5] & (1u << (pos & 31))) {
		A[pos >> 5] -= 1u << (pos & 31);
		++pos;
	}
	if (B[pos >> 5] & (1u << (pos & 31))) {
		B[pos >> 5] -= 1u << (pos & 31);
	} else {
		A[pos >> 5] += 1u << (pos & 31);
	}
	if (pos > max_pos) max_pos = pos;
}

void sub1(int pos) {
	while (B[pos >> 5] & (1u << (pos & 31))) {
		B[pos >> 5] -= 1u << (pos & 31);
		++pos;
	}
	if (A[pos >> 5] & (1u << (pos & 31))) {
		A[pos >> 5] -= 1u << (pos & 31);
	} else {
		B[pos >> 5] += 1u << (pos & 31);
	}
	if (pos > max_pos) max_pos = pos;
}

void commit(node *root, int l, int r) {
	if (l == r) {
		root->val = A[l] || B[l];
	} else {
		int mid = (l + r) >> 1;
		commit(root->l, l, mid);
		commit(root->r, mid + 1, r);
		root->update();
	}
}

void commit(node *root, int a, int b, int l, int r) {
	if (l == a && r == b) {
		return commit(root, l, r), void();
	}
	int mid = (l + r) >> 1;
	if (b <= mid) {
		commit(root->l, a, b, l, mid);
	} else if (a > mid) {
		commit(root->r, a, b, mid + 1, r);
	} else {
		commit(root->l, a, mid, l, mid);
		commit(root->r, mid + 1, b, mid + 1, r);
	}
	root->update();
}

void _add(node *root, uint32_t a, int pos) {
	min_pos = max_pos = -1;
	for (int i = 0; i < 30; i++) {
		if ((a >> i) & 1) {
			add1(pos + i);
			if (min_pos == -1) min_pos = pos + i;
		}
	}
	if (min_pos == -1) return;
	commit(root, min_pos >> 5, max_pos >> 5, 0, len);
}

void _sub(node *root, uint32_t a, int pos) {
	min_pos = max_pos = -1;
	for (int i = 0; i < 30; i++) {
		if ((a >> i) & 1) {
			sub1(pos + i);
			if (min_pos == -1) min_pos = pos + i;
		}
	}
	if (min_pos == -1) return;
	commit(root, min_pos >> 5, max_pos >> 5, 0, len);
}

void add(node *root, int a1, int b) {
	if (a1 > 0) {
		_add(root, a1, b);
	} else {
		_sub(root, -a1, b);
	}
}

int query(node *root, int a, int b, int l, int r) {
	if (l == r) return root->val ? l : -1;
	if (root->val == 0) return -1;
	int mid = (l + r) >> 1;
	if (b <= mid) {
		return query(root->l, a, b, l, mid);
	} else if (a > mid) {
		return query(root->r, a, b, mid + 1, r);
	} else {
		int tmp = query(root->r, mid + 1, b, mid + 1, r);
		if (tmp != -1) return tmp;
		return query(root->l, a, mid, l, mid);
	}
}

int query(node *root, int k) {
	// kth = +-1 : 1 if [k [-1] ...] else 0
	// k > log(x) : 0
	// [+-1]     k   [+1] : 0
	// [+-1]     k   [-1] : 1
	
	int pos = k >> 5, off = k & 31;
	uint32_t tmp = A[pos] | B[pos];
	bool has1 = tmp & (1u << off);
	
	if (!has1) {
		bool has_higher_1 = (off < 32 && (tmp >> (off + 1))) || query(root, pos + 1, len, 0, len) >= 0;
		if (!has_higher_1) return 0;
	}
	
	if (off > 0 && (tmp & ((1u << off) - 1))) {
		for (int i = off - 1; i >= 0; i--) {
			if (tmp & (1u << i)) {
				return has1 ^ ((B[pos] >> i) & 1);
			}
		}
	}
	
	if (pos == 0) {
		return has1;
	}
	
	int p1 = query(root, 0, pos - 1, 0, len);
	if (p1 == -1) {
		return has1;
	}
	
	tmp = A[p1] | B[p1];
	for (int i = 31; i >= 0; i--) {
		if (tmp & (1u << i)) {
			return has1 ^ ((B[p1] >> i) & 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');
		}
	}
}

评测结果