added

3 files changed, 67 insertions, 15 deletions

diff --git a/eulerian_tour.h b/eulerian_tour.h
index 8b60cfe..d755b02 100644
--- a/eulerian_tour.h
+++ b/eulerian_tour.h
@@ -1,37 +1,32 @@
+#include "types/graph/adjacent_list_base.h"
+
 #include <utility>
 #include <vector>
 
-class Eulerian {
+class Eulerian : public AdjacentListBase<int> {
   void dfs(int u) {
     while (~head[u]) {
       int i = head[u];
       head[u] = next[head[u]];
       if (!used[i >> 1]) {
         used[i >> 1] = true;
-        int v = (i & 1) ? edges[i >> 1].first : edges[i >> 1].second;
-        dfs(v);
+        dfs(edges[i]);
       }
     }
     tour.push_back(u);
   }
 
-  int n, m;
-  std::vector<int> head, next;
+  int n;
   std::vector<bool> used;
-  const std::vector<std::pair<int, int>> &edges;
 
 public:
   explicit Eulerian(int n_, int s,
                     const std::vector<std::pair<int, int>> &edges_)
-      : n{n_}, m(edges_.size()), head(n, -1), next(m << 1), used(m),
-        edges{edges_} {
-    for (int i = 0; i < m << 1; ++i) {
-      auto [u, v] = edges[i >> 1];
-      if (i & 1) {
-        std::swap(u, v);
-      }
-      next[i] = head[u];
-      head[u] = i;
+      : AdjacentListBase<int>{n_, static_cast<int>(edges_.size()) << 1}, n{n_},
+        used(edges_.size() << 1) {
+    for (auto [a, b] : edges_) {
+      add(a, b);
+      add(b, a);
     }
     dfs(s);
   }
diff --git a/segment_cover.h b/segment_cover.h
new file mode 100644
index 0000000..9b93a45
--- /dev/null
+++ b/segment_cover.h
@@ -0,0 +1,35 @@
+#include <concepts>
+#include <functional>
+#include <limits>
+#include <map>
+
+template <typename T, std::integral K = int> class SegmentCover {
+  void cut(K k) {
+    auto it = std::prev(segs.upper_bound(k));
+    if (it->first < k) {
+      segs[k] = it->second;
+    }
+  }
+
+public:
+  explicit SegmentCover(T v) {
+    segs[std::numeric_limits<K>::min()] = segs[std::numeric_limits<K>::max()] =
+        v;
+  }
+
+  // set [l, r) to v
+  void cover(K l, K r, T v, const std::function<void(K, K, T)> &cb) {
+    cut(l);
+    cut(r);
+    auto it = segs.find(l);
+    while (it->first < r) {
+      auto iit = std::next(it);
+      cb(it->first, iit->first, it->second);
+      segs.erase(it);
+      it = iit;
+    }
+    segs[l] = v;
+  }
+
+  std::map<K, T> segs;
+};
diff --git a/types/graph/adjacent_list_base.h b/types/graph/adjacent_list_base.h
new file mode 100644
index 0000000..0c17596
--- /dev/null
+++ b/types/graph/adjacent_list_base.h
@@ -0,0 +1,22 @@
+#pragma once
+
+#include <vector>
+
+template <typename Edge> class AdjacentListBase {
+public:
+  explicit AdjacentListBase(int n_, int m = 0) : n{n_}, head(n, -1) {
+    next.reserve(m);
+    edges.reserve(m);
+  }
+
+  template <typename... Args> void add(int u, Args &&...args) {
+    int i = next.size();
+    next.emplace_back(head[u]);
+    head[u] = i;
+    edges.emplace_back(std::forward<Args>(args)...);
+  }
+
+  int n;
+  std::vector<int> head, next;
+  std::vector<Edge> edges;
+};