test/yukicoder/776/main.test.cpp

• View this file on GitHub
• Last update: 2021-04-23 23:44:44+09:00
• Problem: https://yukicoder.me/problems/no/776
• Link: View error logs on GitHub Actions

Depends on

• Max partial sum monoid (Mylib/AlgebraicStructure/Monoid/max_partial_sum.cpp)
• Segment tree (Mylib/DataStructure/SegmentTree/segment_tree.cpp)
• Input tuple (Mylib/IO/input_tuple.cpp)
• Input tuples (Mylib/IO/input_tuples.cpp)
• Input vector (Mylib/IO/input_vector.cpp)

Code

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

#include <algorithm>
#include <climits>
#include <iostream>
#include <string>
#include <vector>
#include "Mylib/AlgebraicStructure/Monoid/max_partial_sum.cpp"
#include "Mylib/DataStructure/SegmentTree/segment_tree.cpp"
#include "Mylib/IO/input_tuples.cpp"
#include "Mylib/IO/input_vector.cpp"

namespace hl = haar_lib;

using M = hl::max_partial_sum_monoid<int64_t>;

int main() {
  int N, Q;
  std::cin >> N >> Q;

  hl::segment_tree<M> seg(N);

  auto a = hl::input_vector<int64_t>(N);
  for (int i = 0; i < N; ++i) {
    seg.set(i, M::max_partial_sum(a[i]));
  }

  for (auto [type] : hl::input_tuples<std::string>(Q)) {
    if (type == "set") {
      int i, x;
      std::cin >> i >> x;
      --i;
      seg.set(i, M::max_partial_sum(x));
      a[i] = x;
    } else {
      int l1, l2, r1, r2;
      std::cin >> l1 >> l2 >> r1 >> r2;
      --l1, --l2, --r1, --r2;

      r1 = std::max(l1, r1);
      l2 = std::min(l2, r2);

      int64_t ans = LLONG_MIN;

      auto f =
          [&](int L1, int L2, int R1, int R2) {
            auto ret =
                seg.fold(L1, L2 + 1).value_or(M::max_partial_sum(0)).right_max +
                seg.fold(std::min(L2 + 1, R1), R1).value_or(M::max_partial_sum(0)).sum +
                seg.fold(R1, R2 + 1).value_or(M::max_partial_sum(0)).left_max;

            if (L2 == R1) ret -= a[L2];

            return ret;
          };

      if (l2 <= r1) {
        ans = f(l1, l2, r1, r2);
      } else {
        if (l1 <= r1) ans = std::max(ans, f(l1, r1, r1, r2));
        if (l2 <= r2) ans = std::max(ans, f(l1, l2, l2, r2));
        if (r1 <= l2) ans = std::max(ans, seg.fold(r1, l2 + 1)->partial_max);
      }

      std::cout << ans << "\n";
    }
  }

  return 0;
}

#line 1 "test/yukicoder/776/main.test.cpp"
#define PROBLEM "https://yukicoder.me/problems/no/776"

#include <algorithm>
#include <climits>
#include <iostream>
#include <string>
#include <vector>
#line 4 "Mylib/AlgebraicStructure/Monoid/max_partial_sum.cpp"
#include <optional>

namespace haar_lib {
  namespace max_partial_sum_monoid_impl {
    template <typename T>
    struct max_partial_sum {
      T sum, left_max, right_max, partial_max;
      max_partial_sum() {}
      max_partial_sum(T x) : sum(x), left_max(x), right_max(x), partial_max(x) {}
      max_partial_sum(T sum, T left_max, T right_max, T partial_max) : sum(sum), left_max(left_max), right_max(right_max), partial_max(partial_max) {}

      friend std::ostream &operator<<(std::ostream &s, const max_partial_sum &a) {
        s << "("
          << "sum: " << a.sum << ", "
          << "left_max: " << a.left_max << ", "
          << "right_max: " << a.right_max << ", "
          << "partial_max: " << a.partial_max << ")";
        return s;
      }
    };
  }  // namespace max_partial_sum_monoid_impl

  template <typename T>
  struct max_partial_sum_monoid {
    using max_partial_sum = max_partial_sum_monoid_impl::max_partial_sum<T>;
    using value_type      = std::optional<max_partial_sum>;

    value_type operator()() const {
      return std::nullopt;
    }

    value_type operator()(const value_type &a, const value_type &b) const {
      if (not a) return b;
      if (not b) return a;

      return max_partial_sum(
          a->sum + b->sum,
          std::max(a->left_max, a->sum + std::max(b->left_max, b->sum)),
          std::max(b->right_max, b->sum + std::max(a->right_max, a->sum)),
          std::max({a->partial_max, b->partial_max, a->right_max + b->left_max}));
    }
  };
}  // namespace haar_lib
#line 3 "Mylib/DataStructure/SegmentTree/segment_tree.cpp"
#include <cassert>
#include <functional>
#line 6 "Mylib/DataStructure/SegmentTree/segment_tree.cpp"

namespace haar_lib {
  template <typename Monoid>
  class segment_tree {
  public:
    using value_type = typename Monoid::value_type;

  private:
    Monoid M_;
    int depth_, size_, hsize_;
    std::vector<value_type> data_;

  public:
    segment_tree() {}
    segment_tree(int n) : depth_(n > 1 ? 32 - __builtin_clz(n - 1) + 1 : 1),
                          size_(1 << depth_),
                          hsize_(size_ / 2),
                          data_(size_, M_()) {}

    auto operator[](int i) const {
      assert(0 <= i and i < hsize_);
      return data_[hsize_ + i];
    }

    auto fold(int l, int r) const {
      assert(0 <= l and l <= r and r <= hsize_);
      value_type ret_left  = M_();
      value_type ret_right = M_();

      int L = l + hsize_, R = r + hsize_;
      while (L < R) {
        if (R & 1) ret_right = M_(data_[--R], ret_right);
        if (L & 1) ret_left = M_(ret_left, data_[L++]);
        L >>= 1, R >>= 1;
      }

      return M_(ret_left, ret_right);
    }

    auto fold_all() const {
      return data_[1];
    }

    void set(int i, const value_type &x) {
      assert(0 <= i and i < hsize_);
      i += hsize_;
      data_[i] = x;
      while (i > 1) i >>= 1, data_[i] = M_(data_[i << 1 | 0], data_[i << 1 | 1]);
    }

    void update(int i, const value_type &x) {
      assert(0 <= i and i < hsize_);
      i += hsize_;
      data_[i] = M_(data_[i], x);
      while (i > 1) i >>= 1, data_[i] = M_(data_[i << 1 | 0], data_[i << 1 | 1]);
    }

    template <typename T>
    void init_with_vector(const std::vector<T> &val) {
      data_.assign(size_, M_());
      for (int i = 0; i < (int) val.size(); ++i) data_[hsize_ + i] = val[i];
      for (int i = hsize_; --i >= 1;) data_[i] = M_(data_[i << 1 | 0], data_[i << 1 | 1]);
    }

    template <typename T>
    void init(const T &val) {
      init_with_vector(std::vector<value_type>(hsize_, val));
    }

  private:
    template <bool Lower, typename F>
    int bound(const int l, const int r, value_type x, F f) const {
      std::vector<int> pl, pr;
      int L = l + hsize_;
      int R = r + hsize_;
      while (L < R) {
        if (R & 1) pr.push_back(--R);
        if (L & 1) pl.push_back(L++);
        L >>= 1, R >>= 1;
      }

      std::reverse(pr.begin(), pr.end());
      pl.insert(pl.end(), pr.begin(), pr.end());

      value_type a = M_();

      for (int i : pl) {
        auto b = M_(a, data_[i]);

        if ((Lower and not f(b, x)) or (not Lower and f(x, b))) {
          while (i < hsize_) {
            const auto c = M_(a, data_[i << 1 | 0]);
            if ((Lower and not f(c, x)) or (not Lower and f(x, c))) {
              i = i << 1 | 0;
            } else {
              a = c;
              i = i << 1 | 1;
            }
          }

          return i - hsize_;
        }

        a = b;
      }

      return r;
    }

  public:
    template <typename F = std::less<value_type>>
    int lower_bound(int l, int r, value_type x, F f = F()) const {
      return bound<true>(l, r, x, f);
    }

    template <typename F = std::less<value_type>>
    int upper_bound(int l, int r, value_type x, F f = F()) const {
      return bound<false>(l, r, x, f);
    }
  };
}  // namespace haar_lib
#line 2 "Mylib/IO/input_tuples.cpp"
#include <initializer_list>
#line 4 "Mylib/IO/input_tuples.cpp"
#include <tuple>
#include <utility>
#line 6 "Mylib/IO/input_tuple.cpp"

namespace haar_lib {
  template <typename T, size_t... I>
  static void input_tuple_helper(std::istream &s, T &val, std::index_sequence<I...>) {
    (void) std::initializer_list<int>{(void(s >> std::get<I>(val)), 0)...};
  }

  template <typename T, typename U>
  std::istream &operator>>(std::istream &s, std::pair<T, U> &value) {
    s >> value.first >> value.second;
    return s;
  }

  template <typename... Args>
  std::istream &operator>>(std::istream &s, std::tuple<Args...> &value) {
    input_tuple_helper(s, value, std::make_index_sequence<sizeof...(Args)>());
    return s;
  }
}  // namespace haar_lib
#line 8 "Mylib/IO/input_tuples.cpp"

namespace haar_lib {
  template <typename... Args>
  class InputTuples {
    struct iter {
      using value_type = std::tuple<Args...>;
      value_type value;
      bool fetched = false;
      int N, c = 0;

      value_type operator*() {
        if (not fetched) {
          std::cin >> value;
        }
        return value;
      }

      void operator++() {
        ++c;
        fetched = false;
      }

      bool operator!=(iter &) const {
        return c < N;
      }

      iter(int N) : N(N) {}
    };

    int N;

  public:
    InputTuples(int N) : N(N) {}

    iter begin() const { return iter(N); }
    iter end() const { return iter(N); }
  };

  template <typename... Args>
  auto input_tuples(int N) {
    return InputTuples<Args...>(N);
  }
}  // namespace haar_lib
#line 4 "Mylib/IO/input_vector.cpp"

namespace haar_lib {
  template <typename T>
  std::vector<T> input_vector(int N) {
    std::vector<T> ret(N);
    for (int i = 0; i < N; ++i) std::cin >> ret[i];
    return ret;
  }

  template <typename T>
  std::vector<std::vector<T>> input_vector(int N, int M) {
    std::vector<std::vector<T>> ret(N);
    for (int i = 0; i < N; ++i) ret[i] = input_vector<T>(M);
    return ret;
  }
}  // namespace haar_lib
#line 12 "test/yukicoder/776/main.test.cpp"

namespace hl = haar_lib;

using M = hl::max_partial_sum_monoid<int64_t>;

int main() {
  int N, Q;
  std::cin >> N >> Q;

  hl::segment_tree<M> seg(N);

  auto a = hl::input_vector<int64_t>(N);
  for (int i = 0; i < N; ++i) {
    seg.set(i, M::max_partial_sum(a[i]));
  }

  for (auto [type] : hl::input_tuples<std::string>(Q)) {
    if (type == "set") {
      int i, x;
      std::cin >> i >> x;
      --i;
      seg.set(i, M::max_partial_sum(x));
      a[i] = x;
    } else {
      int l1, l2, r1, r2;
      std::cin >> l1 >> l2 >> r1 >> r2;
      --l1, --l2, --r1, --r2;

      r1 = std::max(l1, r1);
      l2 = std::min(l2, r2);

      int64_t ans = LLONG_MIN;

      auto f =
          [&](int L1, int L2, int R1, int R2) {
            auto ret =
                seg.fold(L1, L2 + 1).value_or(M::max_partial_sum(0)).right_max +
                seg.fold(std::min(L2 + 1, R1), R1).value_or(M::max_partial_sum(0)).sum +
                seg.fold(R1, R2 + 1).value_or(M::max_partial_sum(0)).left_max;

            if (L2 == R1) ret -= a[L2];

            return ret;
          };

      if (l2 <= r1) {
        ans = f(l1, l2, r1, r2);
      } else {
        if (l1 <= r1) ans = std::max(ans, f(l1, r1, r1, r2));
        if (l2 <= r2) ans = std::max(ans, f(l1, l2, l2, r2));
        if (r1 <= l2) ans = std::max(ans, seg.fold(r1, l2 + 1)->partial_max);
      }

      std::cout << ans << "\n";
    }
  }

  return 0;
}

Back to top page