【CF】Day43——Codeforces Round 906 (Div. 2) E1
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;
}