コンテンツにスキップ

AALC001 M - NAND

サイト
AtCoder
コンテスト
AALC001
問題
M - NAND
難易度
-

00 以上 2302^{30} 未満の整数からなる長さ NN の数列 AA に対して、次の 2 種類のクエリを QQ 個処理する問題です(1≤N,Q≤2×1051 \le N, Q \le 2 \times 10^5)。ここで NAND は、2 進法 30 桁で表したときの桁ごとの NAND(両方 11 なら 00、そうでなければ 11)です。

  • 1 p x:ApA_p を xx に変更する。
  • 2 l r:Bl=AlB_l = A_l とし、i=l+1,…,ri = l + 1, \ldots, r の順に BiB_i を Bi−1B_{i-1} と AiA_i の NAND とする。BrB_r を出力する。

NAND は桁ごとに独立なので、30 桁それぞれについて別々に考えます。ある桁に注目すると、Bi−1B_{i-1} のその桁 bb から BiB_i のその桁を求める操作は、AiA_i のその桁で決まる {0,1}\{0, 1\} 上の写像になります。

  • AiA_i の桁が 11 のとき:b↦¬bb \mapsto \lnot b(0↦10 \mapsto 1, 1↦01 \mapsto 0)
  • AiA_i の桁が 00 のとき:b↦1b \mapsto 1(0↦10 \mapsto 1, 1↦11 \mapsto 1)

クエリ 2 の答えのその桁は、AlA_l のその桁に、Al+1,…,ArA_{l+1}, \ldots, A_r に対応する写像を順に適用したものです。写像の合成は結合的なので、各桁ごとに写像を要素とするセグメント木を作れば、区間 [l+1,r][l + 1, r] の写像の合成を O(log⁡N)O(\log N) で求められます。l=rl = r のときは区間が空になり、合成は恒等写像なので Bl=AlB_l = A_l がそのまま答えになります。

クエリ 1 では 30 本のセグメント木それぞれで 1 点更新をします。全体の計算量は、桁数を W=30W = 30 として O(W(N+Qlog⁡N))O(W (N + Q \log N)) です。

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) は半開区間 [l,r)[l, r) の積です)。monoid::Mapping<2> は {0,1}\{0, 1\} 上の写像の合成のモノイドで、写像 ff を std::array<int, 2> の (f(0),f(1))(f(0), f(1)) で表します。区間の積は左の要素の写像から順に適用した合成なので、prod(l + 1, r) に AlA_l の桁を渡せば BrB_r の桁が得られます。

使用ライブラリ:cpp_include@397a51d