コンテンツにスキップ

ビット演算

タグ「ビット演算」の記事 3 件

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

牛客小白月赛138 C - AND and OR

長さ nn の非負整数列 a1,…,ana_1, \dots, a_n と非負整数 kk が与えられます(2≤n≤2×1052 \le n \le 2 \times 10^5、0≤ai,k≤1090 \le a_i, k \le 10^9)。

(aiandaj)+(aioraj)=k(a_i \mathbin{\mathrm{and}} a_j) + (a_i \mathbin{\mathrm{or}} a_j) = k

を満たす 1≤i<j≤n1 \le i < j \le n があれば 1 つ出力し、なければ −1-1 を出力してください(nn の総和 ≤2×105\le 2 \times 10^5)。

実は、どんな非負整数 a,ba, b についても

(aandb)+(aorb)=a+b(a \mathbin{\mathrm{and}} b) + (a \mathbin{\mathrm{or}} b) = a + b

が成り立ちます。ビットごとに確かめると分かります。各ビットについて、aa と bb のそのビットの組み合わせは次の 3 通りです。

a,ba, b のビットANDORAND + ORa+ba + b
両方 0000000000
片方だけ 1100111111
両方 1111112222

どのビットでも AND と OR の寄与の和が aa と bb の寄与の和に一致するので、全体でも等しくなります。

したがって、問題は「ai+aj=ka_i + a_j = k となる i<ji < j を 1 つ見つけよ」という、よくある問題に言い換えられます。

(ai,i)(a_i, i) の組を値でソートしておきます。各要素 aia_i について、相手の値 k−aik - a_i が列にあるかを二分探索で調べます。見つかった相手が自分自身でなければ、そのペアが答えです。

k−ai=aik - a_i = a_i のときは、二分探索で見つかる最初の要素が自分自身になることがあります。ただ、同じ値がもう 1 つあれば、その要素を見たときに最初の要素が相手として見つかるので、取りこぼしはありません。

計算量はソートと二分探索で O(nlog⁡n)O(n \log n) です。

Python
import bisect
for _ in range(int(input())):
N, K = map(int,input().split())
A = list(map(int,input().split()))
Ai = [(A[i],i) for i in range(N)]
Ai.sort()
for i in range(N):
j = bisect.bisect_left(Ai,(K-Ai[i][0],-1))
if 0<=j<N and i!=j and K-Ai[i][0]==Ai[j][0]:
print(*sorted((Ai[i][1]+1,Ai[j][1]+1)))
break
else:
print(-1)

Ai は (値, 元の添字) の組をソートしたものです。(K-Ai[i][0],-1) で bisect_left すると、値が k−aik - a_i 以上である最初の位置が求まります。添字は 00 以上なので、第 2 要素に −1-1 を入れておけば、値が k−aik - a_i の組より必ず前に来ます。出力は i<ji < j の順にする必要があるので、元の添字をソートしてから出力しています。

Blitz Round #25 D - Shifting Sort

長さ nn の正整数列 a1,…,ana_1, \ldots, a_n があります。次の操作を好きな回数行えます。

  • 添字 ii を選ぶ。操作を始める前の aia_i の最上位ビットの位置を kk として、aia_i の下位 k+1k + 1 ビットを左に 1 つ巡回シフトする

たとえば 4=(100)24 = (100)_2 は (100)2→(001)2→(010)2→(100)2→⋯(100)_2 \to (001)_2 \to (010)_2 \to (100)_2 \to \cdots と変化します。

数列を広義単調増加にするのに必要な操作回数の最小値を求め、不可能なら −1-1 を出力する問題です。

  • 1≤n≤2⋅1051 \le n \le 2 \cdot 10^5、1≤ai≤2⋅1051 \le a_i \le 2 \cdot 10^5、テストケースの nn の総和は 2⋅1052 \cdot 10^5 以下

正確な問題文は元の問題ページを見てください。

aia_i のビット長を wiw_i とすると、操作は aia_i を wiw_i ビット幅で回転させるだけなので、aia_i がとりうる値は

ai を r 回回転させた値(0≤r<wi)a_i \text{ を } r \text{ 回回転させた値} \quad (0 \le r < w_i)

の wiw_i 通りで、そのときの操作回数は rr です。途中で最上位ビットが 00 になっても、回転の幅は操作前のビット長のまま変わらないことに注意します。

各要素の候補は高々 wiw_i 個しかないので、前から順に

dpi[v]=ai を値 v にしたときの、a1,…,ai を広義単調増加にする最小操作回数\mathrm{dp}_i[v] = a_i \text{ を値 } v \text{ にしたときの、} a_1, \ldots, a_i \text{ を広義単調増加にする最小操作回数}

を候補ごとに持つ DP ができます。遷移は

dpi[v]=r+min⁡u≤vdpi−1[u]\mathrm{dp}_i[v] = r + \min_{u \le v} \mathrm{dp}_{i-1}[u]

です。前の要素の候補と今の要素の候補をそれぞれ値でソートしておけば、min⁡u≤v\min_{u \le v} は尺取りで前から最小値を更新していくだけで求まります。

答えは min⁡vdpn[v]\min_v \mathrm{dp}_n[v] で、これが ∞\infty なら −1-1 です。

L=⌊log⁡2max⁡ai⌋+1L = \lfloor \log_2 \max a_i \rfloor + 1 とすると、候補は各要素で高々 LL 個なので、計算量はソートを含めて O(nLlog⁡L)O(n L \log L) です。

Python(upsolve)
INF = float("inf")
for _ in range(int(input())):
N = int(input())
A = list(map(int, input().split()))
dp = [(0, 0)]
for a in A:
w = a.bit_length()
cand = []
x = a
for r in range(w):
cand.append((x, r))
x = (x << 1 | x >> (w - 1)) & ((1 << w) - 1)
cand.sort()
ndp = []
best = INF
p = 0
for q, r in cand:
while p < len(dp) and dp[p][0] <= q:
best = min(best, dp[p][1])
p += 1
ndp.append((q, best + r))
dp = ndp
ans = min(y for _, y in dp)
if ans == INF:
print(-1)
else:
print(ans)

dp は (値, 最小操作回数) の組を値の昇順に並べたもので、best が「値が q 以下の前の候補のうちの最小操作回数」です。