cplib-cpp
cplib-cpp copied to clipboard
Published
20 hours ago •
hitonanode
hitonanode
PQ-tree
https://codeforces.com/blog/entry/93018?#comment-820809 https://codeforces.com/contest/243/problem/E
https://gregable.com/2008/11/pq-tree-algorithm.html によると，頑張れば（頂点数＋各クエリの頂点数の和）に対して線形にできる（らしい）
- P-node の子の情報は常にちゃんと持つ
- Q-node は両端の子の情報を持てばよい
- Q-node のそれぞれの子について両隣の子の情報を持たせる？