長さ n の配列で範囲のセットが与えられた場合、 setS={ (x1,y1) , (x2,y2) ,......(xk,yk) }
からクエリが与えられQ={ (l1,r1) , ......(li,yi) }
ます。各クエリ (li,ri) は、この範囲 (li,ri) の間にセット S からの範囲がいくつあるかを意味します。
次のことが可能かどうかを知りたいだけです。
1. Pre-computation in O(n) and then queries in O(1)
2 Pre-computation in O(nlogn) and then queries in O(logn)
PS:上記の 2 点だけで解決するのではなく、自分で解決策を考えたいと思います。