\(A_i-L_i, A_i\) からなる長さ \(2L\) の配列を作ってソートしておく. また, Fenwick Tree を別に用意しておく.

この配列を最初から順に見ていき, 以下の処理を行う.

要素が \(A_i-L_i\) のとき:

Fenwick Tree の \(i\) 番目の値を増やす.

要素が \(A_i\) のとき:

\(A_i+R_i\) が何番目の家までを含むかを二分探索で探す. これを \(k\) とすると, Fenwick Tree で \([i+1, k]\) に含まれる家の数の合計が, \(i\) 番目の家と相互に配り合う家の数となる.

これを合計すればいい. なお, このやり方の場合, \(A_i-L_i = A_j\) となる場合は \(A_i-L_i\) の方が小さいように扱わければいけないことが分かる.