cartesian_tree.hpp¶

SECTIONData Structure INCLUDEnoya/cartesian_tree.hpp

把数组构造成同时满足下标中序与值堆序的笛卡尔树；常用于区间最值结构、单调栈关系和分治。

Complexity: Time: O(n). Space: O(n).

Implementation¶

ReferenceSourceExpanded

当前头文件，省略 include guard；依赖见 #include。

/// @complexity Time: O(n).
/// Space: O(n).

#include <cassert>
#include <vector>

namespace noya {

/// @brief Cartesian tree where each node is the minimum of its subtree. Equal values prefer the leftmost.
struct min_cartesian_tree {
  int n, rt;
  std::vector<int> par, lef, rig;
  template <class T> void build(int n_, T *as) {
    assert(n_ >= 1);
    n = n_;
    rt = 0;
    par.assign(n, -1);
    lef.assign(n, -1);
    rig.assign(n, -1);
    int top = 0;
    std::vector<int> stk(n, 0);
    for (int u = 1; u < n; ++u) {
      if (as[stk[top]] > as[u]) {
        for (; top >= 1 && as[stk[top - 1]] > as[u]; --top) {
        }
        if (top == 0) {
          rt = par[lef[u] = stk[top]] = u;
        } else {
          par[lef[u] = stk[top]] = u;
          rig[par[u] = stk[top - 1]] = u;
        }
        stk[top] = u;
      } else {
        rig[par[u] = stk[top]] = u;
        stk[++top] = u;
      }
    }
  }
  template <class T> void build(const T &as) { build(as.size(), as.data()); }
};

/// @brief Cartesian tree where each node is the maximum of its subtree. Equal values prefer the leftmost.
struct max_cartesian_tree {
  int n, rt;
  std::vector<int> par, lef, rig;
  template <class T> void build(int n_, T *as) {
    assert(n_ >= 1);
    n = n_;
    rt = 0;
    par.assign(n, -1);
    lef.assign(n, -1);
    rig.assign(n, -1);
    int top = 0;
    std::vector<int> stk(n, 0);
    for (int u = 1; u < n; ++u) {
      if (as[stk[top]] < as[u]) {
        for (; top >= 1 && as[stk[top - 1]] < as[u]; --top) {
        }
        if (top == 0) {
          rt = par[lef[u] = stk[top]] = u;
        } else {
          par[lef[u] = stk[top]] = u;
          rig[par[u] = stk[top - 1]] = u;
        }
        stk[top] = u;
      } else {
        rig[par[u] = stk[top]] = u;
        stk[++top] = u;
      }
    }
  }
  template <class T> void build(const T &as) { build(as.size(), as.data()); }
};

} // namespace noya

#ifndef NOYA_CARTESIAN_TREE_HPP
#define NOYA_CARTESIAN_TREE_HPP 1

/// @complexity Time: O(n).
/// Space: O(n).

#include <cassert>
#include <vector>

namespace noya {

/// @brief Cartesian tree where each node is the minimum of its subtree. Equal values prefer the leftmost.
struct min_cartesian_tree {
  int n, rt;
  std::vector<int> par, lef, rig;
  template <class T> void build(int n_, T *as) {
    assert(n_ >= 1);
    n = n_;
    rt = 0;
    par.assign(n, -1);
    lef.assign(n, -1);
    rig.assign(n, -1);
    int top = 0;
    std::vector<int> stk(n, 0);
    for (int u = 1; u < n; ++u) {
      if (as[stk[top]] > as[u]) {
        for (; top >= 1 && as[stk[top - 1]] > as[u]; --top) {
        }
        if (top == 0) {
          rt = par[lef[u] = stk[top]] = u;
        } else {
          par[lef[u] = stk[top]] = u;
          rig[par[u] = stk[top - 1]] = u;
        }
        stk[top] = u;
      } else {
        rig[par[u] = stk[top]] = u;
        stk[++top] = u;
      }
    }
  }
  template <class T> void build(const T &as) { build(as.size(), as.data()); }
};

/// @brief Cartesian tree where each node is the maximum of its subtree. Equal values prefer the leftmost.
struct max_cartesian_tree {
  int n, rt;
  std::vector<int> par, lef, rig;
  template <class T> void build(int n_, T *as) {
    assert(n_ >= 1);
    n = n_;
    rt = 0;
    par.assign(n, -1);
    lef.assign(n, -1);
    rig.assign(n, -1);
    int top = 0;
    std::vector<int> stk(n, 0);
    for (int u = 1; u < n; ++u) {
      if (as[stk[top]] < as[u]) {
        for (; top >= 1 && as[stk[top - 1]] < as[u]; --top) {
        }
        if (top == 0) {
          rt = par[lef[u] = stk[top]] = u;
        } else {
          par[lef[u] = stk[top]] = u;
          rig[par[u] = stk[top - 1]] = u;
        }
        stk[top] = u;
      } else {
        rig[par[u] = stk[top]] = u;
        stk[++top] = u;
      }
    }
  }
  template <class T> void build(const T &as) { build(as.size(), as.data()); }
};

} // namespace noya

#endif // NOYA_CARTESIAN_TREE_HPP

#include <cassert>
#include <vector>

/// @complexity Time: O(n).
/// Space: O(n).

namespace noya {

/// @brief Cartesian tree where each node is the minimum of its subtree. Equal values prefer the leftmost.
struct min_cartesian_tree {
  int n, rt;
  std::vector<int> par, lef, rig;
  template <class T> void build(int n_, T *as) {
    assert(n_ >= 1);
    n = n_;
    rt = 0;
    par.assign(n, -1);
    lef.assign(n, -1);
    rig.assign(n, -1);
    int top = 0;
    std::vector<int> stk(n, 0);
    for (int u = 1; u < n; ++u) {
      if (as[stk[top]] > as[u]) {
        for (; top >= 1 && as[stk[top - 1]] > as[u]; --top) {
        }
        if (top == 0) {
          rt = par[lef[u] = stk[top]] = u;
        } else {
          par[lef[u] = stk[top]] = u;
          rig[par[u] = stk[top - 1]] = u;
        }
        stk[top] = u;
      } else {
        rig[par[u] = stk[top]] = u;
        stk[++top] = u;
      }
    }
  }
  template <class T> void build(const T &as) { build(as.size(), as.data()); }
};

/// @brief Cartesian tree where each node is the maximum of its subtree. Equal values prefer the leftmost.
struct max_cartesian_tree {
  int n, rt;
  std::vector<int> par, lef, rig;
  template <class T> void build(int n_, T *as) {
    assert(n_ >= 1);
    n = n_;
    rt = 0;
    par.assign(n, -1);
    lef.assign(n, -1);
    rig.assign(n, -1);
    int top = 0;
    std::vector<int> stk(n, 0);
    for (int u = 1; u < n; ++u) {
      if (as[stk[top]] < as[u]) {
        for (; top >= 1 && as[stk[top - 1]] < as[u]; --top) {
        }
        if (top == 0) {
          rt = par[lef[u] = stk[top]] = u;
        } else {
          par[lef[u] = stk[top]] = u;
          rig[par[u] = stk[top - 1]] = u;
        }
        stk[top] = u;
      } else {
        rig[par[u] = stk[top]] = u;
        stk[++top] = u;
      }
    }
  }
  template <class T> void build(const T &as) { build(as.size(), as.data()); }
};

} // namespace noya