P4175 [CTSC2008]ネットワーク管理 解説
問題概要
ノード数が $ n $ の木が与えられ、各ノードには重み $ w_i $ が割り当てられている。$ q $ 個の操作を行う：
0 u v：ノード $ u $ の重みを $ v $ に変更する。
k u v：ノード $ u $ から $ v $ へのパス上の重みの第 $ k $ 番目の大きい値を求める。パス上にノードが $ k $ 個未満ある場合、invalid request! を出力する。
制約
$ 1 \le n, q \le 8 \cdot 10 ...
8月20日 16:41 投稿
CDQ分治と全体二分法の実装と応用
CDQ分治
CDQ分治は、マージソートを応用した分割統治アルゴリズムであり、特に多次元の順序制約（偏序）問題に有効である。基本的な流れは以下の通り：
左半分と右半分をそれぞれ再帰的に処理。
左右をマージしながら、左側の要素が右側の要素に与える影響を計算。
3次元偏序問題
各点が3つの属性 (a, b, c) を持つとき、ある点よりすべての属性が小さい点の数を求 ...
8月12日 01:58 投稿