maspypy
maspypy
準備しようとしているものとは別問題になるかもしれないけど、f(x)/g(x)(1-x)^n の形の有理式の部分分数分解はたまに問われるイメージがあって、この形の場合の速い部分分数分解ライブラリも需要があるかもしれない。（解法も何も考えていないが） https://github.com/yosupo06/library-checker-problems/issues/99 https://atcoder.jp/contests/s8pc-3/tasks/s8pc_3_g
functional graph という言葉を問題名に入れるとわかりやすそう？X はクエリにしてもよいかと。
ああ線形時間でやりたいってことですか。把握。
・https://judge.yosupo.jp/problem/convex_layers では座標が $10^6$ だが、特に理由がなければ $10^9$ でよいかなと思う。 ・$N=0$ で $Q$ だけにしても良いかも。 ・出力させるものが何か良いのかは分からない。「点追加せよ / 頂点の個数と面積を出力せよ」くらいの方が良いかも。 ・Incremental な凸包と Incremental な CHT（Line Add Get Min）は実質一緒という説もある。
問題案をもうすこし具体的にしました。私が作業予定です。
要望があるならついでに通常の凸包も作業してもよいです。 - 頂点を反時計回りに出力 - 最小頂点数（辺上に無駄な頂点が並ぶやつは消す） くらいですか。
揉めポイント：辺上の点も頂点数に含めるか否か。 https://judge.yosupo.jp/problem/convex_layers では、凸包として「辺上の点」も含めている。（人々のライブラリではどちらが一般的だろうか）
問題案を少しいじりました。 内外判定くらいできた方が良いと思ったので足しました。
point set と range affine で セグ木 / 遅延セグ木 の 2 種あるとよいのでは。 （メモリ定数倍が大きいことが多いので、作用素の有無でライブラリを分けたい） ただし ・N が小さい版でもこれを verify できる（が、同解法の中での速度比較はしにくい） ・最速実装はクエリ先読み座圧になってしまいそう（ので、同解法の中での速度比較はしにくい） とかはありますね。