与えられる \(2\) つの数を \(A, B\) とします。 \(B\) の \((a_i, l_i)\) の組を代わりに \((b_i, r_i)\) と書くことにします。

最初の工夫

筆算をするときのように、下の位から見ていきます。よって、 \(a_i, b_i, l_i, r_i\) は reverse しておきます。 また、 \(A, B\) の桁数が違うと不便であるため、桁数の少ない方を適切に \(0\) 埋めします。

考察

この問題で一番考察が難しいのは、繰り上がりの処理です。

「\(A, B\) の両方の桁の数字が一定になる部分」はやはり区間で表されるので、その区間を下の位から見ます。

\(1111111333333 + 2222222777777 = 3333334111110\) のように、下から見て行って、\(A, B\) のいずれかの桁の数字が変化したとき、その最も下の位と、 \(2\) 番目に下の位の値が変わっていることがあります。（この例だと下から \(7\) 桁目は \(4\)、下から \(8\) 桁目は \(3\) になっています）

しかし、 \(2\) 番目から次の\(A, B\) の桁の数字の変化まではずっと同じ桁の数字を保ちます。よって、\(A, B\) の桁の数字が変化した瞬間は、「その位」の処理をし、 「次の桁の位」に進みます。

その後は区間をまとめて処理することができ、「次にどちらかの数字が変化する点」までジャンプすることが出来ます。

ここで気をつけないといけないのは、

• 一の位において「桁の数字が変化した」ときの処理をする必要がある
• 「次の桁の位」に進んだが、その瞬間 \(A,B\) のいずれか桁の数字が変わったとき、再び「桁の数字が変化した」ときの処理をする必要がある
• 同時に桁が変わるときにバグが起きやすい
• 最も上の位で繰り上がりが発生したとき、\(A+B\) は \(1\) 桁増えて \(1\) が追加される（例： \(22+99 = 121\) ）

などがあり、複雑です。実装を工夫したり、コーナーケースを考える必要があります。

最後に、答えに対してランレングス圧縮の処理を行い（ここでオーバーフローに注意してください）、再度 reverse して出力すればよいです。時間計算量は \(O(|a|+|b|)\) です。

実装例(C++)