Merge pull request #3 from MaskRay/cartesianHEADmaster

make stack smaller

1 files changed, 4 insertions, 5 deletions

diff --git a/cartesian.h b/cartesian.h
index 4108d3f..fc2780e 100644
--- a/cartesian.h
+++ b/cartesian.h
@@ -14,14 +14,13 @@ class MaxCartesianTree {
 public:
   explicit MaxCartesianTree(std::ranges::random_access_range auto a,
                             C compare = {})
-      : n(std::ranges::size(a)), stack(n + 1), root{-1}, child(n) {
-    int top = 0;
-    stack[0] = -1;
+      : n(std::ranges::size(a)), stack(n), root{-1}, child(n) {
+    int top = -1;
     for (int i = 0; i < n; i++) {
-      while (~stack[top] && compare(a[stack[top]], a[i])) {
+      while (~top && compare(a[stack[top]], a[i])) {
         top--;
       }
-      int &r = top ? child[stack[top]][1] : root;
+      int &r = ~top ? child[stack[top]][1] : root;
       child[i] = {r, -1};
       r = i;
       stack[++top] = i;