传送门

题目

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

3
4
1 4
2 3
3 6
5 7
3
5 5
5 5
5 5
6
3 3
1 1
5 5
1 5
2 2
4 4

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;
}