test/library-checker/range_chmin_chmax_add_range_sum.test.cpp

• View this file on GitHub
• Last update: 2021-06-09 03:04:07+09:00
• Problem: https://judge.yosupo.jp/problem/range_chmin_chmax_add_range_sum

Depends on

• Buckets (src/data_structure/buckets.hpp)

Code

#define PROBLEM \
  "https://judge.yosupo.jp/problem/range_chmin_chmax_add_range_sum"

#include <algorithm>
#include <cstdint>
#include <cstdio>
#include <map>

#include "src/data_structure/buckets.hpp"

int main() {
  using namespace workspace;
  using i64 = int64_t;

  int n, q;
  scanf("%d%d", &n, &q);
  std::vector<i64> a(n);
  for (auto&& x : a) {
    scanf("%lld", &x);
  }

  struct data {
    i64 min, max, add, sum, num;
    std::map<i64, i64> map;
  };

  constexpr auto inf = 1'000'000'000'000;

  buckets b(
      begin(a), end(a),
      [](auto l, auto r) {
        data d;
        d.add = 0;
        d.sum = 0;
        d.min = inf;
        d.max = -inf;
        d.num = 0;
        while (l != r) {
          d.sum += *l;
          d.map[*l] += 1;
          d.num += 1;
          ++l;
        }
        return d;
      },
      [](const auto& d, auto l, auto r) {
        while (l != r) {
          *l = std::min(d.min, std::max(d.max, *l)) + d.add;
          ++l;
        }
      });

  for (int t, l, r; q--;) {
    scanf("%d%d%d", &t, &l, &r);
    if (t == 3) {
      i64 sum = 0;
      b(l, r, [&](const auto& x) { sum += x.sum; });
      printf("%lld\n", sum);
      continue;
    }

    i64 a;
    scanf("%lld", &a);
    switch (t) {
      case 0:
        b(l, r, [&](auto& d) {
          auto c = a - d.add;
          if (d.min < c) return;
          d.min = c;
          if (d.max > c) d.max = c;
          while (d.map.rbegin()->first > c) {
            auto [v, k] = *prev(d.map.end());
            d.map.erase(prev(d.map.end()));
            d.map[c] += k;
            d.sum += (c - v) * k;
          }
        });
        break;

      case 1:
        b(l, r, [&](auto& d) {
          auto c = a - d.add;
          if (d.max > c) return;
          d.max = c;
          if (d.min < c) d.min = c;
          while (d.map.begin()->first < c) {
            auto [v, k] = *d.map.begin();
            d.map.erase(d.map.begin());
            d.map[c] += k;
            d.sum += (c - v) * k;
          }
        });
        break;

      case 2:
        b(l, r, [&](auto& x) {
          x.sum += x.num * a;
          x.add += a;
        });
        break;
    }
  }
}

#line 1 "test/library-checker/range_chmin_chmax_add_range_sum.test.cpp"
#define PROBLEM \
  "https://judge.yosupo.jp/problem/range_chmin_chmax_add_range_sum"

#include <algorithm>
#include <cstdint>
#include <cstdio>
#include <map>

#line 2 "src/data_structure/buckets.hpp"

/**
 * @file buckets.hpp
 * @brief Buckets
 */

#include <cmath>
#include <vector>

namespace workspace {

/**
 * @brief Buckets on a sequence.
 */
template <class _Iterator, class _Pack, class _Unpack> struct buckets {
  // Require random access.
  static_assert(
      std::is_same<typename std::iterator_traits<_Iterator>::iterator_category,
                   std::random_access_iterator_tag>::value);

  using difference_type =
      typename std::iterator_traits<_Iterator>::difference_type;

  _Iterator __begin, __end;

  using value_type = decltype(std::declval<_Pack>()(std::declval<_Iterator>(),
                                                    std::declval<_Iterator>()));

  struct bucket {
    value_type __data;
    _Iterator __begin;
    _Iterator __end;
  };

  _Pack __pack;
  _Unpack __unpack;
  difference_type __unit;
  std::vector<bucket> __buckets;

  void prepare() {
    if (!__unit) __unit = round(sqrt(std::distance(__begin, __end)));

    for (auto __l = __begin, __r = __l; __r != __end; __l = __r) {
      for (auto __n = __unit; __r != __end && __n; --__n) ++__r;
      __buckets.push_back({__pack(__l, __r), __l, __r});
    }
  }

 public:
  /**
   * @brief Constuct a new buckets object.
   */
  buckets(_Iterator __first, _Iterator __last, _Pack __pack, _Unpack __unpack,
          difference_type __unit = 0)
      : __begin(__first),
        __end(__last),
        __pack(__pack),
        __unpack(__unpack),
        __unit(__unit) {
    prepare();
  }

  /**
   * @brief Number of buckets.
   */
  auto size() const { return __buckets.size(); }

  bool empty() const { return __begin == __end; }

  /**
   * @brief Operate on a subsegment.
   *
   * @param __first
   * @param __last
   * @param __oper
   */
  template <class _Operator>
  void operator()(_Iterator __first, _Iterator __last, _Operator __oper) {
    if (__first == __last) return;

    auto __index = std::distance(__begin, __first);
    auto __b = std::next(__buckets.begin(), __index / __unit);

    if (__index % __unit) {
      __unpack(__b->__data, __b->__begin, __b->__end);

      auto __mid = std::distance(__last, __b->__end) > 0 ? __last : __b->__end;

      auto __tmp = __pack(__first, __mid);
      __oper(__tmp);
      __unpack(__tmp, __first, __mid);

      __b->__data = __pack(__b->__begin, __b->__end);
      ++__b;
    }

    while (true) {
      if (__b == __buckets.end()) return;
      if (std::distance(__b->__end, __last) < 0) break;

      __oper(__b->__data);
      ++__b;
    }

    if (std::distance(__b->__begin, __last) > 0) {
      __unpack(__b->__data, __b->__begin, __b->__end);

      auto __tmp = __pack(__b->__begin, __last);
      __oper(__tmp);
      __unpack(__tmp, __b->__begin, __last);

      __b->__data = __pack(__b->__begin, __b->__end);
    }
  }

  /**
   * @brief Operate on a point.
   *
   * @param __pos
   * @param __oper
   */
  template <class _Operator>
  void operator()(_Iterator __pos, _Operator __oper) {
    auto __index = std::distance(__begin, __pos);
    auto __b = std::next(__buckets.begin(), __index / __unit);

    __unpack(__b->__data, __b->__begin, __b->__end);
    __oper(*__pos);
    __b->__data = __pack(__b->__begin, __b->__end);
  }

  /**
   * @brief Operate on a subsegment.
   *
   * @param __i
   * @param __j
   * @param __oper
   */
  template <class _Operator>
  void operator()(difference_type __i, difference_type __j, _Operator __oper) {
    operator()(std::next(__begin, __i), std::next(__begin, __j), __oper);
  }

  /**
   * @brief Operate on a point.
   *
   * @param __pos
   * @param __oper
   */
  template <class _Operator>
  void operator()(difference_type __i, _Operator __oper) {
    operator()(std::next(__begin, __i), __oper);
  }
};

}  // namespace workspace
#line 10 "test/library-checker/range_chmin_chmax_add_range_sum.test.cpp"

int main() {
  using namespace workspace;
  using i64 = int64_t;

  int n, q;
  scanf("%d%d", &n, &q);
  std::vector<i64> a(n);
  for (auto&& x : a) {
    scanf("%lld", &x);
  }

  struct data {
    i64 min, max, add, sum, num;
    std::map<i64, i64> map;
  };

  constexpr auto inf = 1'000'000'000'000;

  buckets b(
      begin(a), end(a),
      [](auto l, auto r) {
        data d;
        d.add = 0;
        d.sum = 0;
        d.min = inf;
        d.max = -inf;
        d.num = 0;
        while (l != r) {
          d.sum += *l;
          d.map[*l] += 1;
          d.num += 1;
          ++l;
        }
        return d;
      },
      [](const auto& d, auto l, auto r) {
        while (l != r) {
          *l = std::min(d.min, std::max(d.max, *l)) + d.add;
          ++l;
        }
      });

  for (int t, l, r; q--;) {
    scanf("%d%d%d", &t, &l, &r);
    if (t == 3) {
      i64 sum = 0;
      b(l, r, [&](const auto& x) { sum += x.sum; });
      printf("%lld\n", sum);
      continue;
    }

    i64 a;
    scanf("%lld", &a);
    switch (t) {
      case 0:
        b(l, r, [&](auto& d) {
          auto c = a - d.add;
          if (d.min < c) return;
          d.min = c;
          if (d.max > c) d.max = c;
          while (d.map.rbegin()->first > c) {
            auto [v, k] = *prev(d.map.end());
            d.map.erase(prev(d.map.end()));
            d.map[c] += k;
            d.sum += (c - v) * k;
          }
        });
        break;

      case 1:
        b(l, r, [&](auto& d) {
          auto c = a - d.add;
          if (d.max > c) return;
          d.max = c;
          if (d.min < c) d.min = c;
          while (d.map.begin()->first < c) {
            auto [v, k] = *d.map.begin();
            d.map.erase(d.map.begin());
            d.map[c] += k;
            d.sum += (c - v) * k;
          }
        });
        break;

      case 2:
        b(l, r, [&](auto& x) {
          x.sum += x.num * a;
          x.add += a;
        });
        break;
    }
  }
}

Back to top page