問題 D - Decayed Bridges 解法 ぱっと見でUnionFindだろうなと思ったが、少々工夫が必要だった。 橋の削除操作は難しいため、逆順から橋を追加していく操作を考える 橋が一つもない状態の不便さは $ {}_n C_2 $ で求まる 橋を追加後の不便さは、次で求まる …

問題 D - AtCoder Express 2 解法 列車の区間L-Rを二次元座標として考える。 Q個のクエリを求める必要があるが、都度計算すると間に合わない。 二次元累積和を使って前計算しておくことで、Q個のクエリに対して高速に答えを出す。 #include <bits/stdc++.h> using namespace</bits/stdc++.h>…