自动搬运

查看原文

来自洛谷，原作者为

	文文殿下 这家伙很勤奋，但还是什么都没有留下～～

搬运于2025-08-24 22:02:37，当前版本为作者最后更新于2019-07-01 19:03:45，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

一个结论：“从出发点开始走绝对不会出现死循环”。
考虑如何证明这个结论（这会直接提示正解）：
我们对数轴分段，对于任意一个传送门，把当前段分成两段。
对于每一段（除了第一段）我们总会有一个到达这个段的方法：走一个传送门。这个传送门的位置是这个段左边第一个传送门，我们查看这个传送门通向哪里，然后把那个点与这个点连一条有向边。
对于每一段（除了最后一段）我们总会有一个离开这个段的方法，和上面类似建图。
我们考虑，我们在行走过程中，由于第一个段没有入度，所以我们绝对不会回到第一个段。
由于最后一个段没有出度，所以我们绝对不会向其他地方循环。
由于除了开头和结尾的特殊段，其他任何段有且仅有一个入度和出度，所以我们一定会从一号段到达最后一个段离开。
证毕。
我们发现，除了从一号点到最后一个点是一条简单路径，其他的点一定在一个环里（可以画图理解）。
考虑我们新加一个传送门，会导致这张有向图如何变化？
我们有三种加的方式：

• 一：用一对传送门把两个不在同一个连通块的点链接。
  这会直接导致有两个点一分为二，然后他们所在的连通块合并。
  如果我们合并路径和环，我们会得到一个更长的路径。
  如果我们合并环和环，我们会得到一个更大的环。
• 二：用一对传送门链接同一个连通块里两个点。
  这会直接导致这个连通块一分为二。这对答案没有任何帮助。
• 三：这对传送门放在某对传送门的内部，这会导致我们永远无法访问到这个传送门，所以他单独成一个点。

题解显而易见，我们把所有环从大到小排序。
然后从大到小，用传送门把他们用方法一连到我们的路径里。 如果连完以后，传送门还有剩余，我们可以不断做方法三和方法一，把他们累加到答案里。
细节：如果只剩一个传送门，我们就把他加在末尾。
时间复杂度$O(nlogn)$
进一步优化：
我们发现复杂度瓶颈在于排序，但是由于排序的值非常小，我们使用桶排序。
时间复杂度到达理论下届：$O(n)$
但是我懒得写线性的，下面给出$O(nlogn)$的代码，吸氧能过。

#include<bits/stdc++.h>
using namespace std;
const int maxn = 2e6+10;
struct qwq {
    int inc,out;
}s[maxn];
struct QQQ {
    int l,r;
}L[maxn];
struct QAQ {
    int v,bl,type;
    const bool operator < (const QAQ& rhs) const {
        return v<rhs.v;
    }
}v[maxn];
int n,m,cnt,ind[maxn];
int sz[maxn],ans,tot;
bool vis[maxn];
int find(int x) {
    return lower_bound(v+1,v+1+cnt,(QAQ){x,0,0})-v;
}
void dfs(int cur,int pos) {
    while(!vis[cur]) {
        vis[cur]=1;
        sz[pos]++;
        int nxt;
        if(v[cur].type) nxt = find(L[v[cur].bl].l+1);
        else nxt=find(L[v[cur].bl].r+1);
        cur = nxt;
    }
}
int main() {
    scanf("%d%d",&n,&m);
    for(int i=1;i<=n;++i) {
        scanf("%d%d",&L[i].l,&L[i].r);
        v[++cnt].v=L[i].l;
        v[cnt].bl=i;
        v[cnt].type=0;
        v[++cnt].v=L[i].r;
        v[cnt].bl=i;
        v[cnt].type=1;
    }
    sort(v+1,v+1+cnt);
    int cur = 1;
    while(cur!=cnt+1) {
        vis[cur]=1;
        ++ans;
        int nxt;
        if(v[cur].type) nxt = find(L[v[cur].bl].l+1);
        else nxt=find(L[v[cur].bl].r+1);
        cur = nxt;
    }
    vis[cur]=1;
    for(int i=1;i<=cnt;++i) {
        if(!vis[i]) {
            dfs(i,++tot);
        }
    }
#ifdef DEBUG
    printf("%d\n",ans);
    printf("%d\n",tot);
    for(int i=1;i<=tot;++i) printf("%d ",sz[i]);
#endif
    sort(sz+1,sz+1+tot,greater<int>());
    for(int i=1;i<=tot&&m;++i) {
        ans+=2;
        --m;
        ans+=sz[i];
    }
    if(m) {
        if(m&1) --m,++ans;
        ans+= 2*m;
    }
    printf("%d\n",ans);
    return 0;
}