E1. Doremy's Drying Plan (Easy Version)

題目：

思路：

very好題，加深對掃描線的應用，值得深思

由于k = 2，那我們就可以使用簡單一點的方法來寫

題目可以轉化為：給定n個線段，現在讓你刪去2條線段，使得沒有與線段相交的點數最多

那么首先明確一點，就是只有下雨在 0 ~ 2 的城市才可能造成奉獻，否則是不可能造成奉獻的，因為這個城市起碼與三個線段相交，我們只刪兩個是沒用的

那么對于這種區間變化的題目，我們首先想到的就是差分數組+掃描線

題目的答案肯定是： 本來就是 0 的城市 + 刪去 2 條線段后的新的為 0 城市

前部分好算，但是后部分就考我們的代碼能力了

對于題目我們觀察到 n 的數據只有 2e5，所以枚舉一遍肯定是沒問題的，我們可以枚舉每個城市的下雨天，如果這個城市只有 day1 這天下雨，那么就代表如果刪去 day1 可以直接增加這個城市的奉獻，如果這個城市在 day1 day2 的交集處，那我們可以令?{day1，day2} 的奉獻增加 1，因為同時刪去 day1 day2 就會使得這個城市干枯，那么對于 三天以上的 我們就可以忽略不計了

具體的，我們利用差分的思想，在每個下雨的左端點和右端點加上奉獻，但是由于我們要知道具體是第幾天下的雨，所以這里的奉獻不是 1/-1 而是 i/-i?

接下來我們和掃描線一樣的操作，這里由于我們要知道具體的天數，所以我們要使用一個set，而不是int 來存儲，我們利用 set 從第一個城市開始掃描，如果這個城市是某個雨天的起點，那么就將這個雨天加入set中，同時如果是終點，那么就刪去，然后這個城市掃描完后開始判斷

判斷過程如上面所示，如果set中只有1個元素，那么就說明這個城市只在 day1 這天下過雨，也就是說這個城市之下過一次雨，那么刪去 day1 就會有這個城市的奉獻，所以我們用一個cnt數組來儲存第 i 次雨天中只有一次下過雨的城市（即此次）的數量

如果set是空的，說明根本沒下過雨，直接加到最后的答案中即可

如過set是3個及其以上，那么直接跳過即可，因為不可能有奉獻

如果set是2個，那么我們就將 {day1，day2} 這個組合的奉獻加 1，具體的我們可以使用一個map，其代表同時處于 {day1，day2} 這個交集中的城市數量，如果我們刪除 day1 day2 那么就會增加這么多奉獻了

最后就是枚舉刪除方法了，我們有兩種刪除方法，一種是刪除兩個不相交的區間，一個是刪除相交的區間，所以要對這兩種刪法取最大值

第一種刪法顯然是刪除 cnt 中最大的兩個元素即可，因為 cnt 中都是只有一次的城市數，即只與一個線段相交的城市，這里不需要考慮 day1 day2 的情況，因為這些都是只有一次的，不可能相交

第二種刪法就是枚舉 map 中的組合，由于刪除了 day1 day2，所以還需要加上只有一次的情況，即還需要加上 cnt[day1] 和 cnt[day2]

至此完畢，具體實現看代碼

代碼：

#include <iostream>
#include <algorithm>
#include<cstring>
#include<cctype>
#include<string>
#include <set>
#include <vector>
#include <cmath>
#include <queue>
#include <unordered_set>
#include <map>
#include <unordered_map>
#include <stack>
#include <memory>
using namespace std;
#define int long long
#define yes cout << "YES\n"
#define no cout << "NO\n"
typedef pair<int, int> PII;
void solve()
{int n, m, k;cin >> n >> m >> k;//第 i 個位置有幾天是下著雨vector<vector<int>> q(n+m);vector<int> cnt(n + m,0);for (int i = 1; i <= m; i++){int l, r;cin >> l >> r;q[l].push_back(i);q[r + 1].push_back(-i);}set<int>p;int ans = 0, res = 0;map<PII, int> v;for (int i = 1; i <= n; i++){//枚舉第 i 個位置是否會開始下雨，以及停雨，如果開始下雨那么就會一直持續到停雨為止（掃描線）for (auto x : q[i]){if (x > 0)p.insert(x);elsep.erase(-x);}//這個位置內之前和現在都沒下雨，則必定干枯if (p.empty())ans++;//如果當前點之前只有一天下過雨，說明這天的奉獻可以加一，也就是只下過一次雨，到時候刪除這一天就能把這些 1 全加進奉獻else if (p.size() == 1)cnt[*p.begin()]++;//下雨天的 [day1,day2] 的相交處有城市，即當前的 i 點，但是不需要知道具體是那個點，所以 +1 即可else if (p.size() == 2)v[{*p.begin(), * p.rbegin()}]++;//三天及以上的都無法改變}//考慮刪除 [day1 day2] 這個線段的奉獻，一次刪兩個，那么除了相交的城市，還要加上這兩天中只下過一次雨的城市for (auto& x : v)res = max(res, x.second + cnt[x.first.first] + cnt[x.first.second]);//得到最大的兩個只有一天下雨的雨天sort(cnt.begin() + 1, cnt.begin() + 1 + m, greater<int>());//刪除最多的兩個res = max(res, cnt[1] + cnt[2]);cout << ans + res << endl;
}signed main()
{cin.tie(0)->sync_with_stdio(false);int t = 1;cin >> t;while (t--){solve();}return 0;
}