How many Egdes?

$V_i=\{a_i,b_i,i\}$とします．この$V$を第1要素， つまり$a_i$の大きさ順で昇順ソートしたものを$V'$とします．

$i=1,2,\cdots,N$の順に見ていき， $1$以上$i-1$以下の数$j$が，$V'_{j,2} < V'_{i,2}$を満たすとします． このとき$V'_{i,3}$と$j$の間には辺が張られています．

これは$V'$が第1要素でソートされていることからわかります．

同様に$i=N,N-1,\cdots,1$の順に見ていき， $i+1$以上$N$以下の数$j$が， $V'_{i,2} < V'_{j,2}$を満たすとします． このとき$V'_{i,3}$と$j$の間には辺が張られています．

これらの計算は(数列の転倒数を求める要領で)セグメント木やFenwick Treeを用いて$O(N\mathbf{log}N)$で計算可能です．