数直線上に区間$[l,r]$が複数ある場合、数直線上の点をいくつか選んだときに合計でいくつの区間に触れているかを数える。区間の数と選ぶ点の数はともに$10^5$程度までいける。
単純にimos法などを使えば数えられるんじゃないかと一瞬思うが、それだと2つ以上の点が同じ区間に含まれているときにダブルカウントが起こるので、一度数えた区間はもう数えないように工夫が必要。それぞれの区間は連続なので、点を座標についてソートして前から見たときに「点$i$は含まれているが点$i-1$は含まれていない区間」のみを数えていけばよい。点$i$の座標を$x_i$と書くことにすれば、そのような区間の条件は $$x_{i-1}\lt l\leq x_i ,\; x_i\leq r$$ となっていることである。ここで、一次元数直線上の区間$[l,r]$を二次元平面上の点$(l,r)$に対応させると、二次元累積和によってそのような区間の数を数えることができる。
これは画像に赤で示された領域に対応していて、この部分に入っている点の数を数えればよい。これをすべての点について行う。数え方としては単純な二次元累積和やtech001などが考えられる。