ABC 365 E — Xor Sigma Problem

考察

XORの総和はbitごとの1になる区間数に分解できる。固定bitではAを0/1列Bとみなし、区間XORはprefix XOR Cの両端が異なるかで決まる。

全ての非空区間ならC中の0個数×1個数で数えられるが、問題は長さ2以上だけなので、長さ1区間の寄与ΣB_iを引く必要がある。

採用する候補: 各bitでprefix parityの0,1出現数を数え、異parity pair数から単項区間を除いてbit重みを掛ける。

棄却する候補: 各左端から右へXORを更新し、全長2以上の区間値を足す。

一区間のXORは速く得られても区間数が二次で、同じprefix情報を共有できない。

必要な各bit bについてC=0からA_iのb bitを順にxorし、prefix parity 0/1の個数を数える。同bitが1の全非空区間数cnt0·cnt1からA_iの当該bitが1の個数を引き、2^b倍して答えへ加える。

典型の発動条件

XORのbit別寄与

発動条件: XOR値の総和を多数の区間・pairについて求めるとき。

各bitを独立なparity問題として数え、最後にbit重みを戻す。

prefix parityの異値pair計数

発動条件: 区間xorが1となる端点組数を求めるとき。

prefix値0と1の頻度の積で全組をまとめて数える。

問題固有の要素

長さ制限を端点pairの添字差として直接数えるより、数えやすい全区間から長さ1だけ引くと簡潔になる。

別の問題へ持ち帰る視点: ほぼ全範囲を求める制約では、補集合が小さければ全体−例外へ変える。

正当性

C_0=0を含むN+1個のprefix parityから異なる二値を選ぶ組数はcount0·count1である。 隣接prefix pair C_{i−1} xor C_iはB_iそのものなので、除外すべき長さ1区間のbit寄与をΣB_iで正確に引ける。 区間を列挙せず、全端点pairを二種類の頻度積へ集約できる。

実装上の注意

  • prefixには空prefix C_0を必ず含める。A_i<2^27付近までの全bitを扱い、組数×bit値は64 bitで計算する。

復習の核

  • N=2で唯一の長さ2区間と一致するか確認する。全非空区間を数えた式のどこから長さ1を引いたかを明示する。

計算量と制約

時間

O(NB)、Bは値bit長。

空間

O(1)補助、prefix parity counts。

制約との対応

公式制約の確認範囲: Time limit: 2 sec; Memory limit: 1024 MiB; Constraints: 2 \leq N \leq 2 \times 10^5; 1 \leq A_i \leq 10^8; All input values are integers.

出典

分類・前提・執筆情報

掲載状態: 収録済み

Xor Sigma Problem の公式問題ページ(外部リンク)

最終確認:

学習上の位置付け

主題の単元: 局所寄与へ分解して集計順を交換する

主題
追加で学ぶ技能
    なし
    既習技能
      なし

      主タグ: 寄与の数え上げと順序交換

      執筆: abc-explanation-author1.1.1 / revision 2

      学習の位置

      体系上の位置: 局所寄与へ分解して集計順を交換する

      • 数える対象を要素・組・値・区間のいずれかで一意に固定し、各対象が含まれる回数または指示変数の期待値を先に求めて総和できる。

      この解説で扱わないこと:

      • active集合を時刻・座標順に更新するevent sweep、更新列を逆から読むだけの処理、および成分ごとの解を単に掛け合わせる構造判定。

      学習記録

      状況更新: 更新記録なし

      復習設定更新: 更新記録なし

      端末内の保存状態を確認しています。

      要復習一覧 / 学習記録のバックアップ / 解説に戻る

      同じ単元の問題