test/larsch.test.cpp

• View this file on GitHub
• Last update: 2021-04-07 08:01:56+09:00
• Problem: http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=3086

Depends on

• LARSCH Algorithm (algorithm/larsch.cpp)
• Segment Tree (data_structure/segment_tree.cpp)
• other/fast_ios.cpp
• other/int_alias.cpp
• other/less_equal_ordered_set.cpp
• other/min_semigroup.cpp
• other/opposite_ordered_set.cpp
• other/semigroup_to_monoid.cpp

Code

#define PROBLEM "http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=3086"

#include "algorithm/larsch.cpp"
#include "data_structure/segment_tree.cpp"
#include "other/int_alias.cpp"
#include "other/less_equal_ordered_set.cpp"
#include "other/min_semigroup.cpp"
#include "other/opposite_ordered_set.cpp"
#include "other/semigroup_to_monoid.cpp"

#include <iostream>
#include <limits>

int main() {
#include "other/fast_ios.cpp"

  static constexpr i64 inf = std::numeric_limits<i64>::max() / 2;

  usize n, l;
  std::cin >> n >> l;

  segment_tree<semigroup_to_monoid<
      min_semigroup<opposite_ordered_set<less_equal_ordered_set<i64>>>>>
      seg(n);
  for (usize i = 0; i != n; ++i) {
    i64 a;
    std::cin >> a;
    seg.update(i, a);
  }

  std::vector<i64> dp(n + 1);
  dp[0] = 0;

  const auto f = [&](const usize to_, const usize from) -> i64 {
    const usize to = to_ + 1;
    if (to - from < l) {
      return -inf;
    } else {
      return dp[from] + *seg.fold(from, to);
    }
  };

  larsch<i64> larsch_(n, [&](int i, int j) { return -f(i, j); });
  for (usize i = 0; i != n; i += 1) {
    dp[i + 1] = f(i, larsch_.get_argmin());
  }

  std::cout << dp[n] << "\n";

  return 0;
}

#line 1 "test/larsch.test.cpp"
#define PROBLEM "http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=3086"

#line 1 "algorithm/larsch.cpp"
#include <functional>
#include <memory>
#include <vector>

template <class T> class larsch {
  struct reduce_row;
  struct reduce_col;

  struct reduce_row {
    int n;
    std::function<T(int, int)> f;
    int cur_row;
    int state;
    std::unique_ptr<reduce_col> rec;

    reduce_row(int n_) : n(n_), f(), cur_row(0), state(0), rec() {
      const int m = n / 2;
      if (m != 0) {
        rec = std::make_unique<reduce_col>(m);
      }
    }

    void set_f(std::function<T(int, int)> f_) {
      f = f_;
      if (rec) {
        rec->set_f([&](int i, int j) -> T { return f(2 * i + 1, j); });
      }
    }

    int get_argmin() {
      const int cur_row_ = cur_row;
      cur_row += 1;
      if (cur_row_ % 2 == 0) {
        const int prev_argmin = state;
        const int next_argmin = [&]() {
          if (cur_row_ + 1 == n) {
            return n - 1;
          } else {
            return rec->get_argmin();
          }
        }();
        state = next_argmin;
        int ret = prev_argmin;
        for (int j = prev_argmin + 1; j <= next_argmin; j += 1) {
          if (f(cur_row_, ret) > f(cur_row_, j)) {
            ret = j;
          }
        }
        return ret;
      } else {
        if (f(cur_row_, state) <= f(cur_row_, cur_row_)) {
          return state;
        } else {
          return cur_row_;
        }
      }
    }
  };

  struct reduce_col {
    int n;
    std::function<T(int, int)> f;
    int cur_row;
    std::vector<int> cols;
    reduce_row rec;

    reduce_col(int n_) : n(n_), f(), cur_row(0), cols(), rec(n) {}

    void set_f(std::function<T(int, int)> f_) {
      f = f_;
      rec.set_f([&](int i, int j) -> T { return f(i, cols[j]); });
    }

    int get_argmin() {
      const int cur_row_ = cur_row;
      cur_row += 1;
      const auto cs = [&]() -> std::vector<int> {
        if (cur_row_ == 0) {
          return {{0}};
        } else {
          return {{2 * cur_row_ - 1, 2 * cur_row_}};
        }
      }();
      for (const int j : cs) {
        while ([&]() {
          const int size = cols.size();
          return size != cur_row_ && f(size - 1, cols.back()) > f(size - 1, j);
        }()) {
          cols.pop_back();
        }
        if (cols.size() != n) {
          cols.push_back(j);
        }
      }
      return cols[rec.get_argmin()];
    }
  };

  std::unique_ptr<reduce_row> base;

public:
  larsch(int n, std::function<T(int, int)> f)
      : base(std::make_unique<reduce_row>(n)) {
    base->set_f(f);
  }

  int get_argmin() { return base->get_argmin(); }
};

/**
 * @brief LARSCH Algorithm
 * @docs docs/larsch.md
 */
#line 2 "other/int_alias.cpp"

#include <cstddef>
#include <cstdint>

using i32 = std::int32_t;
using i64 = std::int64_t;
using u32 = std::uint32_t;
using u64 = std::uint64_t;
using isize = std::ptrdiff_t;
using usize = std::size_t;
#line 2 "data_structure/segment_tree.cpp"

#include <cassert>
#line 6 "data_structure/segment_tree.cpp"

template <class M> class segment_tree {
  using T = typename M::value_type;

public:
  using value_type = T;

private:
  std::vector<T> tree;

  template <class F>
  usize search_subtree(usize index, const F f, T fold_l) const {
    while (index < size()) {
      const T temp = M::operation(fold_l, tree[index * 2]);
      if (!f(temp)) {
        index = index * 2;
      } else {
        fold_l = temp;
        index = index * 2 + 1;
      }
    }
    return index - size();
  }

public:
  segment_tree() = default;

  explicit segment_tree(const usize n) : tree(n * 2, M::identity) {}

  usize size() const noexcept { return tree.size() / 2; }

  T fold(usize first, usize last) const {
    assert(first <= last);
    assert(last <= size());
    first += size();
    last += size();
    T fold_l = M::identity;
    T fold_r = M::identity;
    while (first != last) {
      if (first % 2 != 0) {
        fold_l = M::operation(fold_l, tree[first]);
        first += 1;
      }
      first /= 2;
      if (last % 2 != 0) {
        last -= 1;
        fold_r = M::operation(tree[last], fold_r);
      }
      last /= 2;
    }
    return M::operation(fold_l, fold_r);
  }
  
  template <class F> usize search(usize first, usize last, const F f) const {
    assert(first <= last);
    assert(last <= size());
    first += size();
    last += size();
    const usize last_cp = last;
    usize shift = 0;
    T fold_l = M::identity;
    while (first != last) {
      if (first % 2 != 0) {
        const T temp = M::operation(fold_l, tree[first]);
        if (!f(temp))
          return search_subtree(first, f, fold_l);
        fold_l = temp;
        first += 1;
      }
      first /= 2;
      last /= 2;
      shift += 1;
    }
    while (shift != 0) {
      shift -= 1;
      last = last_cp >> shift;
      if (last % 2 != 0) {
        last -= 1;
        const T temp = M::operation(fold_l, tree[last]);
        if (!f(temp))
          return search_subtree(last, f, fold_l);
        fold_l = temp;
      }
    }
    return last_cp - size();
  }

  void update(usize index, const T x) {
    assert(index < size());
    index += size();
    tree[index] = x;
    while (index != 1) {
      index /= 2;
      tree[index] = M::operation(tree[index * 2], tree[index * 2 + 1]);
    }
  }
};

/**
 * @brief Segment Tree
 * @docs docs/segment_tree.md
 * @see https://scrapbox.io/data-structures/Segment_Tree
 */
#line 1 "other/less_equal_ordered_set.cpp"
template <class T> class less_equal_ordered_set {
public:
  using value_type = T;
  static constexpr bool compare(const T &x, const T &y) noexcept {
    return x <= y;
  }
};
#line 1 "other/min_semigroup.cpp"
template <class W> class min_semigroup {
  using T = typename W::value_type;

public:
  using value_type = T;
  static constexpr T operation(const T &l, const T &r) noexcept {
    return W::compare(l, r) ? l : r;
  }
};
#line 1 "other/opposite_ordered_set.cpp"
template <class W> class opposite_ordered_set {
  using T = typename W::value_type;

public:
  using value_type = T;
  static constexpr bool compare(const T &l, const T &r) noexcept {
    return W::compare(r, l);
  }
};
#line 1 "other/semigroup_to_monoid.cpp"
#include <optional>
#include <utility>

template <class S> class semigroup_to_monoid {
  using T = std::optional<typename S::value_type>;

public:
  using value_type = T;
  static constexpr T operation(const T &l, const T &r) noexcept {
    if (!l)
      return r;
    if (!r)
      return l;
    return T(std::in_place, S::operation(*l, *r));
  }
  static constexpr T identity{std::nullopt};
};
#line 10 "test/larsch.test.cpp"

#include <iostream>
#include <limits>

int main() {
#line 1 "other/fast_ios.cpp"
std::ios::sync_with_stdio(false);
std::cin.tie(nullptr);
#line 16 "test/larsch.test.cpp"

  static constexpr i64 inf = std::numeric_limits<i64>::max() / 2;

  usize n, l;
  std::cin >> n >> l;

  segment_tree<semigroup_to_monoid<
      min_semigroup<opposite_ordered_set<less_equal_ordered_set<i64>>>>>
      seg(n);
  for (usize i = 0; i != n; ++i) {
    i64 a;
    std::cin >> a;
    seg.update(i, a);
  }

  std::vector<i64> dp(n + 1);
  dp[0] = 0;

  const auto f = [&](const usize to_, const usize from) -> i64 {
    const usize to = to_ + 1;
    if (to - from < l) {
      return -inf;
    } else {
      return dp[from] + *seg.fold(from, to);
    }
  };

  larsch<i64> larsch_(n, [&](int i, int j) { return -f(i, j); });
  for (usize i = 0; i != n; i += 1) {
    dp[i + 1] = f(i, larsch_.get_argmin());
  }

  std::cout << dp[n] << "\n";

  return 0;
}

Back to top page