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
| #include <bits/stdc++.h>
typedef long long ll;
const int maxn = 1e5 + 50;
int n, m, q;
ll a[maxn];
struct {
int l, r;
ll s;
#define l(x) tr[x].l
#define r(x) tr[x].r
#define s(x) tr[x].s
#define lc(x) x * 2
#define rc(x) x * 2 + 1
} tr[4 * maxn];
ll merge(ll x, ll y) {
if (x == -1 || y == -1) return -1;
ll a, b, s = 0;
for (int i = 0; i < 2 * m; i += 2) {
a = (x >> i) & 3ll, b = (y >> i) & 3ll;
if (a == 2ll) {
s |= (b << i);
} else if (b == 2ll || a == b) {
s |= (a << i);
} else {
s = -1;
break;
}
}
return s;
}
void up(int p) { s(p) = merge(s(lc(p)), s(rc(p))); }
ll count(ll x) {
if (x == -1) return 0;
ll cnt = 1;
for (int i = 0; i < 2 * m; i += 2) {
if (((x >> i) & 3ll) == 2ll) cnt *= 2ll;
}
return cnt;
}
void build(int p, int l, int r) {
l(p) = l, r(p) = r;
if (l == r) {
s(p) = a[l];
return;
}
int mid = (l + r) / 2;
build(lc(p), l, mid), build(rc(p), mid + 1, r);
up(p);
}
void update(int p, int x, ll v) {
if (l(p) == r(p)) {
s(p) = v;
return;
}
int mid = (l(p) + r(p)) / 2;
if (x <= mid) update(lc(p), x, v);
if (x > mid) update(rc(p), x, v);
up(p);
}
ll ask(int p, int l, int r) {
if (l(p) >= l && r(p) <= r) return s(p);
int mid = (l(p) + r(p)) / 2;
if (l <= mid) {
if (r > mid)
return merge(ask(lc(p), l, r), ask(rc(p), l, r));
else
return ask(lc(p), l, r);
} else {
return ask(rc(p), l, r);
}
}
int main() {
scanf("%d%d%d", &m, &n, &q);
char str[64];
ll s = 0, ans = 0;
for (int i = 1; i <= n; ++i) {
scanf("%s", str);
s = 0;
for (int j = 0; j < m; ++j) {
s |= (str[j] == '?' ? 2ll : (str[j] - 48)) << (2 * j);
}
a[i] = s;
}
build(1, 1, n);
int opt, x, y;
while (q--) {
scanf("%d%d", &opt, &x);
if (opt == 0) {
scanf("%d", &y);
ans ^= count(ask(1, x, y));
} else if (opt == 1) {
scanf("%s", str);
s = 0;
for (int j = 0; j < m; ++j) {
s |= (str[j] == '?' ? 2ll : (str[j] - 48)) << (2 * j);
}
update(1, x, s);
}
}
printf("%d", ans);
return 0;
}
|