test/aizu-online-judge/3170.test.cpp

• View this file on GitHub
• Last update: 2021-05-22 02:27:41+09:00
• Problem: https://onlinejudge.u-aizu.ac.jp/problems/3170

Depends on

• Buckets (src/data_structure/buckets.hpp)

Code

#define PROBLEM "https://onlinejudge.u-aizu.ac.jp/problems/3170"

#include <algorithm>
#include <cstdio>

#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;
    std::vector<i64> v;
  };

  constexpr auto inf = __INT64_MAX__;

  buckets b(
      begin(a), end(a),
      [](auto l, auto r) {
        data d;
        d.add = 0;
        d.min = inf;
        d.max = -inf;
        d.v = std::vector(l, r);
        std::sort(d.v.begin(), d.v.end());
        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;
        }
      },
      128);

  for (int t, l, r; q--;) {
    i64 x, y;
    scanf("%d%d%d%lld", &t, &l, &r, &x);
    --l;

    switch (--t) {
      case 0:
        b(l, r, [&](auto& d) {
          auto c = x - d.add;
          if (d.min < c) return;
          d.min = c;
          if (d.max > c) d.max = c;
        });
        break;

      case 1:
        b(l, r, [&](auto& d) {
          auto c = x - d.add;
          if (d.max > c) return;
          d.max = c;
          if (d.min < c) d.min = c;
        });
        break;

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

      case 3:
        scanf("%lld", &y);
        int num = 0;
        b(l, r, [&](const auto& d) {
          int sign = 1;
          for (auto z : {x - 1 - d.add, y - d.add}) {
            sign *= -1;
            if (z < d.max) continue;
            if (z < d.min)
              num += sign * (std::upper_bound(d.v.begin(), d.v.end(), z) -
                             d.v.begin());
            else
              num += sign * (int)d.v.size();
          }
        });
        printf("%d\n", num);
        break;
    }
  }
}

#line 1 "test/aizu-online-judge/3170.test.cpp"
#define PROBLEM "https://onlinejudge.u-aizu.ac.jp/problems/3170"

#include <algorithm>
#include <cstdio>

#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 7 "test/aizu-online-judge/3170.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;
    std::vector<i64> v;
  };

  constexpr auto inf = __INT64_MAX__;

  buckets b(
      begin(a), end(a),
      [](auto l, auto r) {
        data d;
        d.add = 0;
        d.min = inf;
        d.max = -inf;
        d.v = std::vector(l, r);
        std::sort(d.v.begin(), d.v.end());
        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;
        }
      },
      128);

  for (int t, l, r; q--;) {
    i64 x, y;
    scanf("%d%d%d%lld", &t, &l, &r, &x);
    --l;

    switch (--t) {
      case 0:
        b(l, r, [&](auto& d) {
          auto c = x - d.add;
          if (d.min < c) return;
          d.min = c;
          if (d.max > c) d.max = c;
        });
        break;

      case 1:
        b(l, r, [&](auto& d) {
          auto c = x - d.add;
          if (d.max > c) return;
          d.max = c;
          if (d.min < c) d.min = c;
        });
        break;

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

      case 3:
        scanf("%lld", &y);
        int num = 0;
        b(l, r, [&](const auto& d) {
          int sign = 1;
          for (auto z : {x - 1 - d.add, y - d.add}) {
            sign *= -1;
            if (z < d.max) continue;
            if (z < d.min)
              num += sign * (std::upper_bound(d.v.begin(), d.v.end(), z) -
                             d.v.begin());
            else
              num += sign * (int)d.v.size();
          }
        });
        printf("%d\n", num);
        break;
    }
  }
}

Back to top page