Cartesian-Tree (src/Misc/CartesianTree.hpp)

View this file on GitHub
View document part on GitHub
Last update: 2023-11-24 00:33:42+09:00
Include: #include "src/Misc/CartesianTree.hpp"

メンバ関数

名前	概要
`CartesianTree(Vec a, bool is_min)`	コンストラクタ. 配列 $(a_n)$ をもとに構築. `is_min` が `true` なら最小値, `false` なら最大値が親になるように構築. 極大長方形のアルゴリズム. 計算量は $O(N)$
`range(int i)`	次の条件を満たす半開区間 $\lbrack l, r)$ を返す. 1. $i \in \lbrace l,\dots,r-1\rbrace$ 2. $\min_{j \in \lbrace l,\dots,r-1\rbrace} \lbrace a_j \rbrace = a_i$ ( `is_min` が `true` の場合, `false` なら $\max$ ) 3. 極大. つまり $\min_{j \in \lbrace l-1,\dots,r-1\rbrace} \lbrace a_j \rbrace \neq a_i$ かつ $\min_{j \in \lbrace l,\dots,r\rbrace} \lbrace a_j \rbrace \neq a_i$ ( `is_min` が `true` の場合, `false` なら $\max$ )
`root()`	Cartesian-Treeの根を返す.
`parent(int i)`	Cartesian-Treeの頂点 $i$ の親を返す.
`children(int i)`	Cartesian-Treeの頂点 $i$ の子を返す. 二分木なので`array<int,2>` で返す. いない場合 $-1$.

Verify

AtCoder Beginner Contest 275 Ex - Monster(木上をdfs)

Required by

Suffix Tree (接尾辞木) (src/String/SuffixTree.hpp)

Verified with

Code

#pragma once
#include <vector>
#include <array>
class CartesianTree {
 std::vector<std::array<int, 2>> rg, ch;
 std::vector<int> par;
 int rt;
public:
 template <class Vec> CartesianTree(const Vec &a, bool is_min= 1): rg(a.size()), ch(a.size(), std::array{-1, -1}), par(a.size(), -1) {
  const int n= a.size();
  auto comp= [&](int l, int r) { return (is_min ? a[l] < a[r] : a[l] > a[r]) || (a[l] == a[r] && l < r); };
  int st[n], t= 0;
  for (int i= n; i--; rg[i][1]= (t ? st[t - 1] : n), st[t++]= i)
   while (t && comp(i, st[t - 1])) ch[i][1]= st[--t];
  for (int i= t= 0; i < n; rg[i][0]= (t ? st[t - 1] + 1 : 0), st[t++]= i++)
   while (t && comp(i, st[t - 1])) ch[i][0]= st[--t];
  for (int i= 0; i < n; ++i)
   for (int b= 2; b--;)
    if (ch[i][b] != -1) par[ch[i][b]]= i;
  for (int i= 0; i < n; ++i)
   if (par[i] == -1) rt= i;
 }
 std::array<int, 2> children(int i) const { return ch[i]; }
 int parent(int i) const { return par[i]; }
 int root() const { return rt; }
 // [l,r)
 std::array<int, 2> range(int i) const { return rg[i]; }
};

#line 2 "src/Misc/CartesianTree.hpp"
#include <vector>
#include <array>
class CartesianTree {
 std::vector<std::array<int, 2>> rg, ch;
 std::vector<int> par;
 int rt;
public:
 template <class Vec> CartesianTree(const Vec &a, bool is_min= 1): rg(a.size()), ch(a.size(), std::array{-1, -1}), par(a.size(), -1) {
  const int n= a.size();
  auto comp= [&](int l, int r) { return (is_min ? a[l] < a[r] : a[l] > a[r]) || (a[l] == a[r] && l < r); };
  int st[n], t= 0;
  for (int i= n; i--; rg[i][1]= (t ? st[t - 1] : n), st[t++]= i)
   while (t && comp(i, st[t - 1])) ch[i][1]= st[--t];
  for (int i= t= 0; i < n; rg[i][0]= (t ? st[t - 1] + 1 : 0), st[t++]= i++)
   while (t && comp(i, st[t - 1])) ch[i][0]= st[--t];
  for (int i= 0; i < n; ++i)
   for (int b= 2; b--;)
    if (ch[i][b] != -1) par[ch[i][b]]= i;
  for (int i= 0; i < n; ++i)
   if (par[i] == -1) rt= i;
 }
 std::array<int, 2> children(int i) const { return ch[i]; }
 int parent(int i) const { return par[i]; }
 int root() const { return rt; }
 // [l,r)
 std::array<int, 2> range(int i) const { return rg[i]; }
};