题解：CF2283F Minimize the Graph

· · 题解

题意

给定一张有向图，顶点编号为 1 \sim n， 对于每个 i=2 , 3 ,\cdots , n，给定区间 [l_i,r_i]，满足：

1\le l_i \le r_i<i

对于所有 j\in[l_i,r_i]，原图中都存在一条有向边 j\to i

现在要构造一张新的有向图，使得对于任意两个不同顶点 x,y

x\text{ 在原图中能到达 }y \iff x\text{ 在新图中能到达 }y

求新图最少需要多少条边。

解析

考虑原图中的一条边

x\to i \ , \ x \in [l_i,r_i]

这条边能被删除，当且仅当存在一条从 x 到 i 的长度至少为 2 的替代路径。

定义 mi_x=\min\{ t \ | \ t\ge 2 \ , \ x\in[l_t,r_t]\}，如果不存在这样的 t，令 mi_x=n+1。

也就是说，mi_x 是第一个覆盖到 x 的区间的编号，也是 x 可到达的最小的节点。

对于边 x\to i，设 t=mi_x \le r_i，显然有 x \in [l_i,r_i] 和 x \in [l_t,r_t]，由题意可知 t>r_t \ge x\ge l_i

即 t\in[l_i,r_i]，存在边 t\to i

原图中存在路径 x\to t\to i，因此边 x\to i 可以被这条路径替代，可以删除。

其中边 x\to t 一定不会被删除，因为 mi_x=t>r_t

所有被删除的边都能用保留下来的边形成替代路径，可达性仍然保持不变。

综上，若 mi_x \le r_i，则边可以删除

若边 x\to i 可以通过其他路径替代，那么存在一条从 x 到 i 的路径：

x=v_0\to v_1\to v_2\to\cdots\to v_k=i \ , \ k\ge 2

由于所有边都指向编号更大的点，所以：

x<v_1<v_2<\cdots<i

路径上 i 的前一个点 v_{k-1} 必须满足 v_{k-1}\in[l_i,r_i]，

有 v_1\le v_{k-1} \le r_i

因为存在边 x\to v_1，有：

mi_x\le v_1\le r_i

若边 x\to i 可以通过其他路径替代，则有 mi_x \le r_i。

综上，若边可以删除，则一定有 mi_x\le r_i

对于每个 i，原本有 r_i-l_i+1 条入边。

其中满足 x\in[l_i,r_i] 且 mi_x \le r_i 的边都可以删除。

所以最少边数为

\sum_{i=2}^{n}\left((r_i-l_i+1)-|\{x \ | \ x\in[l_i,r_i] \land mi_x\le r_i\}|\right)

问题转化为对每个 i，统计区间 [l_i,r_i] 中有多少个 x 满足 mi_x \le r_i

依次处理给定的区间 [l_i,r_i]。

对于区间中还没有被赋值的位置 x，当前的 i 就是第一个覆盖 x 的节点，之后这个位置就不需要再处理了。

使用并查集维护下一个还没有被赋值的位置，每个位置最多被赋值一次，复杂度为：

O(n\alpha(n))

对于每个 i，求

|\{x \ | \ x\in[l_i,r_i] \land mi_x\le r_i\}|

这是一个二维偏序问题，可以离线处理：

当我们按照 r_i 从小到大处理询问时，条件 mi_x \le r_i 中的 r_i 是单调不减的。

因此已经加入树状数组的位置以后也一定满足条件，不需要删除，只需要不断加入新的位置。

时间复杂度 O(n\log n)。

AC Code

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<vector>
using namespace std;
#define int long long
#define ri register int
#define rd(n) n=read()
const int N=300005; 
inline int read(void)
{
    ri res=0,f=0;
    register char c=getchar();
    while(c<'0'||c>'9'){f^=(c=='-');c=getchar();}
    while(c>='0'&&c<='9'){res=(res<<3)+(res<<1)+(c^48);c=getchar();}
    return f?-res:res;
}
inline void fprint(int n)
{
    if(n<0){putchar('-');n=-n;}
    if(n>9) fprint(n/10);
    putchar(n%10+'0');
}
inline void print(int n)
{
    fprint(n);
    putchar('\n');
}
int T,n,m,x,ans;
int l[N],r[N],mi[N],f[N],dat[N];
inline int find(int x)//DSU
{
    while(f[x]!=x)
    {
        f[x]=f[f[x]];
        x=f[x];
    }
    return x;
}
#define lowbit(x) ((x)&-(x))
inline void add(int x)//BIT
{
    for(;x<=n;x+=lowbit(x))
        ++dat[x];
}
inline int query(int x)
{
    ri ret=0;
    for(;x;x-=lowbit(x))
        ret+=dat[x];
    return ret;
} 
inline bool cmp1(int a,int b)
{
    if(mi[a]!=mi[b]) return mi[a]<mi[b];
    return a<b;
}
inline bool cmp2(int a,int b)
{
    if(r[a]!=r[b]) return r[a]<r[b];
    return a<b;
}
vector<int>pos,id; 
inline void Pre_work(void)
{
    for(ri i=0;i<=n+1;++i) 
    {
        f[i]=i;
        mi[i]=n+1;
        dat[i]=0;
    } 
    pos.clear();
    id.clear();
} 
inline void solve(void)
{
    rd(n);
    Pre_work();
    ans=0; 
    for(ri i=2;i<=n;++i)
    {
        rd(l[i]),rd(r[i]);
        x=find(l[i]);
        while(x<=r[i])
        {
            mi[x]=i;
            f[x]=find(x+1);
            x=find(x);
        }
    }
    pos.push_back(1);
    for(ri i=2;i<=n;++i) 
        pos.push_back((int)i),id.push_back((int)i);
    sort(pos.begin(),pos.end(),cmp1); 
    sort(id.begin(),id.end(),cmp2);
    ri p=0,mm=id.size(),nn=pos.size();
    for(ri i=0;i<mm;++i)
    {
        ri d=id[i]; 
        while(p<nn&&mi[pos[p]]<=r[d]) add(pos[p]),++p; 
        ans+=(r[d]-l[d]+1)-(query(r[d])-query(l[d]-1));
    } 
    print(ans);
}
signed main(void)
{
    rd(T);
    while(T--) solve();
    return 0;
}