updated

5 files changed, 50 insertions, 28 deletions

diff --git a/README.md b/README.md
index 54976e1..f8c0e30 100644
--- a/README.md
+++ b/README.md
@@ -1,3 +1,21 @@
+# Build
+
 ```shell
 cmake --build Build && (cd Build && ctest .)
 ```
+
+# Convention
+
+## Naming
+
+## Structure
+
+- namespace `xxx_details`
+
+```c++
+class C {
+  // private members
+public:
+  // public members
+};
+```
diff --git a/cartesian.h b/cartesian.h
index f1dce5d..0aed10c 100644
--- a/cartesian.h
+++ b/cartesian.h
@@ -1,34 +1,33 @@
+#include "types/compare.h"
+
 #include <array>
 #include <functional>
+#include <ranges>
 #include <vector>
 
-template <typename T, typename Compare = std::less<T>>
-struct MaxCartesianTree : public std::vector<std::array<int, 2>> {
-  explicit MaxCartesianTree(const std::vector<T> &a,
-                            Compare compare = Compare{})
-      : std::vector<std::array<int, 2>>(a.size(), std::array<int, 2>{-1, -1}) {
-    int n = a.size();
-    std::vector<int> stack;
-    stack.reserve(n);
-    for (int i = 0; i < n; ++i) {
-      int left = -1;
-      while (!stack.empty() && compare(a[stack.back()], a[i])) {
-        int j = stack.back();
-        stack.pop_back();
-        (*this)[j][1] = left;
-        left = j;
+template <typename T, typename C = std::less<T>>
+  requires IsComparator<C, T>
+class MaxCartesianTree {
+  int n;
+  std::vector<int> stack;
+
+public:
+  explicit MaxCartesianTree(std::ranges::random_access_range auto const &&a,
+                            C compare = {})
+      : n(std::ranges::size(a)), stack(n + 1), root{-1}, child(n) {
+    int top = 0;
+    stack[0] = -1;
+    for (int i = 0; i < n; i++) {
+      while (~stack[top] && compare(a[stack[top]], a[i])) {
+        top--;
       }
-      (*this)[i][0] = left;
-      stack.push_back(i);
-    }
-    root = -1;
-    while (!stack.empty()) {
-      int i = stack.back();
-      stack.pop_back();
-      (*this)[i][1] = root;
-      root = i;
+      int &r = top ? child[stack[top]][1] : root;
+      child[i] = {r, -1};
+      r = i;
+      stack[++top] = i;
     }
   }
 
-  int root;
+  int root; // virtually child[-1][1]
+  std::vector<std::array<int, 2>> child;
 };
diff --git a/types/compare.h b/types/compare.h
new file mode 100644
index 0000000..6e6a4c2
--- /dev/null
+++ b/types/compare.h
@@ -0,0 +1,6 @@
+#pragma once
+
+#include <concepts>
+
+template <typename C, typename T>
+concept IsComparator = std::predicate<C, T, T>;
diff --git a/types/graph.h b/types/graph.h
index b67b5c3..f8ea978 100644
--- a/types/graph.h
+++ b/types/graph.h
@@ -4,9 +4,9 @@
 #include <ranges>
 
 template <typename G>
-concept IsGraph = requires(const G &g) {
+concept IsGraph = requires(G g) {
   { g.size() } -> std::convertible_to<int>;
-} && requires(const G &g, int u) {
+} && requires(G g, int u) {
   requires std::ranges::forward_range<decltype(g[u])>;
 };
 
diff --git a/types/total_monotone.h b/types/total_monotone.h
index 8b614fa..2b742ad 100644
--- a/types/total_monotone.h
+++ b/types/total_monotone.h
@@ -1,7 +1,6 @@
 #pragma once
 
 #include <concepts>
-#include <utility>
 
 template <typename A, typename E>
 concept IsTM2 = requires(A m, int i, int j) {