题解：CF1814F Communication Towers

watermouthhang · 2026-07-21 10:41:28 · 题解

首先，关于线段树分治的部分在其它题解讲得很详细了，本文不予讨论。

让我们把目光集中到所需的数据结构，其需要满足：

1. 单次合并/查询复杂度 O(\log n)；
2. 单次撤销上一步复杂度 O(\log n)；
3. 所有操作结束后，所有和结点 1 连通过的结点需要被标记；
4. 设操作次数为 m，则总时间复杂度 O((n+m)\log n)。

显然，这是基于可撤销并查集的结构。我们考虑精巧地维护标记：

• az 标记，表示以这个结点为根的子树（非路径压缩并查集的树结构）和 1 结点的连通关系。

• t1 标记，表示上一次该结点 az 标记被更新为 1 或 2 （注：1 的维持也算更新）的时间戳。
• t2 标记，标记上一次该节点作为子树被合并的时间戳。

我们知道，在线段树分治中，最终并查集会变成 n 个孤点。也就是说，实际上我们只用维护合并和撤销时根的标记即可（因为最终所有节点都变成了根）。

对于合并操作（将 v 子树合并至 u 子树上）：

1. 若合并完之后，u 子树和 1 连通，则令 u 的 t1 标签更新（时间戳）。

对于撤销操作：（将 v 子树从 u 子树上删去）

• 若 u 的 az 标签为 1:
• • 若 v 的 az 标签为 1，说明 u 的 az 标签由 v 子树提供，此时应将 u 的 az 标签设为 2。
  • 若 v 的 az 标签不为 1，说明 u 的 az 标签不由 v 子树提供，此时应将 v 的 az 标签设为 2，并更新 v 的 t1 标记（因为因此更新了 v 的 az标签）。
• 若 u 的 az 标签为 2，则需要关注 u 的 t1 标签和 v 的 t2 标签的大小关系（即时间戳的前后关系）：
• • 若 v 的 t2 标签早于 u 的 t1 标签，说明对 u 的更新晚于 v 的加入，即更新对 v 有贡献，则将 v 的 az 标签设为 2。当然，要更新 v 的 t1 标签。
  • 否则，对 u 的更新早于 v 的加入，即更新对 v 没有贡献，则无需处理。
• 应将 v 的 t2 标签清零。

由此，我们写出代码。

#include <cstdio>
#include <cassert>
#include <vector>
#include <stack>
using namespace std;
const int maxn=2e5+10;
vector<pair<int,int> > tree[maxn<<2];
int n,m;
void update(int l,int r,int u,int v,int tl,int tr,int c)
{
//  printf("%d %d %d %d %d %d %d\n",l,r,u,v,tl,tr,c);
    if(l>tr||r<tl)return ;
    if(tl<=l&&r<=tr)
    {
        tree[c].push_back(make_pair(u,v));
        return ;
    }
    int mid=l+(r-l)/2;
    update(l,mid,u,v,tl,tr,c*2);
    update(mid+1,r,u,v,tl,tr,c*2+1);
}
int al[maxn],ar[maxn];
const int N=2e5;
bool ans[maxn];
int az[maxn];//0:未曾,1:现在,2:曾经
int t1[maxn];
int t2[maxn];
int dcnt;
int f[maxn];
int sz[maxn];
stack<pair<int,int> > sk;
int finf(int x)
{
    if(f[x]==x)return x;
    return finf(f[x]);
}
bool add(int u,int v)
{
    u=finf(u),v=finf(v);
    if(u==v)return false;
    if(sz[u]<sz[v])swap(u,v);
    sk.push(make_pair(v,u));
    f[v]=u;
    sz[u]+=sz[v];
    if(finf(1)==u)
    {
        az[u]=1;
        t1[u]=++dcnt;
    }
    t2[v]=++dcnt;

    return true;
}

void undo()
{
    pair<int,int> pr=sk.top();
    sk.pop();
    int u=pr.second,v=pr.first;
    f[v]=v;
    sz[u]-=sz[v];

    if(az[u]==1&&az[v]==1)
    {
        az[u]=2;
    }
    else if(az[u]==1&&az[v]!=1)
    {
        az[v]=2;
        t1[v]=++dcnt;
    }
    else if(az[u]==2)
    {
        if(t2[v]<t1[u])
        {
            az[v]=2;
            t1[v]=++dcnt;
        }
    }
    t2[v]=0;
}
void dfs(int l,int r,int c)
{
    int tt=0;
    for(pair<int,int> pr:tree[c])
    {
        tt+=add(pr.first,pr.second);
    }
    if(l<r)
    {
        int mid=l+(r-l)/2;
        dfs(l,mid,c*2);
        dfs(mid+1,r,c*2+1);
    }
    for(int i=1;i<=tt;++i)
    {
        undo();
    }
}
int main()
{
    scanf("%d%d",&n,&m);
    for(int i=1;i<=n;++i)
    {
        scanf("%d%d",&al[i],&ar[i]);
        f[i]=i;
        sz[i]=1;
    }
    for(int i=1;i<=m;++i)
    {
        int u,v;
        scanf("%d%d",&u,&v);
        int l=max(al[u],al[v]);
        int r=min(ar[u],ar[v]);
        if(l<=r)
        {
            update(1,N,u,v,l,r,1);
//          printf("\n");
        }
    }
    az[1]=1;
    dfs(1,N,1);
    for(int i=1;i<=n;++i)
    {
        if(az[i]>0)
        {
            printf("%d ",i);
        }
        assert(f[i]==i);
    }
    printf("\n");
    return 0;
}

时间复杂度 O(n\log^2n)（O(n\log n 次对并查集的操作（由线段树分治导致），每次操作 O(\log n)）。