proconlib

This documentation is automatically generated by competitive-verifier/competitive-verifier

View the Project on GitHub anqooqie/proconlib

:heavy_check_mark: tests/cartesian_tree/tree_based_interval.test.cpp

Depends on

Code

// competitive-verifier: STANDALONE
// Source: https://atcoder.jp/contests/abc407/tasks/abc407_f

#include <algorithm>
#include <functional>
#include <iostream>
#include <ranges>
#include <vector>
#include "tools/assert_that.hpp"
#include "tools/cartesian_tree.hpp"
#include "tools/second_order_imos.hpp"

using ll = long long;

std::vector<ll> solve(const std::vector<ll>& A) {
  const ll N = A.size();

  tools::cartesian_tree ct(A, std::greater<ll>{});
  tools::second_order_imos<ll> answers(N + 1);
  for (ll i = 0; i < N; ++i) {
    const auto& [l, r] = ct.get_vertex(i).tree_based_interval;
    const auto c = std::min(i - l + 1, r - i);
    answers.add(0, c, 0, A[i]);
    answers.add(c, r - l + 1 - c, c * A[i], 0);
    answers.add(r - l + 1 - c, r - l + 1, c * A[i], -A[i]);
  }

  return answers | std::views::drop(1) | std::ranges::to<std::vector>();
}

int main() {
  std::cin.tie(nullptr);
  std::ios_base::sync_with_stdio(false);

  assert_that(solve(std::vector<ll>{5, 3, 4, 2}) == std::vector<ll>{14, 13, 9, 5});
  assert_that(solve(std::vector<ll>{2, 0, 2, 5, 0, 5, 2, 4}) == std::vector<ll>{20, 28, 27, 25, 20, 15, 10, 5});  
  assert_that(solve(std::vector<ll>{9203973, 9141294, 9444773, 9292472, 5507634, 9599162, 497764, 430010, 4152216, 3574307, 430010}) == std::vector<ll>{61273615, 68960818, 69588453, 65590626, 61592799, 57594972, 47995810, 38396648, 28797486, 19198324, 9599162});

  return 0;
}

#line 1 "tests/cartesian_tree/tree_based_interval.test.cpp"
// competitive-verifier: STANDALONE
// Source: https://atcoder.jp/contests/abc407/tasks/abc407_f

#include <algorithm>
#include <functional>
#include <iostream>
#include <ranges>
#include <vector>
#line 1 "tools/assert_that.hpp"



#line 5 "tools/assert_that.hpp"
#include <cstdlib>

#define assert_that_impl(cond, file, line, func) do {\
  if (!cond) {\
    std::cerr << file << ':' << line << ": " << func << ": Assertion `" << #cond << "' failed." << '\n';\
    std::exit(EXIT_FAILURE);\
  }\
} while (false)
#define assert_that(...) assert_that_impl((__VA_ARGS__), __FILE__, __LINE__, __func__)


#line 1 "tools/cartesian_tree.hpp"



#include <cassert>
#line 6 "tools/cartesian_tree.hpp"
#include <iterator>
#include <stack>
#line 9 "tools/cartesian_tree.hpp"
#include <utility>
#line 1 "tools/getter_result.hpp"



#include <type_traits>

namespace tools {
  template <typename T, typename U>
  struct getter_result {
    using type = std::conditional_t<std::is_lvalue_reference_v<T>, const U&, U>;
  };

  template <typename T, typename U>
  using getter_result_t = typename tools::getter_result<T, U>::type;
}


#line 12 "tools/cartesian_tree.hpp"

namespace tools {
  class cartesian_tree {
  public:
    struct vertex {
      int parent;
      int left;
      int right;
      std::pair<int, int> value_based_interval;
      std::pair<int, int> tree_based_interval;
    };

  private:
    std::vector<vertex> m_vertices;

  public:
    cartesian_tree() = default;
    template <std::ranges::random_access_range R, typename Compare = std::ranges::less>
    requires std::indirect_strict_weak_order<Compare, std::ranges::iterator_t<R>>
    explicit cartesian_tree(R&& a, const Compare comp = {}) : m_vertices(std::ranges::distance(a)) {
      if (this->size() == 0) return;

      static constexpr int NONE = -1;
      const auto begin = std::ranges::begin(a);

      for (int i = 0; i < this->size(); ++i) {
        this->m_vertices[i].parent = i ? i - 1 : NONE;
        this->m_vertices[i].left = NONE;
        this->m_vertices[i].right = NONE;
        auto c = NONE;
        while (this->m_vertices[i].parent != NONE && std::invoke(comp, begin[i], begin[this->m_vertices[i].parent])) {
          if (c != NONE) {
            this->m_vertices[c].parent = this->m_vertices[i].parent;
          }
          c = this->m_vertices[i].parent;

          const auto gp = this->m_vertices[this->m_vertices[i].parent].parent;
          this->m_vertices[this->m_vertices[i].parent].parent = i;
          this->m_vertices[i].parent = gp;
        }
      }

      auto root = NONE;
      for (int i = 0; i < this->size(); ++i) {
        const auto p = this->m_vertices[i].parent;
        if (p == NONE) {
          root = i;
        } else {
          if (p < i) {
            this->m_vertices[p].right = i;
          } else {
            this->m_vertices[p].left = i;
          }
        }
      }

      std::vector<int> strict_left(this->size());
      strict_left[root] = 0;
      this->m_vertices[root].value_based_interval = this->m_vertices[root].tree_based_interval = std::make_pair(0, this->size());
      std::stack<int> stack;
      stack.push(root);
      while (!stack.empty()) {
        const auto here = stack.top();
        stack.pop();
        const auto& v = this->m_vertices[here];
        if (v.right != NONE) {
          strict_left[v.right] = here + 1;
          this->m_vertices[v.right].value_based_interval = std::make_pair(
            std::invoke(comp, begin[here], begin[v.right]) ? strict_left[v.right] : this->m_vertices[here].value_based_interval.first,
            this->m_vertices[here].value_based_interval.second
          );
          this->m_vertices[v.right].tree_based_interval = std::make_pair(
            strict_left[v.right],
            this->m_vertices[here].tree_based_interval.second
          );
          stack.push(v.right);
        }
        if (v.left != NONE) {
          strict_left[v.left] = strict_left[here];
          this->m_vertices[v.left].value_based_interval = this->m_vertices[v.left].tree_based_interval = std::make_pair(strict_left[v.left], here);
          stack.push(v.left);
        }
      }
    }
    template <std::ranges::input_range R, typename Compare = std::ranges::less>
    requires (std::indirect_strict_weak_order<Compare, typename std::vector<std::ranges::range_value_t<R>>::iterator> && !std::ranges::random_access_range<R>)
    explicit cartesian_tree(R&& a, const Compare comp = {}) : cartesian_tree(std::forward<R>(a) | std::ranges::to<std::vector>(), comp) {
    }

    int size() const {
      return this->m_vertices.size();
    }
    auto get_vertex(this auto&& self, const int i) -> tools::getter_result_t<decltype(self), vertex> {
      assert(0 <= i && i < self.size());
      return std::forward_like<decltype(self)>(self.m_vertices[i]);
    }
    auto vertices(this auto&& self) -> tools::getter_result_t<decltype(self), std::vector<vertex>> {
      return std::forward_like<decltype(self)>(self.m_vertices);
    }
  };
}


#line 1 "tools/second_order_imos.hpp"



#line 5 "tools/second_order_imos.hpp"
#include <compare>
#include <cstddef>
#line 1 "tools/non_bool_integral.hpp"



#include <concepts>
#line 1 "tools/integral.hpp"



#line 1 "tools/is_integral.hpp"



#line 5 "tools/is_integral.hpp"

namespace tools {
  template <typename T>
  struct is_integral : std::is_integral<T> {};

  template <typename T>
  inline constexpr bool is_integral_v = tools::is_integral<T>::value;
}


#line 5 "tools/integral.hpp"

namespace tools {
  template <typename T>
  concept integral = tools::is_integral_v<T>;
}


#line 7 "tools/non_bool_integral.hpp"

namespace tools {
  template <typename T>
  concept non_bool_integral = tools::integral<T> && !std::same_as<std::remove_cv_t<T>, bool>;
}


#line 10 "tools/second_order_imos.hpp"

namespace tools {
  template <tools::non_bool_integral T>
  class second_order_imos {
    std::vector<T> m_vector;
    std::vector<T> m_diffs2;
    int m_processed;

  public:
    class iterator {
      second_order_imos<T> *m_parent;
      std::size_t m_i;

    public:
      using reference = const T&;
      using value_type = T;
      using difference_type = std::ptrdiff_t;
      using pointer = const T*;
      using iterator_category = std::random_access_iterator_tag;

      iterator() = default;
      iterator(second_order_imos<T> * const parent, const std::size_t i) : m_parent(parent), m_i(i) {
      }

      reference operator*() const {
        return (*this->m_parent)[this->m_i];
      }
      pointer operator->() const {
        return &(*(*this));
      }

      iterator& operator++() {
        ++this->m_i;
        return *this;
      }
      iterator operator++(int) {
        const auto self = *this;
        ++*this;
        return self;
      }
      iterator& operator--() {
        --this->m_i;
        return *this;
      }
      iterator operator--(int) {
        const auto self = *this;
        --*this;
        return self;
      }
      iterator& operator+=(const difference_type n) {
        this->m_i += n;
        return *this;
      }
      iterator& operator-=(const difference_type n) {
        this->m_i -= n;
        return *this;
      }
      friend iterator operator+(const iterator self, const difference_type n) {
        return iterator(self.m_parent, self.m_i + n);
      }
      friend iterator operator+(const difference_type n, const iterator self) {
        return self + n;
      }
      friend iterator operator-(const iterator self, const difference_type n) {
        return iterator(self.m_parent, self.m_i - n);
      }
      friend difference_type operator-(const iterator lhs, const iterator rhs) {
        assert(lhs.m_parent == rhs.m_parent);
        return static_cast<difference_type>(lhs.m_i) - static_cast<difference_type>(rhs.m_i);
      }
      reference operator[](const difference_type n) const {
        return *(*this + n);
      }

      friend std::strong_ordering operator<=>(const iterator lhs, const iterator rhs) {
        assert(lhs.m_parent == rhs.m_parent);
        return lhs.m_i <=> rhs.m_i;
      }
      friend bool operator==(const iterator lhs, const iterator rhs) {
        assert(lhs.m_parent == rhs.m_parent);
        return lhs.m_i == rhs.m_i;
      }
    };

    second_order_imos() : second_order_imos(0) {
    }
    second_order_imos(const int n) : m_vector(n, 0), m_diffs2(n + 2, 0), m_processed(0) {
    }

    int size() const {
      return this->m_vector.size();
    }
    const T& operator[](const int i) {
      assert(0 <= i && i < this->size());
      auto& j = this->m_processed;
      do {
        if (i < j) break;
        if (j == 0) {
          this->m_vector[j] = this->m_diffs2[j];
          ++j;
          if (i < j) break;
        }
        if (j == 1) {
          this->m_vector[j] = this->m_diffs2[j] + 2 * this->m_vector[j - 1];
          ++j;
          if (i < j) break;
        }
        do {
          this->m_vector[j] = this->m_diffs2[j] + 2 * this->m_vector[j - 1] - this->m_vector[j - 2];
          ++j;
        } while (j <= i);
      } while (false);
      return this->m_vector[i];
    }

    iterator begin() { return iterator(this, 0); }
    iterator end() { return iterator(this, this->size()); }
    std::reverse_iterator<iterator> rbegin() { return std::make_reverse_iterator(this->end()); }
    std::reverse_iterator<iterator> rend() { return std::make_reverse_iterator(this->begin()); }

    void add(const int l, const int r, const T a, const T d) {
      assert(0 <= l && l <= r && r <= this->size());
      assert(this->m_processed <= l);
      this->m_diffs2[l] += a;
      this->m_diffs2[l + 1] += d - a;
      this->m_diffs2[r] -= a + (r - l) * d;
      this->m_diffs2[r + 1] += a + (r - l - 1) * d;
    }
  };
}


#line 12 "tests/cartesian_tree/tree_based_interval.test.cpp"

using ll = long long;

std::vector<ll> solve(const std::vector<ll>& A) {
  const ll N = A.size();

  tools::cartesian_tree ct(A, std::greater<ll>{});
  tools::second_order_imos<ll> answers(N + 1);
  for (ll i = 0; i < N; ++i) {
    const auto& [l, r] = ct.get_vertex(i).tree_based_interval;
    const auto c = std::min(i - l + 1, r - i);
    answers.add(0, c, 0, A[i]);
    answers.add(c, r - l + 1 - c, c * A[i], 0);
    answers.add(r - l + 1 - c, r - l + 1, c * A[i], -A[i]);
  }

  return answers | std::views::drop(1) | std::ranges::to<std::vector>();
}

int main() {
  std::cin.tie(nullptr);
  std::ios_base::sync_with_stdio(false);

  assert_that(solve(std::vector<ll>{5, 3, 4, 2}) == std::vector<ll>{14, 13, 9, 5});
  assert_that(solve(std::vector<ll>{2, 0, 2, 5, 0, 5, 2, 4}) == std::vector<ll>{20, 28, 27, 25, 20, 15, 10, 5});  
  assert_that(solve(std::vector<ll>{9203973, 9141294, 9444773, 9292472, 5507634, 9599162, 497764, 430010, 4152216, 3574307, 430010}) == std::vector<ll>{61273615, 68960818, 69588453, 65590626, 61592799, 57594972, 47995810, 38396648, 28797486, 19198324, 9599162});

  return 0;
}
Back to top page