data_structure/cartesian_tree.hpp

• View this file on GitHub
• Last update: 2023-12-26 16:56:23+09:00
• Include: #include "data_structure/cartesian_tree.hpp"

Verified with

• data_structure/test/cartesian_tree.test.cpp

Code

#pragma once

#include <vector>

template <typename T, typename Compare = std::less<T>>
std::vector<int> cartesian_tree(const std::vector<T> &a, Compare comp = Compare()) {
    std::vector<int> stc;
    std::vector<int> par(a.size(), -1);
    for (int i = 0; i < a.size(); ++i) {
        while (stc.size() >= 2 && comp(a[i], a[stc.back()])) {
            if (comp(a[i], a[stc[stc.size() - 2]])) {
                par[stc.back()] = stc[stc.size() - 2];
            } else {
                par[stc.back()] = i;
            }
            stc.pop_back();
        }
        if (stc.size() == 1 && comp(a[i], a[stc.back()])) {
            par[stc.back()] = i;
            stc.pop_back();
        }
        stc.push_back(i);
    }
    while (stc.size() >= 2) {
        par[stc.back()] = stc[stc.size() - 2];
        stc.pop_back();
    }
    return par;
}

#line 2 "data_structure/cartesian_tree.hpp"

#include <vector>

template <typename T, typename Compare = std::less<T>>
std::vector<int> cartesian_tree(const std::vector<T> &a, Compare comp = Compare()) {
    std::vector<int> stc;
    std::vector<int> par(a.size(), -1);
    for (int i = 0; i < a.size(); ++i) {
        while (stc.size() >= 2 && comp(a[i], a[stc.back()])) {
            if (comp(a[i], a[stc[stc.size() - 2]])) {
                par[stc.back()] = stc[stc.size() - 2];
            } else {
                par[stc.back()] = i;
            }
            stc.pop_back();
        }
        if (stc.size() == 1 && comp(a[i], a[stc.back()])) {
            par[stc.back()] = i;
            stc.pop_back();
        }
        stc.push_back(i);
    }
    while (stc.size() >= 2) {
        par[stc.back()] = stc[stc.size() - 2];
        stc.pop_back();
    }
    return par;
}

Back to top page