競技プログラミングにハマるプログラマのスレ 258 (311ﾚｽ)
上下前次1-新
260: 11/15(土)22:58 AAS
# D
初期状態の黒マス集合は 1 個の長方形 [0, X − 1] × [0, Y − 1] です。
各大嵐は、平面を直線 x = Ai（または y = Ai）で 2 つに分け、一方を上（または右）、他方を下（または左）へ平行移動させる全単射なので、黒マス集合は「互いに重ならない長方形の集合」として表現し続けられます。
1 回の大嵐で各長方形は高々 2 個に分割されるため、長方形の総数は高々 2^N（N ≤ 14）です。
最終的な長方形集合に対し、2 つの長方形がマスの辺を共有する（x 区間が重なり y 距離 1、または y 区間が重なり x 距離 1）ときに Union-Find で連結させます。
各連結成分の面積は、その成分に属する長方形の面積の総和として求まり、個数と面積を昇順に出力すればよいです。
# E
数列の順番は関係なく，値の多重集合だけを見ればよいことに気付きます。
l ≤ r のとき，max(l, min(r, a)) は a<l なら l，l≤a≤r なら a，a>r なら r なので，
答えは「a<l の個数×l」＋「l≤a≤r の総和」＋「a>r の個数×r」で計算できます。
0〜5×10^5 の値ごとに個数と総和を Fenwick 木 2 本で管理し，prefix 和から上式を求めます。
l>r のときは max(l, min(r, a))≡l となるため，答えは常に N×l です。
更新クエリは古い値を 1 個減らし新しい値を 1 個増やすだけなので，各操作は O(log M)，全体計算量は O((N+Q)logM) となります。
# F
うんち
# G
二重和を b ごとにまとめ、H[b] = ?_a c_A[a]·C(a, b) を全 b について求める。
C(a, b) = a!/(b!(a-b)!) より、H[b] = inv(b!)·?_{t≥0} (c_A[b+t]·(b+t)!)·inv(t!)。
A’[a] = c_A[a]·a!、F[t] = inv(t!) とおくと、右辺は A’ と F の反転畳み込みで一括計算できる。
A’ を反転して NTT 畳み込み conv を求め、H[b] = inv(b!)·conv[V-b]（V=max(A_i, B_j)）。
最終答えは S = ?_b c_B[b]·H[b]。
前計算 O(V)、畳み込み O(V log V)、合計 O(V log V)。
998244353 は NTT 可能な素数なので安全に実装できる。
上下前次1-新書関写板覧索設栞歴
あと 51 ﾚｽあります
ｽﾚ情報 赤ﾚｽ抽出 画像ﾚｽ抽出 歴の未読ｽﾚ AAｻﾑﾈｲﾙ
ぬこの手 ぬこTOP 0.003s