CF1285E

这题qwq失智qwq
给出 $n$ 个区间，定义‘段数’为在相交区间间连边之后图的联通块个数。求出删去恰好一个区间之后段数的最大值。（以下不区分线段和区间。。）

我看到题之后的思路是注意到只删去一个，删去个区间之后是一段前缀和一段后缀。就把区间按端点排下序，再求每个前缀和后缀的答案，再枚举断点合并。结果发现前缀好求，后缀不好求qwq所以自闭了。

这题有两种做法：
一种是暴力数据结构。我们记录每个点被几条线段覆盖，删去线段就相当于区间减，然后线段树维护答案，每个节点记录区间内有几段，左边是否相连，右边是否相连即可合并。发现区间减无法快速得到答案。利用题目的性质，区间减完立马会加回来。所以每个区间只有两种状态（减过1或没减），分别维护一下即可。
这个做法是我看到题解说要数据结构，但是没看懂。。然后自己yy的。不过细节不会，还是扑街qwq
考虑【1，2】，【3，4】这两个区间，它们应该算成两段，但在线段树上体现不出。因为只记录了每个节点被覆盖几次，无法区分【1，2】，【3，4】和【1，4】。这个把我又恶心了，我都放弃这个做法了qwq。后来才知道可以离散化之后坐标乘2即可解决。

#include<bits/stdc++.h>
using namespace std;
const int N=8e5+50;
int T,n,c[N],m,b[N],ans;
struct node1{int l,r;}a[N];
int read(){
    int x=0,c,f=1;
    while(!isdigit(c=getchar()))c=='-'?f=-1:0;
    while(isdigit(c))x=x*10+c-48,c=getchar();
    return x*f;
}
struct node{
    int num;bool ll,rr;
    node operator +(const node &b){return (node){num+b.num-(rr&b.ll),ll,b.rr};}
}t[N*4],it[N*4];
int get(int x){return lower_bound(c+1,c+m+1,x)-c;}
void build(int x,int l,int r){
    if(l==r){
        t[x]=b[l]?(node){1,1,1}:(node){0,0,0};
        it[x]=b[l]-1?(node){1,1,1}:(node){0,0,0};
        return;
    }
    int mid=(l+r)>>1;
    build(x<<1,l,mid);build(x<<1|1,mid+1,r);
    t[x]=t[x<<1]+t[x<<1|1];it[x]=it[x<<1]+it[x<<1|1];
}
void change(int x,int l,int r,int ql,int qr){
    if(l>=ql&&r<=qr){swap(t[x],it[x]);return;}
    int mid=(l+r)>>1;
    if(ql<=mid)change(x<<1,l,mid,ql,qr);
    if(qr>mid)change(x<<1|1,mid+1,r,ql,qr);
    t[x]=t[x<<1]+t[x<<1|1];
}
void solve(){
    n=read();ans=0;
    for(int i=1;i<=n;i++)a[i].l=c[i]=read(),a[i].r=c[i+n]=read();
    sort(c+1,c+n*2+1);m=unique(c+1,c+n*2+1)-c-1;
    for(int i=1;i<=m*2;i++)b[i]=0;
    for(int i=1;i<=n;i++){
        a[i].l=get(a[i].l)*2,a[i].r=get(a[i].r)*2;
        b[a[i].l]++;b[a[i].r+1]--;
    }
    m*=2;
    for(int i=1;i<=m;i++)b[i]+=b[i-1];
    build(1,1,m);
    for(int i=1;i<=n;i++){
        change(1,1,m,a[i].l,a[i].r);
        ans=max(ans,t[1].num);
        change(1,1,m,a[i].l,a[i].r);
    }
    printf("%d\n",ans);
}
int main(){
    T=read();
    while(T--)solve();
    return 0;
}

第二种做法是这样的：
我们考虑平常求这个段数怎么求？
把所有区间按左端点排序，一个个扫，并记录扫过的中右端点的最大值，如果断掉了就ans++。
这个东西用式子写出来

\sum_{i=1}^n[l_i>mx_{i-1}]

其中 $mx$ 是右端点的前缀max。
线段 $i$ 的贡献即为 $[l_i>mx_{i-1}]$ 。考虑删掉一条线段，则先减去自己的贡献，再加上它使别人多出的贡献。什么意思？一条线段 $i$ 删去之后线段 $j$ 的贡献会从0变到1当且仅当 $mx_{j-1}=r_i\&\&l_j<=mx_{j-1}\&\&l_j>mx2_{j-1}$ ，其中 $mx2$ 是前缀次大值。很好理解吧。于是发现线段 $j$ 能造成贡献的 $i$ 是唯一的（即达到最大值的那条线段），那么我们只要从前往后扫一遍，维护最大和次大，顺便看一下能否造成贡献即可。

#include<bits/stdc++.h>
using namespace std;
const int N=2e5+50;
int t,n,b[N],ans,dat;
struct node{int l,r;bool friend operator <(node a,node b){return a.l<b.l;}}a[N];
void solve(){
    scanf("%d",&n);ans=0;dat=-1;
    for(int i=1;i<=n;i++)scanf("%d%d",&a[i].l,&a[i].r);
    sort(a+1,a+n+1);
    for(int i=1,mx=-1,mx2=-1;i<=n;i++){
        if(mx==-1||a[mx].r<a[i].l)ans++,b[i]=-1;
        else{
            b[i]=0;
            if(mx2==-1||a[mx2].r<a[i].l)b[mx]++;
        }
        int x=i;
        if(mx==-1||a[mx].r<a[x].r)swap(x,mx);
        if(x!=-1&&(mx2==-1||a[mx2].r<a[x].r))mx2=x;
    }
    for(int i=1;i<=n;i++)dat=max(dat,b[i]);
    printf("%d\n",ans+dat);
}
int main(){
    scanf("%d",&t);
    while(t--)solve();
    return 0;
}

Prutekoi's blog

好题