matsutaku-library

This documentation is automatically generated by competitive-verifier/competitive-verifier

View the Project on GitHub MatsuTaku/matsutaku-library

:heavy_check_mark: test/yosupo/dynamic_graph_vertex_add_component_sum.test.cpp

Code

#define PROBLEM "https://judge.yosupo.jp/problem/dynamic_graph_vertex_add_component_sum"

#include "include/mtl/segment_tree_divide_and_conquer.hpp"
#include <bits/stdc++.h>
using namespace std;

struct UndoableUnionFind {
  vector<int> par;
  vector<long long> data;
  stack<vector<pair<int, long long>>> history;
  UndoableUnionFind(int n) : par(n, -1), data(n) {}
  int leader(int x) const {
    return par[x] < 0 ? x : leader(par[x]);
  }
  bool same(int x, int y) const {
    return leader(x) == leader(y);
  }
  int size(int x) const {
    return -par[leader(x)];
  }
  void merge(int x, int y) {
    auto X = leader(x);
    auto Y = leader(y);
    if (X == Y) {
      return;
    }
    if (size(X) < size(Y)) swap(X, Y);
    history.top().emplace_back(X, par[X]);
    par[X] += par[Y];
    history.top().emplace_back(Y, par[Y]);
    par[Y] = X;
    history.top().emplace_back(-X-1, data[X]);
    data[X] += data[Y];
  }
  void add(int v, int x) {
    auto V = leader(v);
    history.top().emplace_back(-V-1, data[V]);
    data[V] += x;
  }
  void snapshot() {
    history.emplace();
  }
  void undo() {
    for (int i = (int)history.top().size()-1; i >= 0; i--) {
      auto [x, y] = history.top()[i];
      if (x < 0) {
        data[-x-1] = y;
      } else {
        par[x] = y;
      }
    }
    history.pop();
  }
};
  
constexpr int NMAX = 3e5+1;

int main() {
  int n,q; cin>>n>>q;
  vector<int> A(n);
  for (int i = 0; i < n; i++) cin>>A[i];
  vector<array<int, 3>> Q(q);
  unordered_map<long long, int> S;
  SegmentTreeDivideAndConquer<vector<pair<int,int>>> G(q);
  for (int i = 0; i < q; i++) {
    int t; cin>>t;
    switch (t) {
      case 0: {
        int u,v; cin>>u>>v;
        Q[i] = {t,u,v};
        if (u > v) swap(u,v);
        S.emplace((long long)NMAX*u+v, i);
        break;
      }
      case 1: {
        int u,v; cin>>u>>v;
        Q[i] = {t,u,v};
        if (u > v) swap(u,v);
        auto it = S.find((long long)NMAX*u+v);
        assert(it != S.end());
        auto s = it->second;
        S.erase(it);
        G.set(s, i, [&](auto& qs) {
          qs.emplace_back(u, v); 
        });
        break;
      }
      case 2: {
        int v,x; cin>>v>>x;
        Q[i] = {t,v,x};
        G.set(i, q, [&](auto& qs) {
          qs.emplace_back(-v-1, x);
        });
        break;
      }
      case 3: {
        int v; cin>>v;
        Q[i] = {t,v};
        break;
      }
    }
  }
  for (auto [id,s] : S) {
    int u = id/NMAX;
    int v = id%NMAX;
    G.set(s, q, [&](auto& qs) {
      qs.emplace_back(u, v);
    });
  }
  UndoableUnionFind uf(n);
  for (int i = 0; i < n; i++) uf.data[i] = A[i];
  G.dfs([&](int i) {
    if (Q[i][0] == 3) {
      cout << uf.data[uf.leader(Q[i][1])] << endl;
    }
  }, [&](auto& vs) {
    uf.snapshot();
    for (auto [a,b]: vs) {
      if (a < 0) {
        uf.add(-a-1, b);
      } else {
        uf.merge(a, b);
      }
    }
  }, [&] {
    uf.undo();
  });
}
#line 1 "test/yosupo/dynamic_graph_vertex_add_component_sum.test.cpp"
#define PROBLEM "https://judge.yosupo.jp/problem/dynamic_graph_vertex_add_component_sum"

#line 2 "include/mtl/bit_manip.hpp"
#include <cstdint>
#include <cassert>
#if __cplusplus >= 202002L
#ifndef MTL_CPP20
#define MTL_CPP20
#endif
#include <bit>
#endif

namespace bm {

/// Count 1s for each 8 bits
inline constexpr uint64_t popcnt_e8(uint64_t x) {
  x = (x & 0x5555555555555555) + ((x>>1) & 0x5555555555555555);
  x = (x & 0x3333333333333333) + ((x>>2) & 0x3333333333333333);
  x = (x & 0x0F0F0F0F0F0F0F0F) + ((x>>4) & 0x0F0F0F0F0F0F0F0F);
  return x;
}
/// Count 1s
inline constexpr unsigned popcnt(uint64_t x) {
#ifdef MTL_CPP20
  return std::popcount(x);
#else
  return (popcnt_e8(x) * 0x0101010101010101) >> 56;
#endif
}
/// Alias to mtl::popcnt(x)
constexpr unsigned popcount(uint64_t x) {
  return popcnt(x);
}
/// Count trailing 0s. s.t. *11011000 -> 3
inline constexpr unsigned ctz(uint64_t x) {
#ifdef MTL_CPP20
  return std::countr_zero(x);
#else
  return popcnt((x & (-x)) - 1);
#endif
}
/// Alias to mtl::ctz(x)
constexpr unsigned countr_zero(uint64_t x) {
  return ctz(x);
}
/// Count trailing 1s. s.t. *11011011 -> 2
inline constexpr unsigned cto(uint64_t x) {
#ifdef MTL_CPP20
  return std::countr_one(x);
#else
  return ctz(~x);
#endif
}
/// Alias to mtl::cto(x)
constexpr unsigned countr_one(uint64_t x) {
  return cto(x);
}
inline constexpr unsigned ctz8(uint8_t x) {
  return x == 0 ? 8 : popcnt_e8((x & (-x)) - 1);
}
/// [00..0](8bit) -> 0, [**..*](not only 0) -> 1
inline constexpr uint8_t summary(uint64_t x) {
  constexpr uint64_t hmask = 0x8080808080808080ull;
  constexpr uint64_t lmask = 0x7F7F7F7F7F7F7F7Full;
  auto a = x & hmask;
  auto b = x & lmask;
  b = hmask - b;
  b = ~b;
  auto c = (a | b) & hmask;
  c *= 0x0002040810204081ull;
  return uint8_t(c >> 56);
}
/// Extract target area of bits
inline constexpr uint64_t bextr(uint64_t x, unsigned start, unsigned len) {
  uint64_t mask = len < 64 ? (1ull<<len)-1 : 0xFFFFFFFFFFFFFFFFull;
  return (x >> start) & mask;
}
/// 00101101 -> 00111111 -count_1s-> 6
inline constexpr unsigned log2p1(uint8_t x) {
  if (x & 0x80)
    return 8;
  uint64_t p = uint64_t(x) * 0x0101010101010101ull;
  p -= 0x8040201008040201ull;
  p = ~p & 0x8080808080808080ull;
  p = (p >> 7) * 0x0101010101010101ull;
  p >>= 56;
  return p;
}
/// 00101100 -mask_mssb-> 00100000 -to_index-> 5
inline constexpr unsigned mssb8(uint8_t x) {
  assert(x != 0);
  return log2p1(x) - 1;
}
/// 00101100 -mask_lssb-> 00000100 -to_index-> 2
inline constexpr unsigned lssb8(uint8_t x) {
  assert(x != 0);
  return popcnt_e8((x & -x) - 1);
}
/// Count leading 0s. 00001011... -> 4
inline constexpr unsigned clz(uint64_t x) {
#ifdef MTL_CPP20
  return std::countl_zero(x);
#else
  if (x == 0)
    return 64;
  auto i = mssb8(summary(x));
  auto j = mssb8(bextr(x, 8 * i, 8));
  return 63 - (8 * i + j);
#endif
}
/// Alias to mtl::clz(x)
constexpr unsigned countl_zero(uint64_t x) {
  return clz(x);
}
/// Count leading 1s. 11110100... -> 4
inline constexpr unsigned clo(uint64_t x) {
#ifdef MTL_CPP20
  return std::countl_one(x);
#else
  return clz(~x);
#endif
}
/// Alias to mtl::clo(x)
constexpr unsigned countl_one(uint64_t x) {
  return clo(x);
}

inline constexpr unsigned clz8(uint8_t x) {
  return x == 0 ? 8 : 7 - mssb8(x);
}
inline constexpr uint64_t bit_reverse(uint64_t x) {
  x = ((x & 0x00000000FFFFFFFF) << 32) | ((x & 0xFFFFFFFF00000000) >> 32);
  x = ((x & 0x0000FFFF0000FFFF) << 16) | ((x & 0xFFFF0000FFFF0000) >> 16);
  x = ((x & 0x00FF00FF00FF00FF) << 8) | ((x & 0xFF00FF00FF00FF00) >> 8);
  x = ((x & 0x0F0F0F0F0F0F0F0F) << 4) | ((x & 0xF0F0F0F0F0F0F0F0) >> 4);
  x = ((x & 0x3333333333333333) << 2) | ((x & 0xCCCCCCCCCCCCCCCC) >> 2);
  x = ((x & 0x5555555555555555) << 1) | ((x & 0xAAAAAAAAAAAAAAAA) >> 1);
  return x;
}

/// Check if x is power of 2. 00100000 -> true, 00100001 -> false
constexpr bool has_single_bit(uint64_t x) noexcept {
#ifdef MTL_CPP20
  return std::has_single_bit(x);
#else
  return x != 0 && (x & (x - 1)) == 0;
#endif
}

/// Bit width needs to represent x. 00110110 -> 6
constexpr int bit_width(uint64_t x) noexcept {
#ifdef MTL_CPP20
  return std::bit_width(x);
#else
  return 64 - clz(x);
#endif
}

/// Ceil power of 2. 00110110 -> 01000000
constexpr uint64_t bit_ceil(uint64_t x) {
#ifdef MTL_CPP20
  return std::bit_ceil(x);
#else
  if (x == 0) return 1;
  return 1ull << bit_width(x - 1);
#endif
}

/// Floor power of 2. 00110110 -> 00100000
constexpr uint64_t bit_floor(uint64_t x) {
#ifdef MTL_CPP20
  return std::bit_floor(x);
#else
  if (x == 0) return 0;
  return 1ull << (bit_width(x) - 1);
#endif
}

} // namespace bm
#line 3 "include/mtl/segment_tree_divide_and_conquer.hpp"
#include <cstddef>
#include <vector>

template<class NodeContainer>
class SegmentTreeDivideAndConquer {
 private:
  size_t time_, size_;
  std::vector<NodeContainer> tree_;

 public:
  SegmentTreeDivideAndConquer() = default;
  explicit SegmentTreeDivideAndConquer(size_t time) : time_(time), size_(bm::bit_ceil(time)), tree_(size_+time_) {}
  
  template<class Set>
  void set(size_t l, size_t r, Set set) {
    for (auto _l = l+size_, _r = r+size_; _l < _r; _l>>=1, _r>>=1) {
      if (_l&1) set(tree_[_l++]);
      if (_r&1) set(tree_[--_r]);
    }
  }

  template<class F, class Upd, class Undo>
  void dfs(F fn, Upd upd, Undo undo) const {
    _dfs(1, fn, upd, undo);
  }

 private:
  template<class F, class Upd, class Undo>
  void _dfs(size_t u, F fn, Upd upd, Undo undo) const {
    if (u >= size_+time_) return;
    upd(tree_[u]);
    if (u < size_) {
      _dfs(u*2, fn, upd, undo);
      _dfs(u*2+1, fn, upd, undo);
    } else {
      fn(u-size_);
    }
    undo();
  }

};
#line 4 "test/yosupo/dynamic_graph_vertex_add_component_sum.test.cpp"
#include <bits/stdc++.h>
using namespace std;

struct UndoableUnionFind {
  vector<int> par;
  vector<long long> data;
  stack<vector<pair<int, long long>>> history;
  UndoableUnionFind(int n) : par(n, -1), data(n) {}
  int leader(int x) const {
    return par[x] < 0 ? x : leader(par[x]);
  }
  bool same(int x, int y) const {
    return leader(x) == leader(y);
  }
  int size(int x) const {
    return -par[leader(x)];
  }
  void merge(int x, int y) {
    auto X = leader(x);
    auto Y = leader(y);
    if (X == Y) {
      return;
    }
    if (size(X) < size(Y)) swap(X, Y);
    history.top().emplace_back(X, par[X]);
    par[X] += par[Y];
    history.top().emplace_back(Y, par[Y]);
    par[Y] = X;
    history.top().emplace_back(-X-1, data[X]);
    data[X] += data[Y];
  }
  void add(int v, int x) {
    auto V = leader(v);
    history.top().emplace_back(-V-1, data[V]);
    data[V] += x;
  }
  void snapshot() {
    history.emplace();
  }
  void undo() {
    for (int i = (int)history.top().size()-1; i >= 0; i--) {
      auto [x, y] = history.top()[i];
      if (x < 0) {
        data[-x-1] = y;
      } else {
        par[x] = y;
      }
    }
    history.pop();
  }
};
  
constexpr int NMAX = 3e5+1;

int main() {
  int n,q; cin>>n>>q;
  vector<int> A(n);
  for (int i = 0; i < n; i++) cin>>A[i];
  vector<array<int, 3>> Q(q);
  unordered_map<long long, int> S;
  SegmentTreeDivideAndConquer<vector<pair<int,int>>> G(q);
  for (int i = 0; i < q; i++) {
    int t; cin>>t;
    switch (t) {
      case 0: {
        int u,v; cin>>u>>v;
        Q[i] = {t,u,v};
        if (u > v) swap(u,v);
        S.emplace((long long)NMAX*u+v, i);
        break;
      }
      case 1: {
        int u,v; cin>>u>>v;
        Q[i] = {t,u,v};
        if (u > v) swap(u,v);
        auto it = S.find((long long)NMAX*u+v);
        assert(it != S.end());
        auto s = it->second;
        S.erase(it);
        G.set(s, i, [&](auto& qs) {
          qs.emplace_back(u, v); 
        });
        break;
      }
      case 2: {
        int v,x; cin>>v>>x;
        Q[i] = {t,v,x};
        G.set(i, q, [&](auto& qs) {
          qs.emplace_back(-v-1, x);
        });
        break;
      }
      case 3: {
        int v; cin>>v;
        Q[i] = {t,v};
        break;
      }
    }
  }
  for (auto [id,s] : S) {
    int u = id/NMAX;
    int v = id%NMAX;
    G.set(s, q, [&](auto& qs) {
      qs.emplace_back(u, v);
    });
  }
  UndoableUnionFind uf(n);
  for (int i = 0; i < n; i++) uf.data[i] = A[i];
  G.dfs([&](int i) {
    if (Q[i][0] == 3) {
      cout << uf.data[uf.leader(Q[i][1])] << endl;
    }
  }, [&](auto& vs) {
    uf.snapshot();
    for (auto [a,b]: vs) {
      if (a < 0) {
        uf.add(-a-1, b);
      } else {
        uf.merge(a, b);
      }
    }
  }, [&] {
    uf.undo();
  });
}

Test cases

Env Name Status Elapsed Memory
g++ dense_00 :heavy_check_mark: AC 355 ms 61 MB
g++ dense_01 :heavy_check_mark: AC 310 ms 56 MB
g++ dense_02 :heavy_check_mark: AC 288 ms 53 MB
g++ example_00 :heavy_check_mark: AC 5 ms 3 MB
g++ link_and_cut_00 :heavy_check_mark: AC 429 ms 66 MB
g++ max_random_00 :heavy_check_mark: AC 436 ms 56 MB
g++ max_random_01 :heavy_check_mark: AC 449 ms 58 MB
g++ max_random_02 :heavy_check_mark: AC 451 ms 58 MB
g++ random_00 :heavy_check_mark: AC 394 ms 53 MB
g++ random_01 :heavy_check_mark: AC 300 ms 37 MB
g++ random_02 :heavy_check_mark: AC 126 ms 18 MB
g++ random_03 :heavy_check_mark: AC 165 ms 23 MB
g++ random_04 :heavy_check_mark: AC 190 ms 22 MB
g++ small_00 :heavy_check_mark: AC 6 ms 4 MB
g++ small_01 :heavy_check_mark: AC 5 ms 4 MB
g++ small_02 :heavy_check_mark: AC 6 ms 4 MB
g++ uv_swapped_00 :heavy_check_mark: AC 429 ms 56 MB
g++ uv_swapped_01 :heavy_check_mark: AC 441 ms 58 MB
g++ uv_swapped_02 :heavy_check_mark: AC 443 ms 57 MB
clang++ dense_00 :heavy_check_mark: AC 339 ms 61 MB
clang++ dense_01 :heavy_check_mark: AC 308 ms 56 MB
clang++ dense_02 :heavy_check_mark: AC 301 ms 53 MB
clang++ example_00 :heavy_check_mark: AC 5 ms 3 MB
clang++ link_and_cut_00 :heavy_check_mark: AC 442 ms 66 MB
clang++ max_random_00 :heavy_check_mark: AC 435 ms 56 MB
clang++ max_random_01 :heavy_check_mark: AC 479 ms 58 MB
clang++ max_random_02 :heavy_check_mark: AC 451 ms 58 MB
clang++ random_00 :heavy_check_mark: AC 394 ms 53 MB
clang++ random_01 :heavy_check_mark: AC 276 ms 37 MB
clang++ random_02 :heavy_check_mark: AC 119 ms 18 MB
clang++ random_03 :heavy_check_mark: AC 152 ms 23 MB
clang++ random_04 :heavy_check_mark: AC 193 ms 22 MB
clang++ small_00 :heavy_check_mark: AC 6 ms 4 MB
clang++ small_01 :heavy_check_mark: AC 5 ms 4 MB
clang++ small_02 :heavy_check_mark: AC 5 ms 3 MB
clang++ uv_swapped_00 :heavy_check_mark: AC 427 ms 56 MB
clang++ uv_swapped_01 :heavy_check_mark: AC 463 ms 58 MB
clang++ uv_swapped_02 :heavy_check_mark: AC 502 ms 57 MB
Back to top page