「NOI 2017」整数【线段树】

Time Limit: 50 Sec Memory Limit: 512 MB

Description

有一个整数 xx,一开始为 00

接下来有 nn 个操作,每个操作都是以下两种类型中的一种:

  • 1 a b1\ a\ b:将 xx 加上整数 a2ba \cdot 2^b,其中 aa 为一个整数,bb 为一个非负整数。
  • 2 k2\ k:询问 xx 在用二进制表示时,位权为 2k2^k 的位的值 (即这一位上的 11 代表 2k2^k)。

保证在任何时候,x0x \geqslant 0

Input

第一行包含四个正整数 n,t1,t2,t3n, t_1, t_2, t_3nn 的含义见题目描述,t1,t2,t3t_1, t_2, t_3 表示子任务类型。
接下来 nn 行,每行给出一个操作,具体格式和含义见题目描述。
同一行输入的相邻两个元素之间,用恰好一个空格隔开。

Output

对于每个询问操作,输出一行,表示该询问的答案 (0011)。对于加法操作,没有任何输出。

Sample Input

1
2
3
4
5
6
7
8
9
10
11
10 3 1 2
1 100 0
1 2333 0
1 -233 0
2 5
2 7
2 15
1 5 15
2 15
1 -1 12
2 15

Sample Output

1
2
3
4
5
0
1
0
1
0

Constraints

n1000000,n \leqslant 1000000, a109,|a| \leqslant 10^9, 0b,k30n0 \leqslant b, k \leqslant 30n

Solution

可以把 xx 的二进制当作 0101 序列用线段树维护,那么序列中的第 kk 位就是整数中位权为 2k2^k 的位。线段树需要维护区间是否全是 11。操作如下:

  • 加法:可以把整数拆成一些二进制位,一位一位地加 11。每次加的时候找更高位第一个为 00 的位置,将其修改为 11,中间的位置就都修改为 00
  • 减法:找到更高位第一个为 11 的位置,将其修改为 00,中间的位置就都修改为 11

但这样的时间复杂度为 O(nlognloga)O(n \log n \log a),将会 TLE\text{TLE}。考虑压位,将 6060 个位用一个 long long 存起来。注意不要再把 aa 一位一位拆开,最多拆成两部分,分别加即可。

时间复杂度为 O(nlogn)O(n \log n)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
const int maxn = 500010, S = 60;
ll a, b, INF = (1LL << S) - 1, f[maxn];
int n, m, t1, t2, t3;
struct segment_tree {
int l, r, pos;
ll lazy;
bool all[2];
} tree[maxn << 2];

void maintain(int k) {
tree[k].all[0] = tree[k << 1].all[0] & tree[k << 1 | 1].all[0];
tree[k].all[1] = tree[k << 1].all[1] & tree[k << 1 | 1].all[1];
}

void modify(int k, ll x) {
if (tree[k].pos != -1) f[tree[k].pos] = x; tree[k].lazy = x;
if (x == 0) tree[k].all[0] = 1, tree[k].all[1] = 0;
else if (x == INF) tree[k].all[0] = 0, tree[k].all[1] = 1;
else tree[k].all[0] = tree[k].all[1] = 0;
}

void pushdown(int k) {
if (tree[k].lazy == -1) return;
modify(k << 1, tree[k].lazy), modify(k << 1 | 1, tree[k].lazy);
tree[k].lazy = -1;
}

void build(int k, int l, int r) {
tree[k].l = l, tree[k].r = r, tree[k].all[0] = 1, tree[k].lazy = tree[k].pos = -1;
if (l == r) { tree[k].pos = l; return; }
int mid = (l + r) >> 1;
build(k << 1, l, mid), build(k << 1 | 1, mid + 1, r);
}

void change(int k, int l, int r, ll x) {
if (tree[k].l == l && tree[k].r == r) { modify(k, x); return; }
pushdown(k);
int mid = (tree[k].l + tree[k].r) >> 1;
if (mid >= r) {
change(k << 1, l, r, x);
} else if (mid < l) {
change(k << 1 | 1, l, r, x);
} else {
change(k << 1, l, mid, x), change(k << 1 | 1, mid + 1, r, x);
}
maintain(k);
}

int find_nxt(int k, int p, int v) {
if (tree[k].all[!v]) return -1;
if (tree[k].l == tree[k].r) return tree[k].l;
int mid = (tree[k].l + tree[k].r) >> 1, t;
if (mid >= p && (t = find_nxt(k << 1, p, v)) != -1) return t;
return find_nxt(k << 1 | 1, p, v);
}

ll query(int k, int p) {
if (tree[k].l == tree[k].r) return f[tree[k].l];
pushdown(k);
int mid = (tree[k].l + tree[k].r) >> 1;
if (mid >= p) {
return query(k << 1, p);
} else {
return query(k << 1 | 1, p);
}
}

void add(int p, ll x) {
ll t = query(1, p); change(1, p, p, (t + x) & INF);
if (t + x > INF) {
t = find_nxt(1, p + 1, 0);
change(1, t, t, f[t] + 1);
if (p + 1 < t) change(1, p + 1, t - 1, 0);
}
}

void sub(int p, ll x) {
ll t = query(1, p); change(1, p, p, (t - x) & INF);
if (t - x < 0) {
t = find_nxt(1, p + 1, 1);
change(1, t, t, f[t] - 1);
if (p + 1 < t) change(1, p + 1, t - 1, INF);
}
}

int main() {
scanf("%d %d %d %d", &m, &t1, &t2, &t3), n = (m + 2) >> 1;
build(1, 0, n);
for (int i = 1, op; i <= m; i++) {
scanf("%d %lld", &op, &a);
if (op == 1) {
scanf("%lld", &b);
if (a > 0) {
int p = b / S, r = b % S;
ll x = a << r & INF;
if (x) add(p, x);
p++, a >>= (S - r);
if (b) add(p, a);
} else {
a = -a;
int p = b / S, r = b % S;
ll x = a << r & INF;
if (x) sub(p, x);
p++, a >>= (S - r);
if (b) sub(p, a);
}
} else {
printf("%d\n", query(1, a / S) >> (a % S) & 1);
}
}
return 0;
}