Created
February 1, 2021 10:53
-
-
Save hitonanode/143b00ae375bc8a3c6f36750ad16195a to your computer and use it in GitHub Desktop.
CS Academy Round #70 "And or Max"
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
#ifndef ATCODER_LAZYSEGTREE_HPP | |
#define ATCODER_LAZYSEGTREE_HPP 1 | |
#include <algorithm> | |
#include <cassert> | |
#include <iostream> | |
#include <vector> | |
// #include "atcoder/internal_bit" | |
#ifndef ATCODER_INTERNAL_BITOP_HPP | |
#define ATCODER_INTERNAL_BITOP_HPP 1 | |
#ifdef _MSC_VER | |
#include <intrin.h> | |
#endif | |
namespace atcoder { | |
namespace internal { | |
// @param n `0 <= n` | |
// @return minimum non-negative `x` s.t. `n <= 2**x` | |
int ceil_pow2(int n) { | |
int x = 0; | |
while ((1U << x) < (unsigned int)(n)) x++; | |
return x; | |
} | |
// @param n `1 <= n` | |
// @return minimum non-negative `x` s.t. `(n & (1 << x)) != 0` | |
int bsf(unsigned int n) { | |
#ifdef _MSC_VER | |
unsigned long index; | |
_BitScanForward(&index, n); | |
return index; | |
#else | |
return __builtin_ctz(n); | |
#endif | |
} | |
} // namespace internal | |
} // namespace atcoder | |
#endif // ATCODER_INTERNAL_BITOP_HPP | |
namespace atcoder { | |
template <class S, | |
S (*op)(S, S), | |
S (*e)(), | |
class F, | |
S (*mapping)(F, S), | |
F (*composition)(F, F), | |
F (*id)()> | |
struct lazy_segtree { | |
public: | |
lazy_segtree() : lazy_segtree(0) {} | |
explicit lazy_segtree(int n) : lazy_segtree(std::vector<S>(n, e())) {} | |
explicit lazy_segtree(const std::vector<S>& v) : _n(int(v.size())) { | |
log = internal::ceil_pow2(_n); | |
size = 1 << log; | |
d = std::vector<S>(2 * size, e()); | |
lz = std::vector<F>(size, id()); | |
for (int i = 0; i < _n; i++) d[size + i] = v[i]; | |
for (int i = size - 1; i >= 1; i--) { | |
update(i); | |
} | |
} | |
void set(int p, S x) { | |
assert(0 <= p && p < _n); | |
p += size; | |
for (int i = log; i >= 1; i--) push(p >> i); | |
d[p] = x; | |
for (int i = 1; i <= log; i++) update(p >> i); | |
} | |
S get(int p) { | |
assert(0 <= p && p < _n); | |
p += size; | |
for (int i = log; i >= 1; i--) push(p >> i); | |
return d[p]; | |
} | |
S prod(int l, int r) { | |
assert(0 <= l && l <= r && r <= _n); | |
if (l == r) return e(); | |
l += size; | |
r += size; | |
for (int i = log; i >= 1; i--) { | |
if (((l >> i) << i) != l) push(l >> i); | |
if (((r >> i) << i) != r) push(r >> i); | |
} | |
S sml = e(), smr = e(); | |
while (l < r) { | |
if (l & 1) sml = op(sml, d[l++]); | |
if (r & 1) smr = op(d[--r], smr); | |
l >>= 1; | |
r >>= 1; | |
} | |
return op(sml, smr); | |
} | |
S all_prod() { return d[1]; } | |
void apply(int p, F f) { | |
assert(0 <= p && p < _n); | |
p += size; | |
for (int i = log; i >= 1; i--) push(p >> i); | |
d[p] = mapping(f, d[p]); | |
for (int i = 1; i <= log; i++) update(p >> i); | |
} | |
void apply(int l, int r, F f) { | |
assert(0 <= l && l <= r && r <= _n); | |
if (l == r) return; | |
l += size; | |
r += size; | |
for (int i = log; i >= 1; i--) { | |
if (((l >> i) << i) != l) push(l >> i); | |
if (((r >> i) << i) != r) push((r - 1) >> i); | |
} | |
{ | |
int l2 = l, r2 = r; | |
while (l < r) { | |
if (l & 1) all_apply(l++, f); | |
if (r & 1) all_apply(--r, f); | |
l >>= 1; | |
r >>= 1; | |
} | |
l = l2; | |
r = r2; | |
} | |
for (int i = 1; i <= log; i++) { | |
if (((l >> i) << i) != l) update(l >> i); | |
if (((r >> i) << i) != r) update((r - 1) >> i); | |
} | |
} | |
template <bool (*g)(S)> int max_right(int l) { | |
return max_right(l, [](S x) { return g(x); }); | |
} | |
template <class G> int max_right(int l, G g) { | |
assert(0 <= l && l <= _n); | |
assert(g(e())); | |
if (l == _n) return _n; | |
l += size; | |
for (int i = log; i >= 1; i--) push(l >> i); | |
S sm = e(); | |
do { | |
while (l % 2 == 0) l >>= 1; | |
if (!g(op(sm, d[l]))) { | |
while (l < size) { | |
push(l); | |
l = (2 * l); | |
if (g(op(sm, d[l]))) { | |
sm = op(sm, d[l]); | |
l++; | |
} | |
} | |
return l - size; | |
} | |
sm = op(sm, d[l]); | |
l++; | |
} while ((l & -l) != l); | |
return _n; | |
} | |
template <bool (*g)(S)> int min_left(int r) { | |
return min_left(r, [](S x) { return g(x); }); | |
} | |
template <class G> int min_left(int r, G g) { | |
assert(0 <= r && r <= _n); | |
assert(g(e())); | |
if (r == 0) return 0; | |
r += size; | |
for (int i = log; i >= 1; i--) push((r - 1) >> i); | |
S sm = e(); | |
do { | |
r--; | |
while (r > 1 && (r % 2)) r >>= 1; | |
if (!g(op(d[r], sm))) { | |
while (r < size) { | |
push(r); | |
r = (2 * r + 1); | |
if (g(op(d[r], sm))) { | |
sm = op(d[r], sm); | |
r--; | |
} | |
} | |
return r + 1 - size; | |
} | |
sm = op(d[r], sm); | |
} while ((r & -r) != r); | |
return 0; | |
} | |
private: | |
int _n, size, log; | |
std::vector<S> d; | |
std::vector<F> lz; | |
void update(int k) { d[k] = op(d[2 * k], d[2 * k + 1]); } | |
void all_apply(int k, F f) { | |
d[k] = mapping(f, d[k]); | |
if (k < size) { | |
lz[k] = composition(f, lz[k]); | |
if (d[k].fail) push(k), update(k); // MODIFIED!!! | |
} | |
} | |
void push(int k) { | |
all_apply(2 * k, lz[k]); | |
all_apply(2 * k + 1, lz[k]); | |
lz[k] = id(); | |
} | |
}; | |
} // namespace atcoder | |
#endif // ATCODER_LAZYSEGTREE_HPP | |
/////////////////////////////////////////////////////// ACL ここまで /////////////////////////////////////////////////////// | |
namespace RangeBitwiseAndOrRangeMax { | |
using UINT = uint32_t; | |
constexpr UINT digit = 20; | |
constexpr int mask = (1 << digit) - 1; | |
struct S { | |
UINT max; // 区間最大値 | |
UINT upper; // 区間内全要素の bitwise or | |
UINT lower; // 区間内全要素の bitwise and | |
bool fail; | |
S(UINT x = 0) : max(x), upper(x), lower(x), fail(false) {} | |
}; | |
S e() { return S(); } | |
S op(S l, S r) { | |
l.max = std::max(l.max, r.max); | |
l.upper |= r.upper; | |
l.lower &= r.lower; | |
return l; | |
} | |
struct F { | |
UINT bit_and; | |
UINT bit_or; | |
F() : bit_and(mask), bit_or(0) {} | |
F(UINT a, UINT o) : bit_and(a), bit_or(o) {} | |
static F b_and(UINT a) noexcept { return {a, 0}; } | |
static F b_or(UINT a) noexcept { return {mask, a}; } | |
}; | |
F composition(F fnew, F fold) { | |
return F{fnew.bit_and & fold.bit_and, fnew.bit_or | (fnew.bit_and & fold.bit_or)}; | |
} | |
F id() { return F(); } | |
S mapping(F f, S x) { | |
if ((x.upper - x.lower) & (~f.bit_and | f.bit_or)) { | |
// 区間内で立っている要素と立っていない要素が混在するような bit で | |
// 変更が起きた場合のみ計算失敗(新たな最大値が不明なので) | |
x.fail = true; | |
return x; | |
} | |
x.upper = (x.upper & f.bit_and) | f.bit_or; | |
x.lower = (x.lower & f.bit_and) | f.bit_or; | |
x.max = (x.max & f.bit_and) | f.bit_or; | |
return x; | |
} | |
using segtree = atcoder::lazy_segtree<S, op, e, F, mapping, composition, id>; | |
} // namespace RangeBitwiseAndOrRangeMax | |
#include <iostream> | |
using namespace std; | |
int main() { | |
cin.tie(nullptr), ios::sync_with_stdio(false); | |
uint32_t N, Q, a; | |
cin >> N >> Q; | |
vector<RangeBitwiseAndOrRangeMax::S> init(N); | |
for (auto& v : init) cin >> a, v = {a}; | |
RangeBitwiseAndOrRangeMax::segtree segtree(init); | |
while (Q--) { | |
uint32_t q, l, r, x; | |
cin >> q >> l >> r; | |
l--; | |
if (q == 3) cout << segtree.prod(l, r).max << '\n'; | |
else { | |
cin >> x; | |
if (q == 1) segtree.apply(l, r, RangeBitwiseAndOrRangeMax::F::b_and(x)); | |
if (q == 2) segtree.apply(l, r, RangeBitwiseAndOrRangeMax::F::b_or(x)); | |
} | |
} | |
} |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment