series-parallel graph - Githubissues

beet-aizu / library

Competitive Programming Library

https://beet-aizu.github.io/library/

128 stars 23 forks source link

Open beet-aizu opened 3 years ago

beet-aizu commented 3 years ago

論文にデータ構造があるらしい？　要チェック

beet-aizu commented 3 years ago

beet-aizu commented 3 years ago

beet-aizu commented 3 years ago

beet-aizu commented 3 years ago

なんかライブラリ化するならもうちょい用件強くしないとキツそう

beet-aizu commented 3 years ago

畳み込み側の操作を限定すれば slope trick に限定できそう例：

0 以上捨てる（一つあたりのコスト0）→R.clear()
abs(x)→ while(L.size()>1) L.erase(L.begin()); while(R.size()>1) R.erase(--R.end());

beet-aizu commented 3 years ago

スライド最小値関数を使えばマージテクでそれなりの計算量にはなりそうな気もしてきた

beet-aizu commented 3 years ago

https://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=0661 うーーーーーーーん　まとめてたくさん突っ込むようにしてしまうか　定数倍はそこまで悪化しないし