test/library-checker/static_range_inversions_query.test.cpp

• View this file on GitHub
• Last update: 2021-06-26 00:26:47+09:00
• Problem: https://judge.yosupo.jp/problem/static_range_inversions_query

Depends on

• src/algebra/system/monoid.hpp
• Mo's Algorithm (src/data_structure/Mo.hpp)
• Compression (src/data_structure/compression.hpp)
• Segment Tree (src/data_structure/segment_tree/basic.hpp)

Code

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

#include <cstdio>

#include "src/data_structure/Mo.hpp"
#include "src/data_structure/compression.hpp"
#include "src/data_structure/segment_tree/basic.hpp"

int main() {
  using i64 = long long;
  int n, q;
  scanf("%d%d", &n, &q);
  std::vector<size_t> a(n);
  for (auto &e : a) scanf("%d", &e);
  workspace::compression ccmp(begin(a), end(a));
  ccmp.make();
  for (auto &&x : a) {
    x = ccmp.lower_bound(x);
  }
  std::vector<int> cnt(ccmp.size());
  workspace::segment_tree<int> seg(n);
  i64 invs = 0;
  auto addl = [&](int i) -> auto {
    i = a[i];
    invs += seg.fold(0, i);
    seg[i]++;
  };
  auto addr = [&](int i) -> auto {
    i = a[i];
    invs += seg.fold(i + 1, n);
    seg[i]++;
  };
  auto dell = [&](int i) -> auto {
    i = a[i];
    invs -= seg.fold(0, i);
    seg[i]--;
  };
  auto delr = [&](int i) -> auto {
    i = a[i];
    invs -= seg.fold(i + 1, n);
    seg[i]--;
  };
  workspace::Mo mo(addl, dell, addr, delr);
  for (int i = 0; i < q; i++) {
    int l, r;
    scanf("%d%d", &l, &r);
    mo.insert(l, r);
  }
  mo.make();
  std::vector<i64> ans(q);
  for (auto &&e : mo) {
    ans[e.index] = invs;
  }
  for (i64 x : ans) printf("%lld\n", x);
}

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

#include <cstdio>

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

/**
 * @file Mo.hpp
 * @brief Mo's Algorithm
 */

#include <cassert>
#include <cmath>
#include <functional>
#include <vector>

namespace workspace {

/**
 * @brief Mo's Alorithm. Process queries about contiguous subarrays.
 *
 * @tparam _Push_back
 * @tparam _Pop_back
 * @tparam _Push_front Use `_Push_back` as default
 * @tparam _Pop_front Use `_Pop_back` as default
 */
template <class _Push_back, class _Pop_back, class _Push_front = _Push_back,
          class _Pop_front = _Pop_back>
class Mo {
 public:
  using size_type = std::size_t;

  struct query {
    size_type index;
    size_type left, right;
  };

  using value_type = query;
  using reference = query&;
  using container_type = std::vector<query>;

 protected:
  _Push_front push_front;
  _Pop_front pop_front;
  _Push_back push_back;
  _Pop_back pop_back;

  container_type queries;

 public:
  /**
   * @brief Construct a new Mo object.
   *
   * @param push_back
   * @param pop_back
   */
  Mo(_Push_back push_back, _Pop_back pop_back) noexcept
      : Mo(push_back, pop_back, push_back, pop_back) {}

  /**
   * @brief Construct a new Mo object.
   *
   * @param push_front
   * @param pop_front
   * @param push_back
   * @param pop_back
   */
  Mo(_Push_front push_front, _Pop_front pop_front, _Push_back push_back,
     _Pop_back pop_back) noexcept
      : push_front(push_front),
        pop_front(pop_front),
        push_back(push_back),
        pop_back(pop_back) {}

  /**
   * @return Number of queries.
   */
  size_type size() const noexcept { return queries.size(); }

  /**
   * @brief Add a query for the interval [l, r).
   *
   * @param __l Left end, inclusive
   * @param __r Right end, exclusive
   * @return Index of the query.
   */
  reference insert(size_type __l, size_type __r) noexcept {
    assert(__l <= __r);
    queries.push_back({queries.size(), __l, __r});
    return queries.back();
  }

  /**
   * @brief Sort all queries.
   */
  void make() noexcept {
    assert(size());
    size_type __n = 0;
    for (const auto& __q : queries) __n = std::max(__n, __q.right);
    size_type __width = ceil(__n / sqrt(size()));
    std::sort(queries.begin(), queries.end(), [&](auto __x, auto __y) {
      if (__x.left / __width != __y.left / __width) return __x.left < __y.left;
      return __x.right < __y.right;
    });
  }

  class iterator : public container_type::iterator {
    using base = typename container_type::iterator;
    Mo* __mo;

    void fit(size_type __l1, size_type __r1, size_type __l2,
             size_type __r2) const noexcept {
      while (__l1 > __l2) __mo->push_front(--__l1);
      while (__r1 < __r2) __mo->push_back(__r1++);
      while (__l1 < __l2) __mo->pop_front(__l1++);
      while (__r1 > __r2) __mo->pop_back(--__r1);
    }

    void fit_from_empty(size_type __l, size_type __r) const noexcept {
      while (__l < __r) __mo->push_back(__l++);
    }

    void fit_to_empty(size_type __l, size_type __r) const noexcept {
      while (__l < __r) __mo->push_back(--__r);
    }

    bool at_end() const noexcept { return __mo->queries.end() == *this; }

   public:
    iterator() = default;

    iterator(Mo* __mo, base __i) noexcept : base(__i), __mo(__mo) {
      if (__i != __mo->queries.end()) fit_from_empty(__i->left, __i->right);
    }

    iterator& operator++() noexcept {
      auto __l = (*this)->left, __r = (*this)->right;
      base::operator++();
      if (at_end())
        fit_to_empty(__l, __r);
      else
        fit(__l, __r, (*this)->left, (*this)->right);
      return *this;
    }

    iterator& operator--() noexcept {
      if (at_end()) {
        base::operator--();
        fit_from_empty((*this)->left, (*this)->right);
      } else {
        size_type __l = (*this)->left, __r = (*this)->right;
        base::operator--();
        fit(__l, __r, (*this)->left, (*this)->right);
      }
      return *this;
    }

    iterator operator++(int) noexcept {
      auto __tmp = *this;
      operator++();
      return __tmp;
    }

    iterator operator--(int) noexcept {
      auto __tmp = *this;
      operator--();
      return __tmp;
    }
  };

  iterator begin() noexcept { return {this, queries.begin()}; }

  iterator end() noexcept { return {this, queries.end()}; }
};

}  // namespace workspace
#line 2 "src/data_structure/compression.hpp"

/**
 * @file compression.hpp
 * @brief Compression
 */

#include <algorithm>
#line 11 "src/data_structure/compression.hpp"

namespace workspace {

template <class _Tp> class compression {
  std::vector<_Tp> __vec;

  decltype(auto) begin() { return __vec.begin(); }

  decltype(auto) end() { return __vec.end(); }

 public:
  using size_type = typename std::vector<_Tp>::size_type;

  /**
   * @brief Construct a new compression object.
   */
  compression() = default;

  /**
   * @brief Construct a new compression object.
   *
   * @param __first
   * @param __last
   */
  template <class _IIter>
  compression(_IIter __first, _IIter __last) noexcept : __vec(__first, __last) {
    make();
  }

  decltype(auto) begin() const noexcept { return __vec.begin(); }

  decltype(auto) end() const noexcept { return __vec.end(); }

  decltype(auto) operator[](size_type __i) const noexcept {
    assert(__i < size());
    return __vec[__i];
  }

  size_type size() const noexcept { return __vec.size(); }

  template <class... _Args> decltype(auto) emplace(_Args&&... __args) noexcept {
    return __vec.emplace_back(std::forward<_Args>(__args)...);
  }

  template <class... _Args> void insert(_Args&&... __args) noexcept {
    __vec.insert(end(), std::forward<_Args>(__args)...);
  }

  /**
   * @brief Sort and make unique.
   * @return Number of different values.
   */
  size_type make() noexcept {
    std::sort(begin(), end());

    __vec.erase(std::unique(begin(), end(),
                            [](const _Tp& __l, const _Tp& __r) {
                              return !(__l < __r) && !(__r < __l);
                            }),
                end());

    return size();
  }

  size_type lower_bound(const _Tp& __x) const noexcept {
    return std::lower_bound(begin(), end(), __x) - begin();
  }

  size_type upper_bound(const _Tp& __x) const noexcept {
    return std::upper_bound(begin(), end(), __x) - begin();
  }
};

template <class _IIter>
compression(_IIter, _IIter)
    -> compression<typename std::iterator_traits<_IIter>::value_type>;

}  // namespace workspace
#line 2 "src/data_structure/segment_tree/basic.hpp"

/**
 * @file basic.hpp
 * @brief Segment Tree
 */

#line 10 "src/data_structure/segment_tree/basic.hpp"

#line 2 "src/algebra/system/monoid.hpp"
#include <limits>

namespace workspace {
template <class T, class E = T> struct min_monoid {
  using value_type = T;
  static T min, max;
  T value;
  min_monoid() : value(max) {}
  min_monoid(const T &value) : value(value) {}
  operator T() const { return value; }
  min_monoid operator+(const min_monoid &rhs) const {
    return value < rhs.value ? *this : rhs;
  }
  min_monoid operator*(const E &rhs) const;
};

template <class T, class E>
T min_monoid<T, E>::min = std::numeric_limits<T>::min() / 2;
template <class T, class E>
T min_monoid<T, E>::max = std::numeric_limits<T>::max() / 2;

template <class T, class E = T> struct max_monoid : min_monoid<T, E> {
  using base = min_monoid<T, E>;
  using base::min_monoid;
  max_monoid() : base(base::min) {}
  max_monoid operator+(const max_monoid &rhs) const {
    return !(base::value < rhs.value) ? *this : rhs;
  }
  max_monoid operator*(const E &rhs) const;
};
}
#line 12 "src/data_structure/segment_tree/basic.hpp"

namespace workspace {

/**
 * @tparam Monoid `operator+`
 * @tparam Container_tmpl `operator[]`, `size_type`
 */
template <class Monoid, template <class...> class Container_tmpl = std::vector>
class segment_tree {
  static_assert(
      std::is_same<Monoid, decltype(std::declval<const Monoid>() +
                                    std::declval<const Monoid>())>::value,
      "\'Monoid\' has no proper binary \'operator+\'.");

  struct node {
    Monoid value{};
    bool latest{true};
  };

  using container_type = Container_tmpl<node>;

 public:
  using size_type = typename container_type::size_type;

  class iterator {
    segment_tree *__p;
    size_type __i;

   public:
    using difference_type = typename std::make_signed<size_type>::type;
    using value_type = Monoid;
    using reference = Monoid &;
    using pointer = iterator;
    using iterator_category = std::random_access_iterator_tag;

    /**
     * @brief Construct a new iterator object
     *
     */
    iterator() = default;

    /**
     * @brief Construct a new iterator object
     *
     * @param __p Pointer to a segment tree object
     * @param __i Index
     */
    iterator(segment_tree *__p, size_type __i) : __p(__p), __i(__i) {}

    bool operator==(iterator const &rhs) const {
      return __p == rhs.__p && __i == rhs.__i;
    }
    bool operator!=(iterator const &rhs) const { return !operator==(rhs); }

    bool operator<(iterator const &rhs) const { return __i < rhs.__i; }
    bool operator>(iterator const &rhs) const { return __i > rhs.__i; }
    bool operator<=(iterator const &rhs) const { return __i <= rhs.__i; }
    bool operator>=(iterator const &rhs) const { return __i >= rhs.__i; }

    iterator &operator++() { return ++__i, *this; }
    iterator &operator--() { return --__i, *this; }

    difference_type operator-(iterator const &rhs) const {
      return __i - rhs.__i;
    }

    /**
     * @brief
     *
     * @return reference
     */
    reference operator*() const { return __p->operator[](__i); }
  };

  using value_type = typename iterator::value_type;
  using reference = typename iterator::reference;

  iterator begin() { return {this, 0}; }
  iterator end() { return {this, size_orig}; }

  auto rbegin() { return std::make_reverse_iterator(end()); }
  auto rend() { return std::make_reverse_iterator(begin()); }

 protected:
  size_type size_orig, height, size_ext;
  container_type data;

  Monoid const &pull(size_type __i) noexcept {
    if (!data[__i].latest)
      data[__i] = {pull(__i << 1) + pull(__i << 1 | 1), true};
    return data[__i].value;
  }

  template <class Pred>
  static constexpr decltype(std::declval<Pred>()(Monoid{})) pass_args(
      Pred pred, Monoid const &_1, [[maybe_unused]] size_type _2) {
    return pred(_1);
  }

  template <class Pred>
  static constexpr decltype(std::declval<Pred>()(Monoid{}, size_type{}))
  pass_args(Pred pred, Monoid const &_1, size_type _2) {
    return pred(_1, _2);
  }

  template <class Pred>
  size_type left_partition_subtree(size_type __i, Monoid mono, size_type step,
                                   Pred pred) {
    assert(__i);
    while (__i < size_ext) {
      const Monoid tmp = pull((__i <<= 1) | 1) + mono;
      if (pass_args(pred, tmp, ((__i | 1) << --step) ^ size_ext))
        mono = tmp;
      else
        ++__i;
    }
    return ++__i -= size_ext;
  }

  template <class Pred>
  size_type right_partition_subtree(size_type __i, Monoid mono, size_type step,
                                    Pred pred) {
    assert(__i);
    while (__i < size_ext) {
      const Monoid tmp = mono + pull(__i <<= 1);
      if (pass_args(pred, tmp, ((__i | 1) << --step) ^ size_ext))
        ++__i, mono = tmp;
    }
    return (__i -= size_ext) < size_orig ? __i : size_orig;
  }

 public:
  /**
   * @brief Construct a new segment tree object
   *
   * @param __n Number of elements.
   */
  segment_tree(size_type __n = 0)
      : size_orig{__n},
        height(__n > 1 ? 64 - __builtin_clzll(__n - 1) : 0),
        size_ext{size_type{1} << height} {
    if constexpr (std::is_constructible_v<container_type, size_t>)
      data = container_type(size_ext << 1);
  }

  /**
   * @brief Construct a new segment tree object
   *
   * @tparam Tp
   * @param __n Number of elements.
   * @param init
   */
  template <class Tp,
            std::enable_if_t<std::is_convertible_v<Tp, Monoid>> * = nullptr>
  segment_tree(size_type __n, Tp const &init) : segment_tree(__n) {
    for (auto i = begin(); i != end(); ++i) *i = init;
  }

  /**
   * @brief Construct a new segment tree object
   *
   * @tparam Iterator
   * @param __first
   * @param __last
   */
  template <class Iterator,
            std::enable_if_t<std::is_convertible_v<
                typename std::iterator_traits<Iterator>::value_type, Monoid>>
                * = nullptr>
  segment_tree(Iterator __first, Iterator __last)
      : segment_tree(std::distance(__first, __last)) {
    for (auto i = begin(); __first != __last; ++i, ++__first) *i = *__first;
  }

  /**
   * @return Number of elements.
   */
  size_type size() const { return size_orig; }

  /**
   * @param __i Index of the element
   * @return Reference to the element.
   */
  reference operator[](size_type __i) {
    assert(__i < size_orig);
    __i |= size_ext;
    for (size_type __j{__i >> 1}; __j && data[__j].latest; __j >>= 1)
      data[__j].latest = false;
    return data[__i].value;
  }

  /**
   * @param first Left end, inclusive
   * @param last Right end, exclusive
   * @return Sum of elements in the interval.
   */
  value_type fold(size_type first, size_type last) {
    assert(last <= size_orig);
    Monoid left{}, right{};
    first += size_ext, last += size_ext;
    while (first < last) {
      if (first & 1) left = left + pull(first++);
      if (last & 1) right = pull(--last) + right;
      first >>= 1, last >>= 1;
    }
    return left + right;
  }

  /**
   * @return The whole sum.
   */
  value_type fold() { return fold(0, size_orig); }

  /**
   * @brief Binary search for the partition point.
   * @param right Right fixed end of the interval, exclusive
   * @param pred Predicate in the form of either 'bool(Monoid)' or 'bool(Monoid,
   * size_type)'
   * @return Left end of the extremal interval satisfying the condition,
   * inclusive.
   */
  template <class Pred> size_type left_partition(size_type right, Pred pred) {
    assert(right <= size_orig);
    right += size_ext;
    Monoid mono{};
    for (size_type left{size_ext}, step{}; left != right;
         left >>= 1, right >>= 1, ++step) {
      if ((left & 1) != (right & 1)) {
        const Monoid tmp = pull(--right) + mono;
        if (!pass_args(pred, tmp, (right << step) ^ size_ext))
          return left_partition_subtree(right, mono, step, pred);
        mono = tmp;
      }
    }
    return 0;
  }

  /**
   * @brief Binary search for the partition point.
   * @param left Left fixed end of the interval, inclusive
   * @param pred Predicate in the form of either 'bool(Monoid)' or 'bool(Monoid,
   * size_type)'
   * @return Right end of the extremal interval satisfying the condition,
   * exclusive.
   */
  template <class Pred> size_type right_partition(size_type left, Pred pred) {
    assert(left <= size_orig);
    left += size_ext;
    Monoid mono{};
    for (size_type right{size_ext << 1}, step{}; left != right;
         left >>= 1, right >>= 1, ++step) {
      if ((left & 1) != (right & 1)) {
        const Monoid tmp = mono + pull(left);
        if (!pass_args(pred, tmp, ((left + 1) << step) ^ size_ext))
          return right_partition_subtree(left, mono, step, pred);
        mono = tmp;
        ++left;
      }
    }
    return size_orig;
  }
};

}  // namespace workspace
#line 8 "test/library-checker/static_range_inversions_query.test.cpp"

int main() {
  using i64 = long long;
  int n, q;
  scanf("%d%d", &n, &q);
  std::vector<size_t> a(n);
  for (auto &e : a) scanf("%d", &e);
  workspace::compression ccmp(begin(a), end(a));
  ccmp.make();
  for (auto &&x : a) {
    x = ccmp.lower_bound(x);
  }
  std::vector<int> cnt(ccmp.size());
  workspace::segment_tree<int> seg(n);
  i64 invs = 0;
  auto addl = [&](int i) -> auto {
    i = a[i];
    invs += seg.fold(0, i);
    seg[i]++;
  };
  auto addr = [&](int i) -> auto {
    i = a[i];
    invs += seg.fold(i + 1, n);
    seg[i]++;
  };
  auto dell = [&](int i) -> auto {
    i = a[i];
    invs -= seg.fold(0, i);
    seg[i]--;
  };
  auto delr = [&](int i) -> auto {
    i = a[i];
    invs -= seg.fold(i + 1, n);
    seg[i]--;
  };
  workspace::Mo mo(addl, dell, addr, delr);
  for (int i = 0; i < q; i++) {
    int l, r;
    scanf("%d%d", &l, &r);
    mo.insert(l, r);
  }
  mo.make();
  std::vector<i64> ans(q);
  for (auto &&e : mo) {
    ans[e.index] = invs;
  }
  for (i64 x : ans) printf("%lld\n", x);
}

Back to top page