Codeforces 707D Persistent Bookcase

链接

传送门

题意

给出$n \times m (1 \leq n, m \leq 10^3)$矩阵,初始全为0。有$q (1 \leq q \leq 10^5)$个操作,可以将一个点置0,将一个点置1,将一行的数字翻转,或回到之前某次操作的状态。对于每次操作输出矩阵中1的个数。

思路

对操作建树,然后在树上dfs求解。

代码

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
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <vector>
#include <bitset>
#include <cassert>
using namespace std;
const int maxn = 1005;
const int maxq = 100005;
int n, m, q;
int x[maxq], y[maxq];
int op[maxq], ans[maxq];
bool flag[maxq], rev[maxn];
vector<int> g[maxq];
bitset<maxn> a[maxn], tmp[maxq];
void dfs(int u, int res) {
tmp[u] = a[x[u]];
flag[u] = rev[x[u]];
if (op[u] == 3) {
rev[x[u]] = !rev[x[u]];
} else if (op[u] != 0) {
a[x[u]][y[u]] = flag[u] ? 1 - (op[u] & 1) : (op[u] & 1);
}
res -= flag[u] ? m - tmp[u].count() : tmp[u].count();
res += rev[x[u]] ? m - a[x[u]].count(): a[x[u]].count();
ans[u] = res;
for (int v: g[u]) {
dfs(v, res);
}
a[x[u]] = tmp[u];
rev[x[u]] = flag[u];
}
int main() {
int pre = 0;
scanf("%d%d%d", &n, &m, &q);
for (int i = 1; i <= q; ++i) {
scanf("%d%d", &op[i], &x[i]);
if (op[i] < 3) {
scanf("%d", &y[i]);
}
if (op[i] == 4) {
pre = x[i];
while (op[pre] == 4) {
x[i] = x[pre];
pre = x[pre];
}
} else {
g[pre].push_back(i);
pre = i;
}
}
dfs(0, 0);
for (int i = 1; i <= q; ++i) {
if (op[i] == 4) {
printf("%d\n", ans[x[i]]);
} else {
printf("%d\n", ans[i]);
}
}
return 0;
}

支付宝扫码领红包