matsutaku-library

This documentation is automatically generated by competitive-verifier/competitive-verifier

View the Project on GitHub MatsuTaku/matsutaku-library

:heavy_check_mark: test/aoj/aoj-range_update_query.test.cpp

Code

#define PROBLEM "https://onlinejudge.u-aizu.ac.jp/problems/DSL_2_D"
#include "include/mtl/dual_segment_tree.hpp"
#include <bits/stdc++.h>
using namespace std;

struct OR {
    int a,b;
    OR() : a(1), b(0) {}
    OR(int b) : a(0), b(b) {}
    OR& operator=(int x) {
        a = 0;
        b = x;
        return *this;
    }
    OR& operator*=(const OR& r) {
        a *= r.a;
        b = b * r.a + r.b;
        return *this;
    }
};

int main() {
    int n,q; cin>>n>>q;
    vector<int> init(n, (1u<<31)-1);
    DualSegmentTree<OR> dst(init.begin(), init.end());
    for (int i = 0; i < q; i++) {
        int t; cin>>t;
        if (t == 0) {
            int s,t,x; cin>>s>>t>>x;
            ++t;
            dst.update(s, t, x);
        } else {
            int i; cin>>i;
            cout << dst.get(i).b << endl;
        }
    }
}
#line 1 "test/aoj/aoj-range_update_query.test.cpp"
#define PROBLEM "https://onlinejudge.u-aizu.ac.jp/problems/DSL_2_D"
#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/dual_segment_tree.hpp"
#include <cstddef>
#include <vector>
#include <algorithm>
#include <stack>
#line 8 "include/mtl/dual_segment_tree.hpp"
#if __cpp_concepts >= 202002L
#include <concepts>

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

template <
#if __cpp_concepts >= 202002L
  IdDualSegmentTreeMonoid
#else
  class
#endif
    M
>
class DualSegmentTree {
 private:
  size_t size_;
  using tree_type = std::vector<M>;
  tree_type tree_;
  std::vector<size_t> ids_;

  int log(size_t x) const {
    return 64 - bm::clz(x-1);
  }

 public:
  explicit DualSegmentTree(size_t size) :
      size_(size),
      tree_(size_*2) {
    ids_.reserve(log(size)*2);
  }

  template <typename Iter>
  explicit DualSegmentTree(Iter begin, Iter end)
    : DualSegmentTree(std::distance(begin, end)) {
    static_assert(std::is_convertible<typename std::iterator_traits<Iter>::value_type, M>::value, "");
    std::copy(begin, end, tree_.begin()+size_);
  }

  void update(size_t l, size_t r, const M& e) {
    assert(l <= r and r <= size_);
    if (l == r) return;
    _lazy_propagation(l, r);

    for (size_t _l=l+size_, _r=r+size_, s=1; _l<_r; _l>>=1, _r>>=1, s*=2) {
      if (_l&1) {
        tree_[_l] *= e;
        ++_l;
      }
      if (_r&1) {
        --_r;
        tree_[_r] *= e;
      }
    }
  }
  void update(size_t i, const M& e) {
    update(i, i+1, e);
  }

  void set(size_t index, const M& e) {
    assert(index < size_);
    _lazy_propagation(index, index+1);
    tree_[size_ + index] = e;
  }

  M get(size_t index) {
    assert(index < size_);
    _lazy_propagation(index, index+1);
    return tree_[size_ + index];
  }

 private:
  void _set_ids(size_t l, size_t r) {
    ids_.clear();
    auto _l=l+size_, _r=r+size_;
    auto lth = _l/(_l&(-_l))/2;
    auto rth = _r/(_r&(-_r))/2;
    for (; _l<_r; _l>>=1, _r>>=1) {
      if (_r <= rth) ids_.emplace_back(_r);
      if (_l <= lth) ids_.emplace_back(_l);
    }
    for (; _l>0; _l>>=1) {
      ids_.emplace_back(_l);
    }
  }

  void _propagate(size_t id) {
    if (id >= size_) return;
    M e = tree_[id];
    tree_[id] = M();
    tree_[id*2] *= e;
    tree_[id*2+1] *= e;
  }

  void _lazy_propagation(size_t l, size_t r) {
    if (l == r) return;
    _set_ids(l, r);
    for (auto it = ids_.rbegin(); it != ids_.rend(); ++it)
      _propagate(*it);
  }

 public:
  template<class F>
  size_t max_right(size_t begin, size_t end, F f) {
    if (begin == end) return end;
    M p;
    std::stack<std::pair<size_t, M>> rps;
    auto l = size_ + begin;
    auto r = size_ + end;
    _lazy_propagation(begin, end);
    auto access = [&](size_t i) {
      _propagate(i);
      return tree_[i].first;
    };
    while (l < r and f(p * access(l))) {
      if (l&1) p = p * tree_[l++].first;
      if (r&1) {
        rps.emplace(r, access(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 * access(l)));
      l <<= 1;
      auto pl = access(l);
      if (f(p * pl)) {
        p = p * pl;
        l++;
      }
    }
    return l - size_;
  }
  template<bool (*F)(M)>
  size_t max_right(size_t begin, size_t end) {
    return max_right(begin, end, [](M x) { return F(x); });
  }

  template<class F>
  size_t min_left(size_t begin, size_t end, F f) {
    if (end == begin) return begin;
    M p;
    std::stack<std::pair<size_t, M>> lps;
    auto l = size_ + begin;
    auto r = size_ + end;
    _lazy_propagation(begin, end);
    auto access = [&](size_t i) {
      _propagate(i);
      return tree_[i].first;
    };
    while (l < r and f(access(r-1) * p)) {
      if (l&1) {
        lps.emplace(l, access(l));
        l++;
      }
      if (r&1) p = tree_[r-1].first * 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(access(r-1) * p));
      r <<= 1;
      auto pr = access(r-1);
      if (f(pr * p)) {
        p = pr * p;
        --r;
      }
    }
    return r - size_;
  }
  template<bool (*F)(M)>
  size_t min_left(size_t begin, size_t end) {
    return min_left(begin, [](M x) { return F(x); });
  }

 private:
  template<bool> struct iterator_base;
  template<bool> friend struct iterator_base;
  template<bool Const>
  struct iterator_base {
    using value_type = std::conditional_t<Const, const M, M>;
    using pointer = std::conditional_t<Const, const M*, M*>;
    using reference = std::conditional_t<Const, const M&, M&>;
    using difference_type = std::ptrdiff_t;
    using iterator_category = std::random_access_iterator_tag;
    DualSegmentTree* tree_ptr;
    size_t idx;
    iterator_base(DualSegmentTree* tree_ptr, size_t idx) : tree_ptr(tree_ptr), idx(idx) {
      assert(idx >= tree_ptr->size_ and idx <= tree_ptr->size_*2);
      if (idx < tree_ptr->tree_.size()) tree_ptr->get(idx - tree_ptr->size_);
    }
    iterator_base& operator+=(difference_type n) { 
      auto l = idx;
      idx += n;
      if (idx == tree_ptr->tree_.size()) return *this;
      auto x = l ^ idx;
      int h = bm::ctz(~x);
      --h;
      while (h >= 0) {
        tree_ptr->_propagate(idx>>h);
        --h;
      }
      return *this;
    }
    iterator_base& operator-=(difference_type n) { 
      auto r = idx;
      idx -= n;
      auto x = idx ^ r;
      int h = bm::ctz(~x);
      --h;
      while (h >= 0) {
        tree_ptr->_propagate(idx>>h);
        --h;
      }
      return *this;
    }
    iterator_base& operator++() { 
      return *this += 1;
    }
    iterator_base& operator--() {
      return *this -= 1;
    }
    iterator_base operator++(int) { auto tmp = *this; ++idx; return tmp; }
    iterator_base operator--(int) { auto tmp = *this; --idx; return tmp; }
    iterator_base operator+(difference_type n) const { return iterator_base(*this) += n; }
    iterator_base operator-(difference_type n) const { return iterator_base(*this) -= n; }
    bool operator==(const iterator_base& o) const { return tree_ptr == o.tree_ptr and idx == o.idx; }
    bool operator!=(const iterator_base& o) const { return tree_ptr != o.tree_ptr or idx != o.idx; }
    difference_type operator-(const iterator_base& o) const { return idx - o.idx; }
    reference operator*() const { return tree_ptr->tree_[idx]; }
    pointer operator->() const { return &tree_ptr->tree_[idx]; }
  };
 public:
  using iterator = iterator_base<false>;
  using const_iterator = iterator_base<true>;
  const_iterator begin() const { return const_iterator(this, size_); }
  const_iterator end() const { return const_iterator(this, size_*2); }
  const_iterator cbegin() const { return const_iterator(this, size_); }
  const_iterator cend() const { return const_iterator(this, size_*2); }
  iterator begin() { return iterator(this, size_); }
  iterator end() { return iterator(this, size_*2); }

};

#line 3 "test/aoj/aoj-range_update_query.test.cpp"
#include <bits/stdc++.h>
using namespace std;

struct OR {
    int a,b;
    OR() : a(1), b(0) {}
    OR(int b) : a(0), b(b) {}
    OR& operator=(int x) {
        a = 0;
        b = x;
        return *this;
    }
    OR& operator*=(const OR& r) {
        a *= r.a;
        b = b * r.a + r.b;
        return *this;
    }
};

int main() {
    int n,q; cin>>n>>q;
    vector<int> init(n, (1u<<31)-1);
    DualSegmentTree<OR> dst(init.begin(), init.end());
    for (int i = 0; i < q; i++) {
        int t; cin>>t;
        if (t == 0) {
            int s,t,x; cin>>s>>t>>x;
            ++t;
            dst.update(s, t, x);
        } else {
            int i; cin>>i;
            cout << dst.get(i).b << endl;
        }
    }
}

Test cases

Env Name Status Elapsed Memory
g++ 00_sample_00.in :heavy_check_mark: AC 5 ms 3 MB
g++ 00_sample_01.in :heavy_check_mark: AC 5 ms 3 MB
g++ 01_rand_00.in :heavy_check_mark: AC 5 ms 3 MB
g++ 01_rand_01.in :heavy_check_mark: AC 5 ms 3 MB
g++ 01_rand_02.in :heavy_check_mark: AC 5 ms 3 MB
g++ 01_rand_03.in :heavy_check_mark: AC 7 ms 3 MB
g++ 01_rand_04.in :heavy_check_mark: AC 9 ms 3 MB
g++ 01_rand_05.in :heavy_check_mark: AC 23 ms 3 MB
g++ 02_corner_00.in :heavy_check_mark: AC 5 ms 3 MB
g++ 02_corner_01.in :heavy_check_mark: AC 5 ms 3 MB
g++ 03_large_00.in :heavy_check_mark: AC 26 ms 4 MB
g++ 03_large_01.in :heavy_check_mark: AC 28 ms 4 MB
g++ 03_large_02.in :heavy_check_mark: AC 26 ms 4 MB
g++ 03_large_03.in :heavy_check_mark: AC 28 ms 4 MB
g++ 04_maximum_00.in :heavy_check_mark: AC 198 ms 5 MB
g++ 04_maximum_01.in :heavy_check_mark: AC 207 ms 5 MB
g++ 04_maximum_02.in :heavy_check_mark: AC 121 ms 5 MB
g++ 04_maximum_03.in :heavy_check_mark: AC 135 ms 5 MB
g++ 05_critical_00.in :heavy_check_mark: AC 126 ms 5 MB
g++ 05_critical_01.in :heavy_check_mark: AC 155 ms 5 MB
g++ 05_critical_02.in :heavy_check_mark: AC 75 ms 5 MB
g++ 05_critical_03.in :heavy_check_mark: AC 77 ms 5 MB
clang++ 00_sample_00.in :heavy_check_mark: AC 6 ms 3 MB
clang++ 00_sample_01.in :heavy_check_mark: AC 5 ms 3 MB
clang++ 01_rand_00.in :heavy_check_mark: AC 5 ms 3 MB
clang++ 01_rand_01.in :heavy_check_mark: AC 5 ms 3 MB
clang++ 01_rand_02.in :heavy_check_mark: AC 5 ms 3 MB
clang++ 01_rand_03.in :heavy_check_mark: AC 6 ms 3 MB
clang++ 01_rand_04.in :heavy_check_mark: AC 8 ms 3 MB
clang++ 01_rand_05.in :heavy_check_mark: AC 15 ms 3 MB
clang++ 02_corner_00.in :heavy_check_mark: AC 5 ms 3 MB
clang++ 02_corner_01.in :heavy_check_mark: AC 5 ms 3 MB
clang++ 03_large_00.in :heavy_check_mark: AC 17 ms 4 MB
clang++ 03_large_01.in :heavy_check_mark: AC 18 ms 4 MB
clang++ 03_large_02.in :heavy_check_mark: AC 17 ms 3 MB
clang++ 03_large_03.in :heavy_check_mark: AC 18 ms 3 MB
clang++ 04_maximum_00.in :heavy_check_mark: AC 122 ms 5 MB
clang++ 04_maximum_01.in :heavy_check_mark: AC 126 ms 5 MB
clang++ 04_maximum_02.in :heavy_check_mark: AC 133 ms 5 MB
clang++ 04_maximum_03.in :heavy_check_mark: AC 127 ms 5 MB
clang++ 05_critical_00.in :heavy_check_mark: AC 126 ms 5 MB
clang++ 05_critical_01.in :heavy_check_mark: AC 145 ms 5 MB
clang++ 05_critical_02.in :heavy_check_mark: AC 79 ms 5 MB
clang++ 05_critical_03.in :heavy_check_mark: AC 81 ms 5 MB
Back to top page