srupのメモ帳

競プロで解いた問題や勉強したことを記録していくメモ帳

SparseTable

Codeforces #361 (Div.2) D. Friends and Subsequences

問題 問題概要 [l, r]の区間を考えた時に, al, .. , ar の最大値と bl, .. , br の最小値が一致する区間の総数を求める. 解法 区間の左端を固定して, 右端を伸ばしていくと, aの最大値は単調増加, bの最小値は単調減少していくので, 区間を伸ばしていくとど…

ARC 045 B - ドキドキデート大作戦高橋君

問題 問題概要 N人の人がM個の教室を掃除する. 一人が掃除する連続区間の教室が与えられる. ひとつの教室につき一人以上が掃除をしていればいい. どの区間を掃除する人はさぼることができるか. さぼる人は 同時に1人として考える. 解法 まずimos法を利用して…