test/library_checker/tree/cartesian_tree.test.cpp

• View this file on GitHub
• Last update: 2024-10-31 23:51:11+09:00
• Problem: https://judge.yosupo.jp/problem/cartesian_tree

Depends on

• Cartesian Tree (デカルト木) (lib/graph/cartesian_tree.hpp)

Code

#define PROBLEM "https://judge.yosupo.jp/problem/cartesian_tree"
#include <bits/stdc++.h>
using namespace std;

#include "../../../lib/graph/cartesian_tree.hpp"

int main(){
    int n; cin >> n;
    vector<int> a(n);
    for(int i = 0; i < n; i++){
        cin >> a[i];
    }
    pair<vector<vector<int>>, int> ct = CartesianTree(a);
    auto [G, r] = ct;
    vector<int> ans(n);
    ans[r] = r;
    for(int i = 0; i < n; i++){
        for(auto x : G[i]){
            ans[x] = i;
        }
    }
    for(int i = 0; i < n; i++){
        cout << ans[i] << " \n"[i == n - 1];
    }
}

#line 1 "test/library_checker/tree/cartesian_tree.test.cpp"
#define PROBLEM "https://judge.yosupo.jp/problem/cartesian_tree"
#include <bits/stdc++.h>
using namespace std;

#line 2 "lib/graph/cartesian_tree.hpp"

/**
 * @brief Cartesian Tree (デカルト木)
 * @docs docs/graph/cartesian_tree.md
 */

#line 9 "lib/graph/cartesian_tree.hpp"
using namespace std;

template <typename T>
pair<vector<vector<int>>, int> CartesianTree(vector<T> &a){
    int n = a.size();
    vector<vector<int>> G(n);
    vector<int> par(n, -1), st;
    for(int i = 0; i < n; ++i){
        int prev = -1;
        while(!st.empty() && a[i] < a[st.back()]){
            prev = st.back();
            st.pop_back();
        }
        if(prev != -1){
            par[prev] = i;
        }
        if(!st.empty()){
            par[i] = st.back();
        }
        st.emplace_back(i);
    }
    int root = -1;
    for(int i = 0; i < n; ++i){
        if(par[i] != -1){
            G[par[i]].emplace_back(i);
        } else{
            root = i;
        }
    }
    return make_pair(G, root);
}
#line 6 "test/library_checker/tree/cartesian_tree.test.cpp"

int main(){
    int n; cin >> n;
    vector<int> a(n);
    for(int i = 0; i < n; i++){
        cin >> a[i];
    }
    pair<vector<vector<int>>, int> ct = CartesianTree(a);
    auto [G, r] = ct;
    vector<int> ans(n);
    ans[r] = r;
    for(int i = 0; i < n; i++){
        for(auto x : G[i]){
            ans[x] = i;
        }
    }
    for(int i = 0; i < n; i++){
        cout << ans[i] << " \n"[i == n - 1];
    }
}

Back to top page