test/yosupo/static_rmq-segment_tree.test.cpp

• View this file on GitHub
• Last update: 2024-07-11 22:21:57+09:00
• Problem: https://judge.yosupo.jp/problem/staticrmq

Code

#define PROBLEM "https://judge.yosupo.jp/problem/staticrmq"
#include "include/mtl/segment_tree.hpp"
#include <bits/stdc++.h>
using namespace std;
using ll = long long;

constexpr int INF = 11e8;
struct Min {
  int x = INF;
  Min operator*(const Min& r) const {
    return {std::min(x, r.x)};
  }
};

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

  int N,Q; cin>>N>>Q;

  std::vector<Min> A(N); for (auto& a : A) cin>>a.x;
  SegmentTree<Min> rmq(A.begin(), A.end());

  for (int q = 0; q < Q; q++) {
    int l,r; cin>>l>>r;
    auto ans = rmq.query(l, r).x;
    cout << ans << endl;
  }

  return 0;
}

#line 1 "test/yosupo/static_rmq-segment_tree.test.cpp"
#define PROBLEM "https://judge.yosupo.jp/problem/staticrmq"
#line 2 "include/mtl/bit_manip.hpp"
#include <cstdint>
#include <cassert>
#if __cplusplus >= 202002L
#ifndef MTL_CPP20
#define MTL_CPP20
#endif
#include <bit>
#endif

namespace bm {

/// Count 1s for each 8 bits
inline constexpr uint64_t popcnt_e8(uint64_t x) {
  x = (x & 0x5555555555555555) + ((x>>1) & 0x5555555555555555);
  x = (x & 0x3333333333333333) + ((x>>2) & 0x3333333333333333);
  x = (x & 0x0F0F0F0F0F0F0F0F) + ((x>>4) & 0x0F0F0F0F0F0F0F0F);
  return x;
}
/// Count 1s
inline constexpr unsigned popcnt(uint64_t x) {
#ifdef MTL_CPP20
  return std::popcount(x);
#else
  return (popcnt_e8(x) * 0x0101010101010101) >> 56;
#endif
}
/// Alias to mtl::popcnt(x)
constexpr unsigned popcount(uint64_t x) {
  return popcnt(x);
}
/// Count trailing 0s. s.t. *11011000 -> 3
inline constexpr unsigned ctz(uint64_t x) {
#ifdef MTL_CPP20
  return std::countr_zero(x);
#else
  return popcnt((x & (-x)) - 1);
#endif
}
/// Alias to mtl::ctz(x)
constexpr unsigned countr_zero(uint64_t x) {
  return ctz(x);
}
/// Count trailing 1s. s.t. *11011011 -> 2
inline constexpr unsigned cto(uint64_t x) {
#ifdef MTL_CPP20
  return std::countr_one(x);
#else
  return ctz(~x);
#endif
}
/// Alias to mtl::cto(x)
constexpr unsigned countr_one(uint64_t x) {
  return cto(x);
}
inline constexpr unsigned ctz8(uint8_t x) {
  return x == 0 ? 8 : popcnt_e8((x & (-x)) - 1);
}
/// [00..0](8bit) -> 0, [**..*](not only 0) -> 1
inline constexpr uint8_t summary(uint64_t x) {
  constexpr uint64_t hmask = 0x8080808080808080ull;
  constexpr uint64_t lmask = 0x7F7F7F7F7F7F7F7Full;
  auto a = x & hmask;
  auto b = x & lmask;
  b = hmask - b;
  b = ~b;
  auto c = (a | b) & hmask;
  c *= 0x0002040810204081ull;
  return uint8_t(c >> 56);
}
/// Extract target area of bits
inline constexpr uint64_t bextr(uint64_t x, unsigned start, unsigned len) {
  uint64_t mask = len < 64 ? (1ull<<len)-1 : 0xFFFFFFFFFFFFFFFFull;
  return (x >> start) & mask;
}
/// 00101101 -> 00111111 -count_1s-> 6
inline constexpr unsigned log2p1(uint8_t x) {
  if (x & 0x80)
    return 8;
  uint64_t p = uint64_t(x) * 0x0101010101010101ull;
  p -= 0x8040201008040201ull;
  p = ~p & 0x8080808080808080ull;
  p = (p >> 7) * 0x0101010101010101ull;
  p >>= 56;
  return p;
}
/// 00101100 -mask_mssb-> 00100000 -to_index-> 5
inline constexpr unsigned mssb8(uint8_t x) {
  assert(x != 0);
  return log2p1(x) - 1;
}
/// 00101100 -mask_lssb-> 00000100 -to_index-> 2
inline constexpr unsigned lssb8(uint8_t x) {
  assert(x != 0);
  return popcnt_e8((x & -x) - 1);
}
/// Count leading 0s. 00001011... -> 4
inline constexpr unsigned clz(uint64_t x) {
#ifdef MTL_CPP20
  return std::countl_zero(x);
#else
  if (x == 0)
    return 64;
  auto i = mssb8(summary(x));
  auto j = mssb8(bextr(x, 8 * i, 8));
  return 63 - (8 * i + j);
#endif
}
/// Alias to mtl::clz(x)
constexpr unsigned countl_zero(uint64_t x) {
  return clz(x);
}
/// Count leading 1s. 11110100... -> 4
inline constexpr unsigned clo(uint64_t x) {
#ifdef MTL_CPP20
  return std::countl_one(x);
#else
  return clz(~x);
#endif
}
/// Alias to mtl::clo(x)
constexpr unsigned countl_one(uint64_t x) {
  return clo(x);
}

inline constexpr unsigned clz8(uint8_t x) {
  return x == 0 ? 8 : 7 - mssb8(x);
}
inline constexpr uint64_t bit_reverse(uint64_t x) {
  x = ((x & 0x00000000FFFFFFFF) << 32) | ((x & 0xFFFFFFFF00000000) >> 32);
  x = ((x & 0x0000FFFF0000FFFF) << 16) | ((x & 0xFFFF0000FFFF0000) >> 16);
  x = ((x & 0x00FF00FF00FF00FF) << 8) | ((x & 0xFF00FF00FF00FF00) >> 8);
  x = ((x & 0x0F0F0F0F0F0F0F0F) << 4) | ((x & 0xF0F0F0F0F0F0F0F0) >> 4);
  x = ((x & 0x3333333333333333) << 2) | ((x & 0xCCCCCCCCCCCCCCCC) >> 2);
  x = ((x & 0x5555555555555555) << 1) | ((x & 0xAAAAAAAAAAAAAAAA) >> 1);
  return x;
}

/// Check if x is power of 2. 00100000 -> true, 00100001 -> false
constexpr bool has_single_bit(uint64_t x) noexcept {
#ifdef MTL_CPP20
  return std::has_single_bit(x);
#else
  return x != 0 && (x & (x - 1)) == 0;
#endif
}

/// Bit width needs to represent x. 00110110 -> 6
constexpr int bit_width(uint64_t x) noexcept {
#ifdef MTL_CPP20
  return std::bit_width(x);
#else
  return 64 - clz(x);
#endif
}

/// Ceil power of 2. 00110110 -> 01000000
constexpr uint64_t bit_ceil(uint64_t x) {
#ifdef MTL_CPP20
  return std::bit_ceil(x);
#else
  if (x == 0) return 1;
  return 1ull << bit_width(x - 1);
#endif
}

/// Floor power of 2. 00110110 -> 00100000
constexpr uint64_t bit_floor(uint64_t x) {
#ifdef MTL_CPP20
  return std::bit_floor(x);
#else
  if (x == 0) return 0;
  return 1ull << (bit_width(x) - 1);
#endif
}

} // namespace bm
#line 3 "include/mtl/segment_tree.hpp"
#include <cstddef>
#include <vector>
#include <stack>
#if __cplusplus >= 202002L
#include <concepts>

template<class M>
concept SegmentTreeMonoid = requires (M m) {
  {m * m} -> std::same_as<M>;
};
#endif

template <class M>
class SegmentTree {
#if __cplusplus >= 202002L
  static_assert(SegmentTreeMonoid<M>);
#endif
 public:
  using monoid_type = M;
  using value_type = monoid_type;
 private:
  size_t size_;
  std::vector<value_type> tree_;

 public:
  explicit SegmentTree(size_t size) : size_(size), tree_(size*2) {}

  template <class Iter>
  explicit SegmentTree(Iter begin, Iter end) : SegmentTree(std::distance(begin, end)) {
    if (size_==0) return;
    std::copy(begin, end, tree_.begin() + size_);
    for (size_t i = size_-1; i > 0; i--)
      tree_[i] = tree_[i<<1] * tree_[(i<<1)+1];
  }

  value_type get(size_t index) const {
    return tree_[size_ + index];
  }
  value_type operator[](size_t index) const {
    return get(index);
  }

 private:
  template<class T>
  void _set(size_t index, T&& val) {
    auto i = size_ + index;
    tree_[i] = std::forward<T>(val);
    i >>= 1;
    while (i > 0) {
      tree_[i] = tree_[i<<1] * tree_[(i<<1)+1];
      i >>= 1;
    }
  }
 public:
  template<class T>
  void set(size_t index, T&& val) {
    return _set(index, std::forward<T>(val));
  }
  void set(size_t index, const value_type& val) {
    _set(index, val);
  }
  void set(size_t index, value_type&& val) {
    _set(index, std::move(val));
  }

  value_type query(size_t l, size_t r) const {
    value_type lhs,rhs;
    for (auto _l = l+size_, _r = r+size_; _l < _r; _l>>=1, _r>>=1) {
      if (_l&1) lhs = lhs * tree_[_l++];
      if (_r&1) rhs = tree_[--_r] * rhs;
    }
    return lhs * rhs;
  }

  template<class F>
  size_t max_right(size_t begin, size_t end, F f) const {
    if (begin == end) return end;
    monoid_type p;
    std::stack<std::pair<size_t, monoid_type>> rps;
    auto l = size_ + begin;
    auto r = size_ + end;
    while (l < r and f(p * tree_[l])) {
      if (l&1) p = p * tree_[l++];
      if (r&1) {
        rps.emplace(r, tree_[r-1]);
        r--;
      }
      l>>=1; r>>=1;
    }
    if (l >= r) {
      while (rps.size()) {
        auto& [r, rp] = rps.top();
        if (!f(p * rp)) {
          l = r-1;
          break;
        }
        p = p * rp;
        rps.pop();
      }
      if (rps.empty()) return end;
    }
    while (l < size_) {
      assert(!f(p * tree_[l]));
      l <<= 1;
      if (f(p * tree_[l]))
        p = p * tree_[l++];
    }
    return l - size_;
  }

  template<class F>
  size_t min_left(size_t begin, size_t end, F f) const {
    if (end == begin) return begin;
    monoid_type p;
    std::stack<std::pair<size_t, monoid_type>> lps;
    auto l = size_ + begin;
    auto r = size_ + end;
    while (l < r and f(tree_[r-1] * p)) {
      if (l&1) {
        lps.emplace(l, tree_[l]);
        l++;
      }
      if (r&1) p = tree_[r-1] * p;
      l>>=1; r>>=1;
    }
    if (l >= r) {
      while (lps.size()) {
        auto& [l, lp] = lps.top();
        if (!f(lp * p)) {
          r = l+1;
          break;
        }
        p = lp * p;
        lps.pop();
      }
      if (lps.empty()) return begin;
    }
    while (r <= size_) {
      assert(!f(tree_[r-1] * p));
      r <<= 1;
      if (f(tree_[r-1] * p)) 
        p = tree_[--r] * p;
    }
    return r - size_;
  }
  template<bool (*F)(value_type)>
  size_t min_left(size_t begin, size_t end) const {
    return min_left(begin, [](value_type x) { return F(x); });
  }

};
#line 3 "test/yosupo/static_rmq-segment_tree.test.cpp"
#include <bits/stdc++.h>
using namespace std;
using ll = long long;

constexpr int INF = 11e8;
struct Min {
  int x = INF;
  Min operator*(const Min& r) const {
    return {std::min(x, r.x)};
  }
};

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

  int N,Q; cin>>N>>Q;

  std::vector<Min> A(N); for (auto& a : A) cin>>a.x;
  SegmentTree<Min> rmq(A.begin(), A.end());

  for (int q = 0; q < Q; q++) {
    int l,r; cin>>l>>r;
    auto ans = rmq.query(l, r).x;
    cout << ans << endl;
  }

  return 0;
}

Test cases

Env	Name	Status	Elapsed	Memory
g++	example_00	AC	6 ms	3 MB
g++	max_random_00	AC	664 ms	9 MB
g++	max_random_01	AC	606 ms	9 MB
g++	max_random_02	AC	624 ms	9 MB
g++	max_random_03	AC	662 ms	9 MB
g++	max_random_04	AC	615 ms	9 MB
g++	random_00	AC	501 ms	8 MB
g++	random_01	AC	519 ms	9 MB
g++	random_02	AC	428 ms	4 MB
g++	random_03	AC	60 ms	8 MB
g++	random_04	AC	136 ms	7 MB
g++	small_00	AC	7 ms	3 MB
g++	small_01	AC	7 ms	3 MB
g++	small_02	AC	6 ms	3 MB
g++	small_03	AC	6 ms	3 MB
g++	small_04	AC	6 ms	3 MB
g++	small_05	AC	6 ms	3 MB
g++	small_06	AC	6 ms	3 MB
g++	small_07	AC	6 ms	3 MB
g++	small_08	AC	6 ms	3 MB
g++	small_09	AC	7 ms	3 MB
g++	small_values_00	AC	600 ms	9 MB
g++	small_width_query_00	AC	564 ms	9 MB
g++	small_width_query_01	AC	558 ms	9 MB
g++	small_width_query_02	AC	551 ms	9 MB
g++	small_width_query_03	AC	554 ms	9 MB
g++	small_width_query_04	AC	547 ms	9 MB
clang++	example_00	AC	6 ms	3 MB
clang++	max_random_00	AC	642 ms	9 MB
clang++	max_random_01	AC	617 ms	9 MB
clang++	max_random_02	AC	605 ms	9 MB
clang++	max_random_03	AC	631 ms	9 MB
clang++	max_random_04	AC	612 ms	9 MB
clang++	random_00	AC	494 ms	8 MB
clang++	random_01	AC	506 ms	9 MB
clang++	random_02	AC	471 ms	4 MB
clang++	random_03	AC	61 ms	8 MB
clang++	random_04	AC	136 ms	7 MB
clang++	small_00	AC	7 ms	3 MB
clang++	small_01	AC	6 ms	3 MB
clang++	small_02	AC	7 ms	3 MB
clang++	small_03	AC	6 ms	3 MB
clang++	small_04	AC	6 ms	3 MB
clang++	small_05	AC	6 ms	3 MB
clang++	small_06	AC	6 ms	3 MB
clang++	small_07	AC	6 ms	3 MB
clang++	small_08	AC	6 ms	3 MB
clang++	small_09	AC	6 ms	3 MB
clang++	small_values_00	AC	595 ms	9 MB
clang++	small_width_query_00	AC	557 ms	9 MB
clang++	small_width_query_01	AC	579 ms	9 MB
clang++	small_width_query_02	AC	572 ms	9 MB
clang++	small_width_query_03	AC	563 ms	9 MB
clang++	small_width_query_04	AC	565 ms	9 MB

Back to top page