test/yosupo-judge/rectangle_sum/main.persistent_segment_tree.test.cpp

• View this file on GitHub
• Last update: 2021-04-23 23:44:44+09:00
• Problem: https://judge.yosupo.jp/problem/rectangle_sum
• Link: View error logs on GitHub Actions

Depends on

• Sum monoid (Mylib/AlgebraicStructure/Monoid/sum.cpp)
• Persistent segment tree (Mylib/DataStructure/SegmentTree/persistent_segment_tree.cpp)
• Input tuple (Mylib/IO/input_tuple.cpp)
• Input tuple vector (Mylib/IO/input_tuple_vector.cpp)
• Input tuples (Mylib/IO/input_tuples.cpp)
• Compressor (Mylib/Utils/compressor.cpp)
• Sort simultaneously (Mylib/Utils/sort_simultaneously.cpp)

Code

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

#include <iostream>
#include <vector>
#include "Mylib/AlgebraicStructure/Monoid/sum.cpp"
#include "Mylib/DataStructure/SegmentTree/persistent_segment_tree.cpp"
#include "Mylib/IO/input_tuple_vector.cpp"
#include "Mylib/IO/input_tuples.cpp"
#include "Mylib/Utils/compressor.cpp"
#include "Mylib/Utils/sort_simultaneously.cpp"

namespace hl = haar_lib;

using Seg = hl::persistent_segment_tree<hl::sum_monoid<int64_t>>;

int main() {
  std::cin.tie(0);
  std::ios::sync_with_stdio(false);

  int N, Q;
  std::cin >> N >> Q;

  auto [x, y, w] = hl::input_tuple_vector<int64_t, int64_t, int64_t>(N);

  hl::sort_simultaneously(
      [&](int i, int j) {
        return y[i] < y[j];
      },
      x, y, w);

  auto c      = hl::compressor_builder<int64_t>().add(x).build().compress(x);
  const int m = c.size();

  std::vector<Seg> seg;
  seg.push_back(Seg(m));

  for (int i = 0; i < N; ++i) {
    auto &s = seg.back();
    seg.push_back(s.update(x[i], w[i]));
  }

  for (auto [l, d, r, u] : hl::input_tuples<int64_t, int64_t, int64_t, int64_t>(Q)) {
    l = c.get_index(l);
    r = c.get_index(r);

    u = std::lower_bound(y.begin(), y.end(), u) - y.begin();
    d = std::lower_bound(y.begin(), y.end(), d) - y.begin();

    auto ans = seg[u].fold(l, r) - seg[d].fold(l, r);
    std::cout << ans << "\n";
  }

  return 0;
}

#line 1 "test/yosupo-judge/rectangle_sum/main.persistent_segment_tree.test.cpp"
#define PROBLEM "https://judge.yosupo.jp/problem/rectangle_sum"

#include <iostream>
#include <vector>
#line 2 "Mylib/AlgebraicStructure/Monoid/sum.cpp"

namespace haar_lib {
  template <typename T>
  struct sum_monoid {
    using value_type = T;
    value_type operator()() const { return 0; }
    value_type operator()(value_type a, value_type b) const { return a + b; }
  };
}  // namespace haar_lib
#line 2 "Mylib/DataStructure/SegmentTree/persistent_segment_tree.cpp"
#include <cassert>
#line 4 "Mylib/DataStructure/SegmentTree/persistent_segment_tree.cpp"

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

  private:
    struct node {
      value_type value;
      node *left = nullptr, *right = nullptr;
      node(const value_type &value) : value(value) {}
    };

    Monoid M_;
    int depth_, size_;
    node *root_ = nullptr;

    persistent_segment_tree(int depth, node *root) : depth_(depth), root_(root) {}

    node *assign(node *t, const std::vector<value_type> &init_list, int d, int &pos) {
      if (d == depth_) {
        t = new node(pos < (int) init_list.size() ? init_list[pos] : M_());
        ++pos;
      } else {
        t        = new node(M_());
        t->left  = assign(t->left, init_list, d + 1, pos);
        t->right = assign(t->right, init_list, d + 1, pos);
        t->value = M_(t->left->value, t->right->value);
      }
      return t;
    }

    void init(const std::vector<value_type> &init_list) {
      size_   = init_list.size();
      depth_  = size_ == 1 ? 1 : 32 - __builtin_clz(size_ - 1) + 1;
      int pos = 0;
      root_   = assign(root_, init_list, 1, pos);
    }

  public:
    persistent_segment_tree() {}
    persistent_segment_tree(const std::vector<value_type> &init_list) {
      init(init_list);
    }
    persistent_segment_tree(int size) {
      init(std::vector(size, M_()));
    }
    persistent_segment_tree(int size, const value_type &value) {
      init(std::vector(size, value));
    }

  protected:
    node *set(node *t, int l, int r, int pos, const value_type &val) const {
      if (r <= pos or pos + 1 <= l) {
        return t;
      } else if (pos <= l and r <= pos + 1) {
        return new node(val);
      } else {
        const int m = (l + r) >> 1;
        auto lp     = set(t->left, l, m, pos, val);
        auto rp     = set(t->right, m, r, pos, val);

        node *s = new node(M_(lp->value, rp->value));

        s->left  = lp;
        s->right = rp;

        return s;
      }
    }

  public:
    persistent_segment_tree set(int i, const value_type &val) const {
      assert(0 <= i and i < size_);
      node *t = set(root_, 0, 1 << (depth_ - 1), i, val);
      return persistent_segment_tree(depth_, t);
    }

    persistent_segment_tree update(int i, const value_type &val) const {
      return set(i, M_((*this)[i], val));
    }

  protected:
    value_type get(node *t, int i, int j, int l, int r) const {
      if (i <= l and r <= j) return t->value;
      if (r <= i or j <= l) return M_();
      const int m = (l + r) >> 1;
      return M_(get(t->left, i, j, l, m), get(t->right, i, j, m, r));
    }

  public:
    value_type fold(int l, int r) const {
      assert(0 <= l and l <= r and r <= size_);
      return get(root_, l, r, 0, 1 << (depth_ - 1));
    }

    value_type operator[](int i) const {
      return fold(i, i + 1);
    }
  };
}  // namespace haar_lib
#line 2 "Mylib/IO/input_tuple_vector.cpp"
#include <initializer_list>
#line 4 "Mylib/IO/input_tuple_vector.cpp"
#include <tuple>
#include <utility>
#line 7 "Mylib/IO/input_tuple_vector.cpp"

namespace haar_lib {
  template <typename T, size_t... I>
  void input_tuple_vector_init(T &val, int N, std::index_sequence<I...>) {
    (void) std::initializer_list<int>{(void(std::get<I>(val).resize(N)), 0)...};
  }

  template <typename T, size_t... I>
  void input_tuple_vector_helper(T &val, int i, std::index_sequence<I...>) {
    (void) std::initializer_list<int>{(void(std::cin >> std::get<I>(val)[i]), 0)...};
  }

  template <typename... Args>
  auto input_tuple_vector(int N) {
    std::tuple<std::vector<Args>...> ret;

    input_tuple_vector_init(ret, N, std::make_index_sequence<sizeof...(Args)>());
    for (int i = 0; i < N; ++i) {
      input_tuple_vector_helper(ret, i, std::make_index_sequence<sizeof...(Args)>());
    }

    return ret;
  }
}  // namespace haar_lib
#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 2 "Mylib/Utils/compressor.cpp"
#include <algorithm>
#line 4 "Mylib/Utils/compressor.cpp"

namespace haar_lib {
  template <typename T>
  class compressor {
    std::vector<T> data_;
    template <typename>
    friend class compressor_builder;

  public:
    int get_index(const T &val) const {
      return std::lower_bound(data_.begin(), data_.end(), val) - data_.begin();
    }

    auto &compress(std::vector<T> &vals) const {
      for (auto &x : vals) x = get_index(x);
      return *this;
    }

    auto &compress(T &val) const {
      val = get_index(val);
      return *this;
    }

    template <typename U, typename... Args>
    auto &compress(U &val, Args &... args) const {
      compress(val);
      return compress(args...);
    }

    auto &decompress(std::vector<T> &vals) const {
      for (auto &x : vals) x = data_[x];
      return *this;
    }

    auto &decompress(T &val) const {
      val = data_[val];
      return *this;
    }

    template <typename U, typename... Args>
    auto &decompress(U &val, Args &... args) const {
      decompress(val);
      return decompress(args...);
    }

    int size() const { return data_.size(); }
    T operator[](int index) const { return data_[index]; }
  };

  template <typename T>
  class compressor_builder {
    std::vector<T> data_;

  public:
    auto &add(const T &val) {
      data_.push_back(val);
      return *this;
    }

    auto &add(const std::vector<T> &vals) {
      data_.insert(data_.end(), vals.begin(), vals.end());
      return *this;
    }

    template <typename U, typename... Args>
    auto &add(const U &val, const Args &... args) {
      add(val);
      return add(args...);
    }

    auto build() const {
      compressor<T> ret;
      ret.data_ = data_;
      std::sort(ret.data_.begin(), ret.data_.end());
      ret.data_.erase(std::unique(ret.data_.begin(), ret.data_.end()), ret.data_.end());
      return ret;
    }
  };
}  // namespace haar_lib
#line 5 "Mylib/Utils/sort_simultaneously.cpp"
#include <numeric>
#line 8 "Mylib/Utils/sort_simultaneously.cpp"

namespace haar_lib {
  namespace sort_simultaneously_impl {
    template <typename T>
    void helper(int N, const std::vector<int> &ord, std::vector<T> &a) {
      std::vector<T> temp(N);
      for (int i = 0; i < N; ++i) temp[i] = a[ord[i]];
      std::swap(temp, a);
    }
  }  // namespace sort_simultaneously_impl

  template <typename Compare, typename... Args>
  void sort_simultaneously(const Compare &compare, std::vector<Args> &... args) {
    const int N = std::max({args.size()...});
    assert((int) std::min({args.size()...}) == N);
    std::vector<int> ord(N);
    std::iota(ord.begin(), ord.end(), 0);
    std::sort(ord.begin(), ord.end(), compare);

    (void) std::initializer_list<int>{
        (void(sort_simultaneously_impl::helper(N, ord, args)), 0)...};
  }
}  // namespace haar_lib
#line 11 "test/yosupo-judge/rectangle_sum/main.persistent_segment_tree.test.cpp"

namespace hl = haar_lib;

using Seg = hl::persistent_segment_tree<hl::sum_monoid<int64_t>>;

int main() {
  std::cin.tie(0);
  std::ios::sync_with_stdio(false);

  int N, Q;
  std::cin >> N >> Q;

  auto [x, y, w] = hl::input_tuple_vector<int64_t, int64_t, int64_t>(N);

  hl::sort_simultaneously(
      [&](int i, int j) {
        return y[i] < y[j];
      },
      x, y, w);

  auto c      = hl::compressor_builder<int64_t>().add(x).build().compress(x);
  const int m = c.size();

  std::vector<Seg> seg;
  seg.push_back(Seg(m));

  for (int i = 0; i < N; ++i) {
    auto &s = seg.back();
    seg.push_back(s.update(x[i], w[i]));
  }

  for (auto [l, d, r, u] : hl::input_tuples<int64_t, int64_t, int64_t, int64_t>(Q)) {
    l = c.get_index(l);
    r = c.get_index(r);

    u = std::lower_bound(y.begin(), y.end(), u) - y.begin();
    d = std::lower_bound(y.begin(), y.end(), d) - y.begin();

    auto ans = seg[u].fold(l, r) - seg[d].fold(l, r);
    std::cout << ans << "\n";
  }

  return 0;
}

Back to top page