CompetitiveProgrammingCpp

This documentation is automatically generated by online-judge-tools/verification-helper

View the Project on GitHub

:heavy_check_mark: Test/DataStructure/SegmentTree_minleft.test.cpp

Depends on

Code

#define PROBLEM "https://yukicoder.me/problems/no/1435"

#include <algorithm>

#include <iostream>

#include <ranges>

#include <vector>


// begin:tag includes

#include "./../../Library/DataStructure/SegmentTree.hpp"

// end:tag includes


using ll = long long;

struct T {
  ll min1, min2, max;
  constexpr T(ll _min1, ll _min2, ll _max)
      : min1(_min1), min2(_min2), max(_max) {}
};
auto op = [](const T& a, const T& b) {
  std::vector<ll> v{a.min1, a.min2, b.min1, b.min2};
  std::ranges::sort(v);
  return T(v[0], v[1], std::max(a.max, b.max));
};
constexpr T e{1LL << 60, 1LL << 60, -(1LL << 60)};
using M = mtd::Monoid<T, e, decltype(op)>;

signed main() {
  std::cin.tie(0);
  std::ios::sync_with_stdio(0);

  int n;
  std::cin >> n;
  std::vector<ll> a(n);
  for (auto i : std::views::iota(0, n)) { std::cin >> a[i]; }

  auto segtree = mtd::SegmentTree<M>(n);
  for (auto i : std::views::iota(0, n)) {
    segtree.update(i, T(a[i], 1LL << 60, a[i]));
  }

  ll ans = 0;
  for (auto r : std::views::iota(0, n)) {
    auto l = segtree.min_left(r, [](const M& m) {
      auto [min1, min2, max] = m.m_val;
      return max <= min1 + min2;
    });
    ans += r - l;
  }
  std::cout << ans << std::endl;
}
#line 1 "Test/DataStructure/SegmentTree_minleft.test.cpp"
#define PROBLEM "https://yukicoder.me/problems/no/1435"

#include <algorithm>

#include <iostream>

#include <ranges>

#include <vector>


// begin:tag includes

#line 2 "Library/DataStructure/SegmentTree.hpp"

#include <deque>

#line 5 "Library/DataStructure/SegmentTree.hpp"
#include <utility>

#line 7 "Library/DataStructure/SegmentTree.hpp"

#line 2 "Library/Algebraic/Monoid.hpp"

#line 4 "Library/Algebraic/Monoid.hpp"

namespace mtd {

  template <class S,    // set
            S element,  // identity element
            class op    // binary operation
            >
  requires std::is_invocable_r_v<S, op, S, S>
  struct Monoid {
    using value_type = S;
    constexpr static S _element = element;
    using op_type = op;

    S m_val;
    constexpr Monoid(S val) : m_val(val) {}
    constexpr Monoid() : Monoid(element) {}
    constexpr Monoid binaryOperation(const Monoid& m2) const {
      return op()(m_val, m2.m_val);
    }
    friend std::ostream& operator<<(std::ostream& os,
                                    const Monoid<S, element, op>& m) {
      return os << m.m_val;
    }
  };

  namespace __detail {
    template <typename T, template <typename, auto, typename> typename S>
    concept is_monoid_specialization_of = requires {
      typename std::enable_if_t<std::is_same_v<
          T, S<typename T::value_type, T::_element, typename T::op_type>>>;
    };
  }  // namespace __detail

  template <typename M>
  concept monoid = __detail::is_monoid_specialization_of<M, Monoid>;

}  // namespace mtd
#line 9 "Library/DataStructure/SegmentTree.hpp"

namespace mtd {

  template <monoid Monoid>
  class SegmentTree {
  private:
    const int m_size;
    std::vector<Monoid> m_node;
    using S = decltype(Monoid().m_val);

    constexpr int calcSize(int n) const {
      int size = 1;
      while (size < n) { size <<= 1; }
      return size;
    }

    template <class Lambda>
    constexpr auto _update_op(int itr, Monoid&& val, const Lambda& op) {
      int i = itr + m_size - 1;
      m_node[i] = op(m_node[i], std::forward<decltype(val)>(val));
      while (i) {
        i = (i - 1) >> 1;
        m_node[i] = m_node[(i << 1) | 1].binaryOperation(m_node[(i + 1) << 1]);
      }
    }

    constexpr auto _query(int _l, int _r) const {
      auto l = std::max(_l, 0) + m_size;
      auto r = std::min(_r, m_size - 1) + m_size;
      auto lm = Monoid();
      auto rm = Monoid();
      while (l <= r) {
        if (l & 1) {
          lm = lm.binaryOperation(m_node[l - 1]);
          ++l;
        }
        if (!(r & 1)) {
          rm = m_node[r - 1].binaryOperation(rm);
          --r;
        }
        l >>= 1, r >>= 1;
      }
      return lm.binaryOperation(rm);
    }

    constexpr auto _construct(const std::vector<S>& vec) {
      for (unsigned int i = 0; i < vec.size(); ++i) {
        m_node[i + m_size - 1] = Monoid(vec[i]);
      }
      for (int i = m_size - 2; i >= 0; --i) {
        m_node[i] = m_node[(i << 1) | 1].binaryOperation(m_node[(i + 1) << 1]);
      }
    }

  public:
    SegmentTree(int n) : m_size(calcSize(n)), m_node((m_size << 1) - 1) {}
    SegmentTree(int n, const std::vector<S>& vec) : SegmentTree(n) {
      _construct(vec);
    }

    template <class Lambda>
    constexpr auto update_op(int itr, Monoid&& val, const Lambda& op) {
      return _update_op(itr, std::forward<Monoid>(val), op);
    }
    constexpr auto update(int itr, Monoid&& val) {
      return update_op(itr, std::forward<Monoid>(val),
                       [](const Monoid&, const Monoid& m2) { return m2; });
    }
    constexpr auto add(int itr, Monoid&& val) {
      return update_op(itr, std::forward<Monoid>(val),
                       [](const Monoid& m1, const Monoid& m2) {
                         return Monoid(m1.m_val + m2.m_val);
                       });
    }
    constexpr auto query(int l, int r) const { return _query(l, r).m_val; }
    constexpr auto query_all() const { return m_node[0].m_val; }

    /*
     * f([l, r]) = true となる最大のr
     * judge: (Monoid) -> bool
     **/
    template <class F>
    constexpr auto max_right(int _l, const F& judge) const {
      if (!judge(Monoid())) {
        throw std::runtime_error("SegmentTree.max_right.judge(e) must be true");
      }
      auto l = std::max(_l, 0) + m_size;
      auto r = 2 * m_size - 1;
      auto lm = Monoid();
      while (l <= r) {
        if (l & 1) {
          auto next = lm.binaryOperation(m_node[l - 1]);
          if (!judge(next)) {
            auto itr = l;
            while (itr < m_size) {
              auto litr = 2 * itr;
              auto ritr = 2 * itr + 1;
              auto lval = lm.binaryOperation(m_node[litr - 1]);
              if (!judge(lval)) {
                itr = litr;
              } else {
                itr = ritr;
                std::swap(lm, lval);
              }
            }
            return itr - m_size - 1;
          }
          std::swap(lm, next);
          ++l;
        }
        l >>= 1, r >>= 1;
      }
      return m_size - 1;
    }

    /*
     * f([l, r]) = true となる最小のl
     * judge: (Monoid) -> bool
     **/
    template <class F>
    constexpr auto min_left(int _r, const F& judge) const {
      if (!judge(Monoid())) {
        throw std::runtime_error("SegmentTree.min_left.judge(e) must be true");
      }
      auto l = m_size;
      auto r = std::min(_r, m_size - 1) + m_size;
      auto rm = Monoid();
      while (l <= r) {
        if (l & 1) { ++l; }
        if (!(r & 1) || (_r == m_size - 1 && r == 1)) {
          auto next = m_node[r - 1].binaryOperation(rm);
          if (!judge(next)) {
            auto itr = r;
            while (itr < m_size) {
              auto litr = 2 * itr;
              auto ritr = 2 * itr + 1;
              auto rval = m_node[ritr - 1].binaryOperation(rm);
              if (!judge(rval)) {
                itr = ritr;
              } else {
                itr = litr;
                std::swap(rm, rval);
              }
            }
            return itr - m_size + 1;
          }
          std::swap(rm, next);
          --r;
        }
        l >>= 1, r >>= 1;
      }
      return 0;
    }

    constexpr auto debug() const {
      for (int i = 0; i < m_size; ++i) {
        std::cout << m_node[m_size + i - 1] << " ";
      }
      std::cout << std::endl;
    }
  };

}  // namespace mtd

#line 10 "Test/DataStructure/SegmentTree_minleft.test.cpp"
// end:tag includes


using ll = long long;

struct T {
  ll min1, min2, max;
  constexpr T(ll _min1, ll _min2, ll _max)
      : min1(_min1), min2(_min2), max(_max) {}
};
auto op = [](const T& a, const T& b) {
  std::vector<ll> v{a.min1, a.min2, b.min1, b.min2};
  std::ranges::sort(v);
  return T(v[0], v[1], std::max(a.max, b.max));
};
constexpr T e{1LL << 60, 1LL << 60, -(1LL << 60)};
using M = mtd::Monoid<T, e, decltype(op)>;

signed main() {
  std::cin.tie(0);
  std::ios::sync_with_stdio(0);

  int n;
  std::cin >> n;
  std::vector<ll> a(n);
  for (auto i : std::views::iota(0, n)) { std::cin >> a[i]; }

  auto segtree = mtd::SegmentTree<M>(n);
  for (auto i : std::views::iota(0, n)) {
    segtree.update(i, T(a[i], 1LL << 60, a[i]));
  }

  ll ans = 0;
  for (auto r : std::views::iota(0, n)) {
    auto l = segtree.min_left(r, [](const M& m) {
      auto [min1, min2, max] = m.m_val;
      return max <= min1 + min2;
    });
    ans += r - l;
  }
  std::cout << ans << std::endl;
}
Back to top page