【CF-1285E】Delete a Segment（区间处理(并集)----思维）

题目

给定一些区间，一些区间之间可以组成一个大的区间（相当于将有交集的区间并起来）记为union。
问从这些给定的n个区间中删除一个区间，剩余n-1区间组成的union数的最大值。
样例：
input

output

2
1
5

解题思路

参考qsc学姐的b站视频，基本上搞懂了这道题。第一次做这种区间（线段）合并处理类的题，很不熟悉，加强练习！
最终的情况无非是下面几种：

其中比较麻烦的是对有交集的区间进行处理。
add[i]表示删除第i个区间后，增加的union数
ans1记录独立的区间数（比如上图的左右两个区间，除非删除自己这段区间，否则删除其他的区间对其对union的贡献数无影响）
对于上图中间这三种比较复杂的情况，在处理过程中可以归为三类：

第一类：

区间相交。
当前端点集为[ [，下一个遍历到的区间端点为] ，且此]可与前面的[配对，配对后只剩下一个[（记其所在的区间编号为x），并且再下一个端点是[。
这样当删除区间x时，对union的贡献都要增加1，即add[x]++
第二类

独立区间，区间编号x。
当前端点集为[，下一个端点为]，可配对，那么该区间可视为一个独立区间，ans1++
第三类

区间编号x。
当前端点集为空，下一个端点为[，且再下一个端点为]，后续可配对。若为此种情况，那么删除该区间，对union的贡献-1，即add[x]–
再往下处理就转成了第二类问题

对于第一张图中没有提到的下图情况，其实在处理过程中可以转化为第二类问题，~~（大概）是因为删除下面或者上面的区间，都可使剩余的区间成为一个独立区间，对答案的贡献是正确的（瞎说的）~~

此外就是代码巧用pair，具体实现参见代码。

ac代码

#include<bits/stdc++.h>
using namespace std;
const int maxn = 2e5+10;
typedef long long ll;
pair<int, int> a[maxn<<1];//<x坐标，+/-i> i输出编号，-i表示左端点
int add[maxn];//ans[i]表示删除第i个区间，新增的union数
int t, n, l, r, ans1, ans2;
int main()
{
    //freopen("/Users/zhangkanqi/Desktop/11.txt","r",stdin);
    scanf("%d", &t);
    while(t--)
    {
        ans1 = 0;
        scanf("%d", &n);
        for(int i = 1; i <= n; i++)
        {
            scanf("%d %d", &l, &r);
            a[2*i-1] = make_pair(l, -i);
            a[2*i] = make_pair(r, i);
            add[i] = 0;
        }
        sort(a+1, a+1+2*n);//所有端点从大到小排开
        multiset<int> s;//最左侧未匹配的左端点所在的区间编号
        for(int i = 1; i <= 2*n; i++)//处理每个端点
        {
            if(a[i].second<0) s.insert(-a[i].second);
            else s.erase(s.find(a[i].second));//可配对

            if(s.size()==0) ans1++;// [ ]
            if(s.size()==1 && a[i].second>0 && a[i+1].second<0 && a[i+1].first>a[i].first)//[ [ ] 配对完后下一个端点为[
                add[*s.begin()]++;
            if(s.size()==1 && a[i].second<0 && a[i+1].second>0)//当前[ 下一个端点为]
                add[*s.begin()]--;
        }
        ans2 = INT_MIN;
        for(int i = 1; i <= n; i++)//必须删除一个，不能先加ans1
            ans2 = max(ans2, add[i]);
        printf("%d\n", ans1+ans2);
    }
    return 0;
}