Range set query
(Mylib/Typical/range_set_query.cpp)

• View this file on GitHub
• Last update: 2021-04-23 23:44:44+09:00

Operations

区間に含まれる要素の種類数を求めるクエリを処理する。

Requirements

Notes

Problems

• SPOJ DQUERY
• ABC174 F - Range Set Query

References

• https://hama-du-competitive.hatenablog.com/entry/2016/10/01/001418

Depends on

• Fenwick tree (Add) (Mylib/DataStructure/FenwickTree/fenwick_tree_add.cpp)

Code

#pragma once
#include <algorithm>
#include <tuple>
#include <vector>
#include "Mylib/DataStructure/FenwickTree/fenwick_tree_add.cpp"

namespace haar_lib {
  template <typename T>
  class range_set_query {
    std::vector<int> a_;
    std::vector<std::tuple<int, int, int>> qs_;
    int N_;

  public:
    range_set_query() {}
    range_set_query(std::vector<T> a) : N_(a.size()) {
      auto temp = a;
      std::sort(temp.begin(), temp.end());
      temp.erase(std::unique(temp.begin(), temp.end()), temp.end());

      for (auto x : a) {
        const int i = std::lower_bound(temp.begin(), temp.end(), x) - temp.begin();
        a_.push_back(i);
      }
    }

    void add(int l, int r) {  // [l, r)
      const int i = qs_.size();
      qs_.emplace_back(r, l, i);
    }

    auto solve() {
      std::sort(qs_.begin(), qs_.end());

      fenwick_tree_add<int> b(N_);

      const int Q = qs_.size();
      std::vector<int> last_index(N_, -1), ret(Q);

      int cur = 0;
      for (auto [r, l, i] : qs_) {
        while (cur < r) {
          if (last_index[a_[cur]] != -1) {
            b.update(last_index[a_[cur]], -1);
          }

          last_index[a_[cur]] = cur;
          b.update(last_index[a_[cur]], 1);

          ++cur;
        }

        ret[i] = b.fold(l, r);
      }

      return ret;
    }
  };
}  // namespace haar_lib

#line 2 "Mylib/Typical/range_set_query.cpp"
#include <algorithm>
#include <tuple>
#include <vector>
#line 2 "Mylib/DataStructure/FenwickTree/fenwick_tree_add.cpp"
#include <cassert>
#line 4 "Mylib/DataStructure/FenwickTree/fenwick_tree_add.cpp"

namespace haar_lib {
  template <typename T>
  class fenwick_tree_add {
  public:
    using value_type = T;

  private:
    int size_;
    std::vector<value_type> data_;

  public:
    fenwick_tree_add() {}
    fenwick_tree_add(int size) : size_(size), data_(size + 1, 0) {}

    void update(int i, value_type val) {
      assert(0 <= i and i < size_);
      i += 1;  // 1-index

      while (i <= size_) {
        data_[i] = data_[i] + val;
        i += i & (-i);
      }
    }

    value_type fold(int i) const {  // [0, i)
      assert(0 <= i and i <= size_);
      value_type ret = 0;

      while (i > 0) {
        ret = ret + data_[i];
        i -= i & (-i);
      }

      return ret;
    }

    value_type fold(int l, int r) const {  // [l, r)
      assert(0 <= l and l <= r and r <= size_);
      return fold(r) - fold(l);
    }

    value_type operator[](int x) const {
      return fold(x, x + 1);
    }
  };
}  // namespace haar_lib
#line 6 "Mylib/Typical/range_set_query.cpp"

namespace haar_lib {
  template <typename T>
  class range_set_query {
    std::vector<int> a_;
    std::vector<std::tuple<int, int, int>> qs_;
    int N_;

  public:
    range_set_query() {}
    range_set_query(std::vector<T> a) : N_(a.size()) {
      auto temp = a;
      std::sort(temp.begin(), temp.end());
      temp.erase(std::unique(temp.begin(), temp.end()), temp.end());

      for (auto x : a) {
        const int i = std::lower_bound(temp.begin(), temp.end(), x) - temp.begin();
        a_.push_back(i);
      }
    }

    void add(int l, int r) {  // [l, r)
      const int i = qs_.size();
      qs_.emplace_back(r, l, i);
    }

    auto solve() {
      std::sort(qs_.begin(), qs_.end());

      fenwick_tree_add<int> b(N_);

      const int Q = qs_.size();
      std::vector<int> last_index(N_, -1), ret(Q);

      int cur = 0;
      for (auto [r, l, i] : qs_) {
        while (cur < r) {
          if (last_index[a_[cur]] != -1) {
            b.update(last_index[a_[cur]], -1);
          }

          last_index[a_[cur]] = cur;
          b.update(last_index[a_[cur]], 1);

          ++cur;
        }

        ret[i] = b.fold(l, r);
      }

      return ret;
    }
  };
}  // namespace haar_lib

Back to top page