Codeforces 707D Persistent Bookcase

发表于 分类于 Disqus：

链接

传送门

题意

给出\(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;
}
相关文章