题解

题目分析

这是一道基于线段树和位运算的题目，需要维护一个支持大数运算的数据结构。

解题思路

1. 问题建模

• 维护一个长度为 $n$ 的数组，支持单点加法和区间查询
• 使用模运算 $mod = 2^{30}$ 处理溢出
• 需要支持进位和借位操作

2. 线段树设计

• 每个节点维护：值 $val$、是否有小值 $small$、是否有大值 $big$
• 使用懒标记 $lazy$ 支持区间更新
• 特殊处理：当值达到 $mod-1$ 时标记为 $small$，当值大于 $0$ 时标记为 $big$

3. 关键操作

• 单点加法：add(i, x) 在位置 $i$ 加上 $x$
• 进位处理：当加法导致溢出时，寻找下一个可进位位置
• 借位处理：当减法导致下溢时，寻找下一个可借位位置
• 区间查询：query(i) 查询位置 $i$ 的值

4. 位运算优化

• 将大数按 $B=30$ 位分组处理
• 使用位运算快速计算进位和借位
• 通过哈希表快速查找可操作位置

5. 算法流程

1. 将输入的大数按位分解
2. 对每个位组进行加法操作
3. 处理进位和借位
4. 查询指定位置的值

时间复杂度

• 单次操作：$O(\log n)$
• 总体复杂度：$O(n \log n)$

#include <bits/stdc++.h> 
using namespace std; 
#define taskname "default"

const int mod = 1 << 30, B = 30;

struct Segment_Tree {
	int tree_size(int m) {return 1 << (__lg(m - 1) + 2);}
	
	struct tree_node {
		int val; bool small, big;
		tree_node() : val(0), small(1), big(0) {}
		int update(int delta) {
			int res = 0;
			// cout << "Previous : " << val << ' ' << small << ' ' << big << endl;
			if (delta < 0) {
				if (val < -delta) res = -1;
				val = (val + mod + delta) % mod;
			}
			else {
				if (val + delta >= mod) res = 1;
				val = (val + delta) % mod;
			}
			small = (val < mod - 1); big = (val > 0);
			// cout << "Now : " << val << ' ' << small << ' ' << big << endl;
			return res;
		}
	};
	
	tree_node merge(const tree_node& L, const tree_node& R) {
		tree_node res;
		res.small = L.small | R.small;
		res.big = L.big | R.big;
		return res;
	}
	
	int n;
	vector<tree_node> node; vector<int> lazy;
	void init(int m) {
		n = m;
		node.assign(tree_size(n + 1) + 8, tree_node());
		lazy.assign(tree_size(n + 1) + 8, -1);
	}
	
	void modify(int id, int x) {
		node[id].val = x;
		node[id].small = (node[id].val < mod - 1); node[id].big = (node[id].val > 0);
		lazy[id] = x;
	}
	
	void push(int id) {
		if (lazy[id] < 0) return;
		modify(id * 2, lazy[id]); modify(id * 2 + 1, lazy[id]);
		lazy[id] = -1;
	}
	
	int point_update(int id, int l, int r, int i, int delta) {
		if (l == r) return node[id].update(delta);
		int res;
		int mid = (l + r) / 2;
		push(id);
		if (i <= mid) res = point_update(id * 2, l, mid, i, delta);
		else res = point_update(id * 2 + 1, mid + 1, r, i, delta);
		node[id] = merge(node[id * 2], node[id * 2 + 1]);
		return res;
	}
	
	void range_update(int id, int l, int r, int u, int v, int x) {
		if (r < u || v < l) return;
		if (u <= l && r <= v) {
			// cout << "Setting " << id << ' ' << l << ' ' << r << " to " << x << endl;
			modify(id, x); 
			// cout << node[id].val << ' ' << node[id].small << ' ' << node[id].big << endl;
			return;
		}
		int mid = (l + r) / 2;
		push(id);
		range_update(id * 2, l, mid, u, v, x);
		range_update(id * 2 + 1, mid + 1, r, u, v, x);
		node[id] = merge(node[id * 2], node[id * 2 + 1]);
	}
	
	int search_small_subtree(int id, int l, int r) {
		if (l == r) return l;
		int mid = (l + r) / 2;
		push(id);
		if (node[id * 2].small) return search_small_subtree(id * 2, l, mid);
		else return search_small_subtree(id * 2 + 1, mid + 1, r);
	}
	
	int search_big_subtree(int id, int l, int r) {
		if (l == r) return l;
		int mid = (l + r) / 2;
		push(id);
		if (node[id * 2].big) return search_big_subtree(id * 2, l, mid);
		else return search_big_subtree(id * 2 + 1, mid + 1, r);
	}
	
	int search_small(int id, int l, int r, int u, int v) {
		if (r < u || v < l) return -1;
		if (u <= l && r <= v) {
			if (node[id].small) return search_small_subtree(id, l, r);
			else return -1;
		}
		int mid = (l + r) / 2;
		push(id);
		int t = search_small(id * 2, l, mid, u, v);
		if (t >= 0) return t;
		else return search_small(id * 2 + 1, mid + 1, r, u, v);
	}
	
	int search_big(int id, int l, int r, int u, int v) {
		if (r < u || v < l) return -1;
		if (u <= l && r <= v) {
			if (node[id].big) return search_big_subtree(id, l, r);
			else return -1;
		}
		int mid = (l + r) / 2;
		push(id);
		int t = search_big(id * 2, l, mid, u, v);
		if (t >= 0) return t;
		else return search_big(id * 2 + 1, mid + 1, r, u, v);
	}
	
	int query(int id, int l, int r, int i) {
		if (l == r) return node[id].val;
		int mid = (l + r) / 2;
		push(id);
		if (i <= mid) return query(id * 2, l, mid, i);
		else return query(id * 2 + 1, mid + 1, r, i);
	}
	
	int point_update(int i, int delta) {return point_update(1, 0, n, i, delta);}
	void set(int l, int r, int x) {range_update(1, 0, n, l, r, x);}
	int query(int i) {return query(1, 0, n, i);}
	void add(int i, int x) {
		int c = point_update(i, x);
		if (c > 0) {
			int t = search_small(1, 0, n, i + 1, n);
			// cout << "Carrying " << c << " to " << t << endl;
			// cout << query(t) << "?+" << endl;
			point_update(t, +1);
			if (i + 1 < t) set(i + 1, t - 1, 0);
			// cout << "New i and t : " << query(i) << ' ' << query(t) << endl;
		}
		else if (c < 0) {
			int t = search_big(1, 0, n, i + 1, n);
			// cout << "Carrying " << c << " to " << t << endl;
			// cout << query(t) << "?-" << endl;
			point_update(t, -1);
			if (i + 1 < t) set(i + 1, t - 1, mod - 1);
			// cout << "New i and t : " << query(i) << ' ' << query(t) << endl;
		}
	}
} tree;

signed main() {
	// freopen(taskname".inp", "r", stdin);
	// freopen(taskname".out", "w", stdout);
	ios_base::sync_with_stdio(0);
	cin.tie(0); cout.tie(0);
	int n, t1, t2, t3; cin >> n >> t1 >> t2 >> t3;
	tree.init(n + 1);
	// tree.add(1, 10); 
	// tree.add(0, -2);
	// cout << tree.query(0) << endl << tree.query(1);
	int qtype, a, b, la, ra, sa, bp, res; vector<int> pos;
	while (n--) {
		cin >> qtype >> a;
		if (qtype == 1) {
			cin >> b; pos = {}; sa = (a < 0 ? -1 : +1);
			if (a == 0) continue;
			a = abs(a);
			for (int i = 0; i < B; ++i) if (a & (1 << i)) pos.push_back(i + b);
			la = 0; ra = 0;
			bp = pos[0] - pos[0] % B + B;
			for (int i : pos)
				if (i < bp) la ^= 1 << (i % B);
				else ra ^= 1 << (i % B);
			// if (la) cout << "+ " << bp / B - 1 << ' ' << la * sa << '\n';
			tree.add(bp / B - 1, la * sa);
			// if (ra) cout << "+ " << bp / B << ' ' << ra * sa << '\n';
			tree.add(bp / B, ra * sa);
		}
		else {
			res = tree.query(a / B);
			// cout << a / B << ' ' << res << endl;
			cout << (res & (1 << (a % B)) ? 1 : 0) << '\n';
		}
	}
}