上一章中介绍到使用可撤销并查集结合线段树分治可以维护图的连通性信息。由于在同一时间线段树的深度为 $O(\log q)$ ，因此可以利用直接复制的操作，如果数据结构大小为 $n$，则总的时间复杂度为 $O(nq\log q)$

  1. CF601E

    维护背包问题的 dp 数组：

    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
    int main() {
      std::ios::sync_with_stdio(false);
      std::cin.tie(nullptr);
      int n, k;
      cin >> n >> k;
      std::vector<Z> fac(k);
      fac[0] = 1;
      const int P = 10000019;
      for (int i = 1; i < k; i++) {
        fac[i] = fac[i - 1] * P;
      }
      
      std::vector<pii> items(n);
      
      for (int i = 0; i < n; i++) {
        int v, w;
        cin >> v >> w;
        items[i] = {v, w};
      }
      
      int q, cnt = n;
      cin >> q;
      items.resize(n + q);
      std::vector<std::vector<int>> event(n + q);
      for (int i = 0; i < n; i++) {
        event[i].push_back(0);
      }
      
      std::vector<bool> haveq(q + 1);
      
      for (int i = 1; i <= q; i++) {
        int op;
        cin >> op;
        if (op == 1) {
          int v, w;
          cin >> v >> w;
          items[cnt] = {v, w};
          event[cnt].push_back(i);
          cnt++;
        } else if (op == 2) {
          int x;
          cin >> x;
          x--;
          event[x].push_back(i - 1);
        } else {
          haveq[i] = true;
        }
      }
      
      std::vector<std::vector<int>> seg((q + 1) << 2);
      auto add = [&](this auto && add, int p, int l, int r, int x, int y, int v) -> void {
        if (l >= x && r <= y) {
          seg[p].push_back(v);
          return;
        }
        int m = (l + r) / 2;
        if (x <= m) {
          add(p << 1, l, m, x, y, v);
        }
        if (y >= m + 1) {
          add(p << 1 | 1, m + 1, r, x, y, v);
        }
      };
      for (int i = 0; i < n + q; i++) {
        if (event[i].size() == 0) break;
        
        if (event[i].size() & 1) {
          event[i].push_back(q);
        }
        
        for (int j = 0; j + 1 < event[i].size(); j++) {
          add(1, 0, q, event[i][j], event[i][j + 1], i);
        }
      }
      std::vector<int> dp(k + 1);
      auto dfs = [&](this auto && dfs, int p, int l, int r) -> void {
        auto ndp = dp;
        for (auto x : seg[p]) {
          auto [v, w] = items[x];
          for (int i = k; i >= w; i--) {
            dp[i] = std::max(dp[i], dp[i - w] + v);
          }
        }
        
        if (l == r) {
          if (haveq[l]) {
            Z ans = 0;
            for (int i = 1; i <= k; i++) {
              ans += fac[i - 1] * dp[i];
            }
            cout << ans << "\n";
          }
          dp = ndp;
          return;
        }
        
        int m = (l + r) / 2;
        dfs(p << 1, l, m);
        dfs(p << 1 | 1, m + 1, r);
        
        dp = ndp;
      };
      dfs(1, 0, q);
      return 0;
    }

  2. loj 6515