add cart.cpp

snuke · snuke · commit 63a4f8f78f52 · 2025-05-25T03:08:47.000+09:00
diff --git a/README.md b/README.md
@@ -19,6 +19,7 @@ AtCoder解説放送ライブラリ集
 |BIT|[bit.cpp](bit.cpp)|Binary Indexed Tree (Fenwick Tree)|
 |UnionFind|[uf.cpp](uf.cpp)|Union Find (DSU)|
 |CHT|[cht.cpp](cht.cpp)|Convex Hull Trick|
+|CartesianTree|[cart.cpp](cart.cpp)|Cartesian Tree|
 
 ### 数学
 |名前|コード|説明|
diff --git a/cart.cpp b/cart.cpp
@@ -0,0 +1,24 @@
+// Cartesian Tree
+// https://youtu.be/XVu8-ZnuOiA?t=9291
+template<class T=long long>
+struct CartesianTree {
+  int n, root;
+  vector<int> l, r;
+  CartesianTree() {}
+  CartesianTree(const vector<T>& a, bool _max=true) {
+    n = a.size();
+    l = r = vector<int>(n,-1);
+    vector<int> st;
+    rep(i,n) {
+      int p = -1;
+      while (st.size() && !((a[st.back()] < a[i])^_max)) {
+        int j = st.back(); st.pop_back();
+        r[j] = p; p = j;
+      }
+      l[i] = p;
+      st.push_back(i);
+    }
+    rep(i,st.size()-1) r[st[i]] = st[i+1];
+    root = st[0];
+  }
+};
