AT2645 [ARC076D] Exhausted?

對于一個二分圖左邊點連接的是右邊點的一個前綴和一個后綴，求解最大匹配。

首先不能直接求解最大匹配，但是我們可以利用Hall定理的推論求解
$$|U|?max(|X|?N(|X|))$$

現在需要讓$|S|?(m?{?}_{i\in S}[l_i,r_i])$最大，也就是讓$|S|+{?}_{i\in S}[l_i,r_i]?m$最大，然后如果沒有交集的情況答案就是n-m, 否則我們考慮枚舉這個交集，對于一個區間答案最大就是區間長度加上覆蓋這段區間的區間個數，那么我們考慮掃描線+線段樹維護。

使用這個方法主要有兩個限制，一個是要求各個區間對各個下標的貢獻獨立，一個是要求方便移動答案信息。

總結

以上是生活随笔為你收集整理的AT2645 [ARC076D] Exhausted?（Hall定理推论/线段树+扫描线）的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。