考察
二つのRLE列は、どちらかのrun端点に到達するまで値の組が変わらない。
採用する候補: 二列のrunを二ポインタでマージ
棄却する候補: 長さLの列へ展開
Lは10^12で保存できない。
各列の現在run値と残長を持ち、d=min(rem1,rem2)だけ進め、値が等しければdを答えへ加え、残長0の側を次runへ移す。
典型の発動条件
RLEの同期走査
発動条件: 同じ巨大長の圧縮列同士を位置ごとに比較する。
run境界を二ポインタでmergeする。
問題固有の要素
必要なのは個々の位置でなく二列の境界和集合が作る区間だけである。
別の問題へ持ち帰る視点: 複数RLE列の位置演算は境界イベントを同期処理する。
正当性
両列の累積run端点のmergeが、値ペア一定区間の完全な分割になる。 残り長の小さいrun分だけ同時に進め、値が等しい区間長を足せば展開せず線形処理できる。
実装上の注意
- 累積長と答えを64ビットで持ち、片側だけrunが終わる場合に他側残長を保持する。
復習の核
- 展開可能な短列と比較し、run境界一致・交互境界・全区間同値を確認する。
計算量と制約
時間
O(N1+N2)、二列のrun数。
空間
O(N1+N2)、入力run。
制約との対応
公式制約の確認範囲: Time limit: 2 sec; Memory limit: 1024 MiB; Constraints: 1\leq L\leq 10 ^ {12}; 1\leq N _ 1,N _ 2\leq 10 ^ 5; 1\leq v _ {i,j}\leq 10 ^ 9\ (i\in\lbrace1,2\rbrace,1\leq j\leq N _ i); 1\leq l _ {i,j}\leq L\ (i\in\lbrace1,2\rbrace,1\leq j\leq N _ i); v _ {i,j}\neq v _ {i,j+1}\ (i\in\lbrace1,2\rbrace,1\leq j\lt N _ i); l _ {i,1}+l _ {i,2}+\cdots+l _ {i,N _ i}=L\ (i\in\lbrace1,2\rbrace); All values in the input are integers.
出典