noshi91

答えの頂点を掠めるような半平面が出力に入っているのは嬉しいのか嬉しくないのかという問題はある。凸包で辺上の点を含めるかと近い問題で、Convex Layers では含めていて Incremental Convex Hull では未定？

https://twitter.com/noimi_kyopro/status/1555482085397131264 > [のいみ](https://twitter.com/noimi_kyopro) [@noimi_kyopro](https://twitter.com/noimi_kyopro) まあでも正直本当の実用上だと 大きさ 2 × 10^9 の bounding box で囲んで困ることないしそれして有界の場合に限ってもいい気はするけどね 参考

参考 (permutation tree という語の使用を否定するものではありません) - [1] Uno, T., & Yagiura, M. (2000). Fast algorithms to enumerate all common intervals of two permutations. Algorithmica, 26(2), 290-309. - [2] Xuan, B. M....

追記 片方を id として一般性を失わないと書きましたが、その他方の順列のみに着目した場合、connected interval という語も使われているようです。([4] の 4 章) - [4] Belghiti, I., & Habib, M. (2013). A general method for common intervals. arXiv preprint arXiv:1309.7141.

[2] では、join は linear、cut は prime と呼ばれています。 [3], [4] では linear をさらに increasing と decreasing の 2 つに分類しています。

私の理解を書いておきます。 --- P を順列とする。connected interval とは、区間 [l, r] であって {P_i | l ≤ i ≤ r} もまた区間となるものである。connected interval のうち、他の connected interval と overlap (非交でも包含でもないこと) しないものを strong であると呼ぶことにする。strong な connected interval...

- 孤立点があるときに No になるかどうか

準備します

多重辺あり非連結あり自己ループ無しが良い気がしました。 https://github.com/yosupo06/library-checker-problems/blob/master/docs/style.md

燃やす埋めると最小カットが近すぎるのが原因だと思います。 燃やす埋めるの厳密な定義は多分存在しない？はずなので