題解：CF1889C1-Doremy’s Drying Plan (Easy Version)

一、 題意描述

1. 題目鏈接

（1） CF鏈接

CodeForces

（2） 洛谷鏈接

洛谷

2. 題目翻譯

有一個長度為 $n$ 的序列，上面有 $n$ 個點，編號為 $1$ 到 $n$。現在給定 $m$ 個區間，第 $i$ 個區間覆蓋了序列中的 $l_i$ 到 $r_i$ 之間（包含兩端）的所有點。你可以刪除其中的 $2$ 個線段，使得序列中未被任何線段覆蓋的點數最大。
$1\le n\le 2?10^5$, $2\le m\le 2?10^5$, $k=2$。
$\sum n+m\le 2?10^5$

二、 思路分析

觀察數據范圍，$n$ 和 $m$ 都是 $10^5$ 級別，所以考慮 $O(n+m)$ 左右的算法，當然帶上幾個小 $log$ 也沒問題。
對于序列中所有的點，我們可以對它們進行分類：
①被 $0$ 個區間覆蓋；
②被 $1$ 個區間覆蓋；
③被 $2$ 個區間覆蓋；
④被 $3$ 個或者更多個區間覆蓋。
想要求出某個點是哪一類，我們可以在讀入線段時記錄差分。
顯然，對于①類點，無論選擇哪兩條，它們都是“未被任何線段覆蓋的點”，所以直接計入總數。
對于④類點，無論怎么選都無法讓它們變成“未被任何線段覆蓋的點”，所以它們被我們拋棄了。
如果只能刪除一個線段，那么對最終答案所能產生的貢獻自然是這個線段內②類點的數量，為了迅速求出它，我們需要維護一個前綴和，存儲在某個點之前有多少個②類點。
顯然，我們可以把每個線段按照這種貢獻從大到小排序，選取最大的兩個，把它們的貢獻相加計入總數。
問題：這樣求出的貢獻一定是最大的嗎？
顯然不是！我們只能把貢獻計入一個存儲最終貢獻的最大值的變量。如果兩個線段有重疊，那么最終的貢獻還要加上中間重疊部分的③類點總數（這個我們也用前綴和維護），但是如果繼續用剛才的方法進行排序取出的最大兩個有可能不是最優的。
于是我們考慮，被兩個線段覆蓋的點有哪些？我們可以遍歷一遍每個節點，通過前綴和求出它被多少區間覆蓋。但問題又來了，到底是哪兩個區間呢？我們可以把線段的左端點和右端點加一分別扔進兩個序列（記錄一下差分維護的過程），按照端點下標排序，并記錄到底是哪個線段，在遍歷節點之前，用一個集合來維護那些線段覆蓋到遍歷到的點，最后遍歷到每個點 $i$，左端點的序列里端點下標為 $i$ 的元素先把對應的線段編號扔進這個集合，再把它從序列中刪除，右端點加一的序列同理，只不過是把里面的線段編號從集合里刪除。最后如果集合里是兩條線段，就計算這兩條線段的貢獻，和之前的貢獻取最大值。最后把貢獻最大值累加到①類點數量才是答案。
具體實現還要看代碼。

三、 時間代價

算法主體遍歷線段、節點是 $O(n?m)$ 的，但是維護一大堆集合和序列用到 $set$，需要乘上一個 $O(log(m))$，所以總共時間復雜度可以估計成 $O((n+m)?log(m))$

四、代碼實現

#include<bits/stdc++.h>
#define N 220000
using namespace std;
multiset<pair<int,int>>in={},out={};
multiset<int>inc1={};
set<int>xd={};
int c[N]={},c1[N]={},c2[N]={},l[N]={},r[N]={},s[N]={},s1[N]={},s2[N]={},ans=0,inc=0,k=0,m=0,n=0,t=0;
int main(){scanf("%d",&t);while(t--){scanf("%d%d%d",&n,&m,&k);for(int i=1;i<=n+1;i++){c[i]=0;c1[i]=0;c2[i]=0;}in.clear();out.clear();for(int i=1;i<=m;i++){scanf("%d%d",&l[i],&r[i]);c[l[i]]++;c[r[i]+1]--;in.insert({l[i],i});out.insert({r[i]+1,i});}ans=0;for(int i=1;i<=n;i++){s[i]=s[i-1]+c[i];if(s[i]==0){ans++;}else{if(s[i]==1){c1[i]++;}else{if(s[i]==2){c2[i]++;}}}s1[i]=s1[i-1]+c1[i];s2[i]=s2[i-1]+c2[i];}inc1.clear();for(int i=1;i<=m;i++){inc1.insert(-(s1[r[i]]-s1[l[i]-1]));}inc=0;int x=*inc1.begin();inc1.erase(inc1.begin());int y=*inc1.begin();inc=max(inc,-(x+y));xd.clear();for(int i=1;i<=n;i++){while(out.empty()==false&&out.begin()->first==i){xd.erase(out.begin()->second);out.erase(out.begin());}while(in.empty()==false&&in.begin()->first==i){xd.insert(in.begin()->second);in.erase(in.begin());}if(xd.size()==2){auto now=xd.begin();int a=*now;now++;int b=*now;int ret=(s1[r[a]]-s1[l[a]-1])+(s1[r[b]]-s1[l[b]-1])+(s2[min(r[a],r[b])]-s2[max(l[a],l[b])-1]);inc=max(inc,ret);}}printf("%d\n",ans+inc);}return 0;
}