AALC001 M - NAND
以上 未満の整数からなる長さ の数列 に対して、次の 2 種類のクエリを 個処理する問題です()。ここで NAND は、2 進法 30 桁で表したときの桁ごとの NAND(両方 なら 、そうでなければ )です。
1 p x: を に変更する。2 l r: とし、 の順に を と の NAND とする。 を出力する。
NAND は桁ごとに独立なので、30 桁それぞれについて別々に考えます。ある桁に注目すると、 のその桁 から のその桁を求める操作は、 のその桁で決まる 上の写像になります。
- の桁が のとき:(, )
- の桁が のとき:(, )
クエリ 2 の答えのその桁は、 のその桁に、 に対応する写像を順に適用したものです。写像の合成は結合的なので、各桁ごとに写像を要素とするセグメント木を作れば、区間 の写像の合成を で求められます。 のときは区間が空になり、合成は恒等写像なので がそのまま答えになります。
クエリ 1 では 30 本のセグメント木それぞれで 1 点更新をします。全体の計算量は、桁数を として です。
C++
#include "shogo-library/algebra/monoid.hpp"#include "shogo-library/base/all"#include "shogo-library/data_structures/segtree.hpp"
void solve() { LL(N, Q); VL(A, N); ary<SegTree<monoid::Mapping<2>>, 30> seg; rep(d, 30) { vec<monoid::Mapping<2>::S> init; init.reserve(N); for (ll a : A) { if ((a >> d) & 1) { init.push_back({1, 0}); } else { init.push_back({1, 1}); } } seg[d] = SegTree<monoid::Mapping<2>>(init); } rep(Q) { LL(q); if (q == 1) { LL(p, x); p--; rep(d, 30) { if ((x >> d) & 1) { seg[d].set(p, {1, 0}); } else { seg[d].set(p, {1, 1}); } } A[p] = x; } else { LL(l, r); l--; ll ans = 0; rep(d, 30) { ll t = seg[d].prod(l + 1, r)[(A[l] >> d) & 1]; ans |= t << d; } print(ans); } }}
int main() { std::cin.tie(nullptr); std::ios_base::sync_with_stdio(false); solve();}SegTree にはモノイドを表す構造体を渡します(1 点更新・区間積のセグメント木で、prod(l, r) は半開区間 の積です)。monoid::Mapping<2> は 上の写像の合成のモノイドで、写像 を std::array<int, 2> の で表します。区間の積は左の要素の写像から順に適用した合成なので、prod(l + 1, r) に の桁を渡せば の桁が得られます。
使用ライブラリ:cpp_include@397a51d