ABC 357 F — Two Sequence Queries

考察

片方の配列へ同じ値を足したとき、積の増分はもう片方の配列の値に比例する。そこで、答えとなる積和に加えて両配列の和と区間長を持てば、区間内の要素を一つずつ見ずに更新できる。この四つを遅延セグメント木で管理する。

積和を更新するには何が足りないか

求めるのは、指定区間の各位置で二つの値を掛け、その結果を足した値である。区間内を毎回走査すると、最悪で O(NQ)O(NQ) 時間かかる。N,Q≤2×105N,Q\leq 2\times 10^5 なので、区間全体への加算と積和の取得を高速に行いたい。

まず、AA の各要素に xx を加える操作だけを考える。一つの位置 ii では、積の変化は次のように書ける。

(Ai+x)Bi−AiBi=xBi(A_i+x)B_i-A_iB_i=xB_i

従って、更新区間全体での積和の増分は、その区間の BB の和を xx 倍したものになる。積和だけを保存しても更新できず、もう片方の配列の和が必要である。対称に、BB への加算には区間の AA の和が必要になる。

では、追加した二つの和自身はどう更新すればよいか。長さ nn の区間で AA の各要素に xx を加えれば、AA の和は nxnx 増える。BB の和も同様なので、区間長も持てば、必要な情報をすべて更新できる。

ここで、区間 II の要約を次の四つ組で定義する。

S(I)=(n,a,b,p)S(I)=(n,a,b,p)
  • n=∣I∣n=|I|:区間長。
  • a=∑i∈IAia=\sum_{i\in I}A_i:AA の区間和。
  • b=∑i∈IBib=\sum_{i\in I}B_i:BB の区間和。
  • p=∑i∈IAiBip=\sum_{i\in I}A_iB_i:答えに使う積和。

実装上の名前では、順に len、sumA、sumB、sumAB に対応する。以下の和と積はすべて 998244353998244353 を法として計算する。加算・乗算だけで各式が成り立つので、途中でも余りを取ってよい。

二種類の加算を一つの操作で表す

遅延セグメント木では、子へまだ伝えていない操作をまとめて保存したい。そこで、AA に xx、BB に yy を加える操作を、加算量の組 f=(x,y)f=(x,y) で表す。種類1のクエリは (x,0)(x,0)、種類2で yy を加えるクエリは (0,y)(0,y) である。

一つの位置で両方を加算した後の積を展開する。

(Ai+x)(Bi+y)=AiBi+yAi+xBi+xy(A_i+x)(B_i+y)=A_iB_i+yA_i+xB_i+xy

これを区間全体で足すと、最後の xyxy は要素数だけ現れる。従って更新後の積和は次の値になる。

p′=p+ya+xb+nxyp'=p+ya+xb+nxy

元のクエリは片方への加算だが、遅延させた操作をまとめると x,yx,y の両方が非零になる。その合成後の操作にも対応するため、nxynxy を省いてはいけない。 要約全体への作用は、次の三式と、長さが変わらないことで定まる。

a′=a+nx,b′=b+ny,p′=p+ya+xb+nxy.\begin{aligned} a'&=a+nx,\\ b'&=b+ny,\\ p'&=p+ya+xb+nxy. \end{aligned}

右辺の a,b,pa,b,p はすべて、この操作を適用する直前の値である。実装では先に古い sumA、sumB から新しい sumAB を計算し、その後に二つの和を更新するか、更新前の要約から新しい要約を別に作る。この変換を mapping(f, S) と呼ぶ。

二つの操作 f1=(x1,y1)f_1=(x_1,y_1)、f2=(x2,y2)f_2=(x_2,y_2) をこの順に行うと、各要素への加算量は足し合わされる。

f2∘f1=(x1+x2, y1+y2)f_2\circ f_1=(x_1+x_2,\ y_1+y_2)

この合成を composition(f2, f1) とする。恒等作用、すなわち何もしない操作は (0,0)(0,0) である。保存する遅延タグはこの加算量の組だけでよく、積和の増分をタグへ別に保存する必要はない。

二要素で更新前の和と合成を確かめる

独自の小例として、区間全体で A=(1,2)A=(1,2)、B=(3,4)B=(3,4) とする。初期要約は (2,3,7,11)(2,3,7,11) である。この区間の AA に2を加え、続いて BB に5を加える。

段階aabbpp
初期3711
AA に2を加算7725
BB に5を加算71760

一回目は p=11+2⋅7=25p=11+2\cdot7=25、二回目は p=25+5⋅7=60p=25+5\cdot7=60 となる。二回目に使う a=7a=7 は、二回目の操作の直前の和である。一回目の更新より前の a=3a=3 ではない。

一方、タグをまとめれば (2,0)(2,0) と (0,5)(0,5) の合成は (2,5)(2,5) となる。初期要約へ一度に作用させると、今度は初期の a=3,b=7a=3,b=7 を使い、積和は次の値になる。

11+5⋅3+2⋅7+2⋅2⋅5=6011+5\cdot3+2\cdot7+2\cdot2\cdot5=60

更新後は A=(3,4),B=(8,9)A=(3,4),B=(8,9) なので、要素ごとの計算 3⋅8+4⋅9=603\cdot8+4\cdot9=60 とも一致する。合成後の作用で交差項 2⋅2⋅5=202\cdot2\cdot5=20 が補うのは、先の AA 加算によって増えた部分へ、後の BB 加算が作用する分である。逆順に処理しても、積和は 11+5⋅3=2611+5\cdot3=26、続いて 26+2⋅17=6026+2\cdot17=60 と同じになる。この加算同士は順序を交換できるが、各回の式にはその回の更新前の和を使う。

要約を木に載せてクエリを処理する

隣接する左右区間の要約は、四成分をそれぞれ足せば結合できる。この結合を op とする。積和は同じ位置どうしの積を足したものなので、左右をまたぐ積を追加する必要はない。空区間の要約は e=(0,0,0,0)e=(0,0,0,0) である。

  1. 位置 ii の葉を (1,Ai,Bi,AiBi)(1,A_i,B_i,A_iB_i) とし、下から op で結合して木を構築する。各ノードの遅延タグは (0,0)(0,0) で初期化する。
  2. 区間全体を更新するときは、ノードの要約へ mapping を適用し、既存タグの後に新しい操作を合成する。子へ降りる必要が生じるまでは、子への反映を保留する。
  3. 更新または照会が区間の一部だけにかかるなら、保留中のタグを左右の子へ適用して親のタグを恒等作用へ戻し、必要な子へ降りる。部分更新から戻ったら左右の要約を結合し直す。
  4. 積和の照会では、指定区間を覆うノードの要約を結合し、その pp を出力する。交わらない区間からは ee を返す。

AtCoder Library を使うなら、種類1・2は apply にそれぞれ (x,0)(x,0)・(0,y)(0,y) を渡し、種類3は prod の結果の積和を読む。要約・作用・合成はいずれも定数サイズなので、各クエリを O(log⁡N)O(\log N) 時間で処理できる。

典型の発動条件

積のrange updateに必要なmoment拡張

区間の答えだけでは一括更新できないとき、一要素での変化を展開し、総和を取って不足する量を探す。さらに、その補助量自身の更新に何が必要かも確認する。本問では積和から二つの一次の和、そこから長さを追加すると、それ以上の情報が不要になる。

遅延segment treeの作用設計

区間を結合できるだけでなく、一括更新を要約だけから計算でき、複数の更新も同じ形式にまとめられるときに候補になる。要約の結合、恒等作用、合成順、左右に更新してから結合しても結果が変わらないことを確認する。

問題固有の要素

同じ位置の二配列の積を問うため、AA への加算の係数には BB の和が、BB への加算の係数には AA の和が現れる。元のクエリが片方だけへの加算でも、操作をまとめた表現では両方への加算を扱う。この違いに注目すると、交差項 nxynxy の必要性を見落としにくい。

正当性

区間の要約は、その区間に含まれる要素数と三種類の総和を表す。左右区間が重ならなければ各成分の和が全体の要約になり、成分ごとの加算は結合的である。空要約 e=(0,0,0,0)e=(0,0,0,0) を結合しても値は変わらない。従って、区間をどのように分割して結合しても、同じ要約を得る。

mapping は一要素の積の展開を総和した式なので、その区間へ加算した後の要約を正確に返す。長さと三つの和はすべて左右の和であり、更新後の各成分もそれらの線形結合である。よって、左右を結合してから同じ操作を適用する結果と、左右へ適用してから結合する結果は一致する。空要約にはすべての成分が0のまま作用し、恒等作用 (0,0)(0,0) はどの要約も変えない。

二つの操作を順に適用することは、各要素へ加算量の成分和を一度に加えることと等しい。mapping が各要素への操作を正確に要約するので、タグを composition でまとめても要約は一致する。従って、子への更新を保留しても、子へ降りる前に合成タグを伝播すれば、一回ずつ更新した場合と同じ要約が得られる。

葉の初期値は定義どおりであり、結合・全体更新・タグの伝播・部分更新後の再結合はいずれもこの意味を保つ。照会区間を重複なく分割して結合した要約の pp は、現在の配列の指定区間における積和そのものである。以上は加算・乗算の等式だけを用いるため、法上で計算した値も要求された余りに一致する。

実装上の注意

  • mapping の右辺はすべて更新前の値から評価する。sumAB を計算し終えてから sumA、sumB を書き換える。
  • 入力の1始まり閉区間 [l,r][l,r] は、0始まり半開区間を使う実装では [l−1,r)[l-1,r) にそろえる。長さ1や全区間も同じ規則で扱う。
  • 初期値・加算量を法で正規化し、積の途中でも余りを取る。各因子を法未満にしても、nxynxy を剰余なしで一度に掛けると64 bit整数に収まらない。剰余整数型を使うか、二因子ずつ十分な幅で掛けて剰余を取る。

復習の核

  • 区間の答えを一括更新できなければ、一要素の変化を展開してから総和を取り、必要な補助量を洗い出す。その補助量自身も更新できるか確かめる。
  • 元のクエリだけでなく、複数クエリを合成した操作にも更新式が対応しているか確認する。
  • 二回の作用と合成後の一回の作用を小例で比べる。「更新前」は、適用する操作ごとの直前を指す。

計算量と制約

時間

葉の初期化と木の構築に O(N)O(N) 時間、各クエリに O(log⁡N)O(\log N) 時間かかる。全体で O(N+Qlog⁡N)O(N+Q\log N) 時間。

空間

O(N)O(N) 個のノードに四成分の要約と二成分の遅延タグを保存する。入力配列と木を合わせて O(N)O(N) 空間。

制約との対応

1≤N,Q≤2×1051\leq N,Q\leq 2\times10^5 に対し、各クエリでは対数個のノードを処理する。初期値は 0≤Ai,Bi≤1090\leq A_i,B_i\leq10^9、加算量は 1≤x≤1091\leq x\leq10^9 だが、答えは 998244353998244353 で割った余りなので、配列の実際の値を蓄積せず法上の要約とタグを保持すればよい。1≤l≤r≤N1\leq l\leq r\leq N で入力の照会区間は空でないが、木の内部で使う空要約も上記の規則で処理できる。

出典

分類・前提・執筆情報

掲載状態: 収録済み

Two Sequence Queries の公式問題ページ(外部リンク)

最終確認:

学習上の位置付け

主題の単元: 区間更新を要約へ作用させる

主題
追加で学ぶ技能
    なし
    既習技能
    • 区間monoid要約: 要約する値・単位元・結合的な合成規則を定義し、prefix fold・Segment Tree・SWAGで答えを求められる。

    主タグ: 遅延評価する区間作用

    補助タグ: 区間monoid要約

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

    学習の位置

    体系上の位置: 区間更新を要約へ作用させる

    • 更新作用の合成順と要約への適用を定義し、遅延評価で保てる。

    先に読む単元:

    • 区間monoid要約 — queryに十分な値と結合順・単位元を定義し、Segment Treeまたはprefix foldで動的区間要約を保つ。その発動条件と正当化原理を比較可能な独立教材として学ぶ。

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

    • 過去の版の保存・rollback・構造共有。

    学習記録

    状況更新: 更新記録なし

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

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

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

    同じ単元の問題