「離散数学への招待（上）」を読んでいれば簡単
部分点１、２
わからない
部分点３
(a,b)⇄(c,d) when a<b&&c<dという半順序集合があって、これらを被覆するパスの本数 は最小でいくつか という問題。
これは、反鎖、つまり、左下⇄右上の関係が成り立たない部分集合の大きさの最大値を求めればよい。
その部分集合は右下⇄左上（境界を含む）の関係が成り立つので、LISっぽいもの（最長"広義"増加部分列）が求められればよい。
"広義"の処理が少しだけ面倒くさい。
各クエリでLISをやると、O(QNlogN)で部分点51点。
22分05秒
満点
LISがそもそも1からNまで順に構築して行くものだから、クエリと共に走査すればよいことはわかる。
また、LISはそもそも、その長さで最小となる値を持っているはずだから、一定の高さで切っても最適であることがわかる。
LISの単調増加が、二方向で抑えるクエリと揃った形である。
LISを構築していく1→Nの方向にクエリをソートして、二分探索で制限を超えない最長の長さを求めてやれば、計算量はO(NlogN)になる。
38分07秒
難易度10の中では最速で解けた
と思ったら本番で7人通してるし難易度10なさそう
