問題ページ これは を最小化するように空港を設置する問題である.もし と が同じ木の頂点であれば,どのように空港を配置しても2点間の距離は変化しない.木の2点間の距離はLCAなどを用いることによって で求めることができる. ここからは と が違う木に属…
問題ページ が の中央値のとき は最小になる.Wavelet Matrixを用いると数列のある連続する区間のk番目の数を求めることができるので,各クエリに対して中央値を求めることができる. 未満の要素の個数 未満の要素の和 以上の要素の和 以上の要素の個数 が答…
引用をストックしました
引用するにはまずログインしてください
引用をストックできませんでした。再度お試しください
限定公開記事のため引用できません。