Codeforces Round #613 (Div. 2) E. Delete a Segment（构造，思维）

链接：Codeforces Round #613 (Div. 2) E. Delete a Segment

题意：

给出$n$（$2\le n\le 2?10^5$）条$x$坐标轴上的线段$[l_i,r_i]$（$?10^9\le l_i\le r_i\le 10^9$），可删除任意$1$条线段，问删除后的联合段数量最多是多少？

分析：

这题解是真的难懂…

通过记录联合段的左边界数量代替联合段数量，先求出原有数量cur，并将这些联合段的左边界暂存到Lb中；

将所有线段边界以三元组形式(p,id,flag)存储，p为边界位置，id为边界所属的线段编号，flag==-1表示左边界，flag==1表示右边界，并从小到大排序；

从左到右遍历所有线段边界（线扫描）,定义：

• 当前只遇到其左边界而未遇到其右边界的线段为开放线段
• 已经遇到其右边界的线段为闭合线段

如下图中蓝色为当前扫描线，黑色为闭合线段，红色为开放线段；

open集合存储当前的开放线段，op集合存储当次扫描待加入开放线段，cl集合存储当次扫描待加入的闭合线段，ans[x]记录删除线段x后增加的联合段左边界数量；

可以发现当且仅当open集合中只有$1$条开放线段（记为x）,且op集合不为空时，删除x 会 使得联合段的左边界数量+1（即ans[x]++），因为op集合中的 待加入开放线段左边界 会成为 新的联合段左边界；

如下图open={2}，op={3,4}，cl={2}，删除线段2后，会产生新的联合段左边界；

可以发现若open中有多条线段，则仅删除$1$条无任何效果，若op集合为空，也同样无法产生新的联合段左边界。

最后，考虑一种特殊情况，若x原本就是原有联合段左边界（且是唯一的），则删除后会增加的联合段左边界数量会多算$1$，既要令ans[x]-1，如下图所示，计算得到的ans[x]=3，但实际上删除x后的增加的联合段左边界数量应为ans[x]=2。

可以发现，若x不是原有联合段左边界，或者不是唯一的联合段左边界，则不会出现上述情况。

最后max{ans}+cur即为最终答案。

以下代码：

#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
typedef pair<int,int> PII;
const int INF=0x3f3f3f3f;
const int maxn=2e5+7;
int n,m;
struct segment
{
    int L,R;
}a[maxn];
bool cmp1(const segment &x,const segment &y)
{
    return x.L<y.L;
}
struct border
{
    int p,id,flag;
}b[2*maxn];
bool cmp2(const border &x,const border &y)
{
    return x.p<y.p;
}
map<int,int> Lb;
int init()
{
    int cnt=0;Lb.clear();int L,R=-INF;for(int i=1;i<=n;i++){
    if(a[i].L>R){
    if(R!=-INF)Lb[L]=0;cnt++;L=a[i].L,R=a[i].R;}elseR=max(R,a[i].R);}Lb[L]=0;return cnt;
}
int ans[maxn];
void process()
{
    set<int> open;for(int i=1;i<=m;i++){
    vector<int> op,cl;int j=i;do{
    if(b[j].flag==-1)op.push_back(b[j].id);elsecl.push_back(b[j].id);j++;}while(j<=m&&b[j].p==b[i].p);if(open.size()==1&&!op.empty())ans[*open.begin()]++;for(auto it:op)open.insert(it);for(auto it:cl)open.erase(it);i=j-1;}
}
int main()
{
    int T;scanf("%d",&T);while(T--){
    scanf("%d",&n);for(int i=1;i<=n;i++)scanf("%d %d",&a[i].L,&a[i].R);sort(a+1,a+n+1,cmp1);int cur=init();m=0;for(int i=1;i<=n;i++){
    b[++m]=border{
    a[i].L,i,-1};b[++m]=border{
    a[i].R,i,1};}sort(b+1,b+m+1,cmp2);memset(ans,0,(n+1)*sizeof(int));process();for(int i=1;i<=n;i++){
    if(Lb.count(a[i].L))Lb[a[i].L]++;}for(int i=1;i<=n;i++){
    if(Lb[a[i].L]==1)ans[i]--;}printf("%d\n",*max_element(ans+1,ans+n+1)+cur);}return 0;
}