ABC260 E - At Least One (500)
$ (A_i.B_i)のペアで昇順にソートする
あるところまでは$ Bをそれから右は$ Aを使うということにする
左端としてあり得る最大値は$ A_iとそれまでのBの最小値の小さい方
右端としてあり得る最小値は$ A_nとそれまでのBの最大値の大きい方
左端に対する右端の値が小さいなら更新する
それまでのBの最大値と最小値を$ B_iで更新可能なら更新
最後に全てをBを使った場合の左端と右端についても上と同じ処理をする
Mについてそれぞれの$ iで以下を行う
左端と右端のペアから左辺$ iが$ i以上で最小のを見つける
無ければ飛ばす
最小幅は$ r - i + 1
最大幅は$ M - 1
$ iを左端にした場合はこれらの間の長さは全て取れるのでこの間について個数を1個ずつ足す
愚直に行うと$ \mathcal{O}(M^2)なのでBITで計算量を落とす
全体で$ \mathcal{O}(N \log N + M \log N + M \log M)