P5787

· · 题解

upd on 2025/8/5 6:52

声明：本人保证是在阅读并理解了洛谷题解补充计划和洛谷模板题题解规范的完整内容后提交该文章的。

upd on 2025/8/7 11:44

初稿提交时审核通过，但作者自查发现笔误，为造成的审核重复性劳动表示歉意。

算法介绍

问题背景

本模板题旨在解决一类经典的离线动态图问题。考虑一个场景：我们需要维护一个图，支持动态地加入和删除边，并实时查询图的某些性质（例如连通性、是否为二分图等）。

对于只有加边的操作，一个标准的、带有路径压缩优化的并查集能以近乎常数的时间复杂度高效完成。然而，删除操作却是一个难题。因为路径压缩等均摊优化会彻底改变并查集的内部结构，使得撤销某一次特定的合并操作变得异常困难。

可撤销数据结构

让我们先思考一个简化版的问题：如果操作并非任意删除，而是严格地撤销上一步操作呢？

这种回退的需求，实现起来就容易得多。以并查集为例，我们可以：

用线段树对时间进行分治

然而，原问题要求删除任意指定时间的边，这似乎超出了可撤销模型的处理能力。线段树分治的巧妙之处就在于，它通过对时间维度进行分治，将一个看似需要可追溯化的复杂问题，转化为了仅需可撤销数据结构即可解决的模型。

其核心流程如下：

通过这种方式，任意时刻的删除操作被自然地转化为了 DFS 回溯时的撤销操作，完美地适配了可撤销数据结构的特性。

对于P5787的特化：加权并查集

在掌握了线段树分治的通用框架后，我们需要解决本题的核心问题：如何利用一个可撤销的数据结构，来动态维护一个图是否为二分图。

一个图是二分图的充要条件是图中不存在奇数环。这里，我们采用一种精妙的带权并查集来维护节点间的关系，从而判断奇数环的产生。

其核心思想如下：

关系量化：

路径查询 fat(x)：

合并与冲突判断 tog(u, v)：

判断冲突：

执行合并：

通过将这种可撤销的带权并查集与线段树分治框架结合，我们就能准确地在每个时间点判断图是否为二分图。

复杂度证明

设操作（边）的总数为 m，时间轴的总长度为 k，图的节点数为 n。

时间复杂度:

预处理（操作挂载）：一条边的生命周期为 [l, r]，将其挂载到代表总时间 [1, k] 的线段树上，需要分解成 O(\log k) 个线段树节点区间。因此，m 条边总共会产生 O(m \log k) 次挂载。

DFS 遍历：DFS 会遍历线段树的每个节点。在每个节点，算法会应用（进入时）和撤销（离开时）所有挂载在该节点上的操作。总的应用与撤销次数与总挂载次数同阶，为 O(m \log k)。

数据结构操作：我们使用的是可撤销的扩展域并查集。由于放弃了路径压缩，只采用按秩合并，其 find 和 unite 操作的单次时间复杂度为稳定的 O(\log N)（在本题中 N = 2n）。在这里解释了为何要放弃路径压缩：虽然路径压缩的均摊复杂度极低，但其单次操作的最坏时间以及对数据结构“势”的破坏性改变，使其无法支持高效、精确的单步撤销。我们牺牲了单次查询的效率，换来了宝贵的可撤销性。

总体时间复杂度：将上述几点综合考虑，得到总时间复杂度为 O(m \log k \log n)。

空间复杂度

线段树节点：线段树本身需要 O(k) 的空间。

操作存储：m 条边在 O(\log k) 个节点上存储，总共需要 O(m \log k) 的空间。

可撤销并查集的栈：栈的深度取决于DFS的递归深度 O(\log k) 以及每层挂载的边数，最坏情况下与总挂载数同阶，为 O(m \log k)。

因此，总空间复杂度为 O(k + m \log k)。

代码实现

本节将逐一解析代码的关键部分，将前述的算法思想与最终的实现细节对应起来。代码主要包含两个核心模块：带权并查集的操作函数，以及线段树分治的递归框架。

在阅读前，请注意以下全局变量的含义：

带权并查集

这部分是整个数据结构的核心，负责维护节点间的关系并判断冲突。

// 查询节点x的根，并返回{根节点, x到根的路径权值异或和}
pair<int,bool> fat(int x)
{
    bool y=0;
    while(f[x]!=x)
    {
        y^=w[x];
        x=f[x];
    }
    return make_pair(x,y);
}

// 宏定义，用于判断x和y是否为“同类”
#define sam(x,y) fat(x)==fat(y)

// 合并x和y，并返回用于撤销的信息
pair<int,int> tog(int x,int y)
{
    pair<int,bool>a=fat(x),b=fat(y);
    // 如果根已相同，则不合并，返回一个无效标记{0,0}
    if(a.F==b.F)return make_pair(0,0);
    // 按秩合并：将小树合并到大树
    if(sz[a.F]>sz[b.F])swap(a,b);
    // 设置小树根的权值，维持x、y为异类的关系
    w[a.F]=1^a.S^b.S;
    // 更新父节点和大小
    f[a.F]=b.F,sz[b.F]+=sz[a.F];
    // 返回{被合并的根, 新的根}，用于撤销
    return make_pair(a.F,b.F);
}

// 撤销操作，恢复a.F为根，并更新a.S的大小
void split(pair<int,int>a)
{
    // 如果是无效标记，则不操作
    if(a.F==0)return;
    // 恢复被合并根的父节点、权值和大小
    w[a.F]=0,f[a.F]=a.F,sz[a.S]-=sz[a.F]; 
}

线段树分治

这部分是算法的框架，负责将边的生命周期映射到线段树上，并通过DFS进行求解。

// 将边x挂载到其生命周期[lb, rb]对应的线段树节点上
void Add(int l,int r,int u,int lb,int rb,pair<int,int>x)
{
    if(rb<l||r<lb)return;
    if(lb<=l&&r<=rb)
    {
        ++tl[u];
        o[u].push_back(x);
        return;
    }
    int mid=(l+r)>>1;
    Add(l,mid,u<<1,lb,rb,x);
    Add(mid+1,r,u<<1|1,lb,rb,x);
}

// DFS求解函数
void Query(int l,int r,int u)
{
    // 记录进入此节点前的栈大小，作为回溯的“检查点”
    unsigned bef=e.size();
    // 遍历此节点上的所有边
    for(int i=0;i<tl[u];++i)
    {
        // 如果发现奇数环
        if(sam(o[u][i].F,o[u][i].S))
        {
            // 此节点代表的时间区间内，图都不是二分图
            for(int j=l;j<=r;++j)printf("No\n");
            // 回溯前，撤销本层已进行的所有合并
            while(e.size()!=bef)
            {
                split(e.top());
                e.pop();
            }
            return; // 剪枝，直接返回
        }
        else
        {
            // 否则，合并并记录操作
            e.push(tog(o[u][i].F,o[u][i].S));
        }
    }

    // 如果到达叶子节点，说明此时间点没有冲突
    if(l==r)
        printf("Yes\n");
    else
    {
        // 否则，递归进入左右子区间
        int mid=(l+r)>>1;
        Query(l,mid,u<<1);
        Query(mid+1,r,u<<1|1);
    }

    // 回溯：撤销本层所有操作，恢复到进入前的状态
    while(e.size()>bef)
    {
        split(e.top());
        e.pop();
    }
}

完整代码

#include<fstream>
#include<vector>
#include<stack> 
#define F first
#define S second
const int N=110000;
using namespace std;
int n,m,k,tl[N<<2],f[N],sz[N];
bool w[N];
vector<pair<int,int> >o[N<<2];
stack<pair<int,int> >e;
pair<int,bool> fat(int x)
{
    bool y=0;
    while(f[x]!=x)
    {
        y^=w[x];
        x=f[x];
    }
    return make_pair(x,y);
}
#define sam(x,y) fat(x)==fat(y)
pair<int,int> tog(int x,int y)
{
    pair<int,bool>a=fat(x),b=fat(y);
    if(a.F==b.F)return make_pair(0,0);
    if(sz[a.F]>sz[b.F])swap(a,b);
    w[a.F]=1^a.S^b.S;
    f[a.F]=b.F,sz[b.F]+=sz[a.F];
    return make_pair(a.F,b.F);
}
void split(pair<int,int>a)
{
    if(a.F==0)return;
    w[a.F]=0,f[a.F]=a.F,sz[a.S]-=sz[a.F]; 
}
void Add(int l,int r,int u,int lb,int rb,pair<int,int>x)
{
    if(rb<l||r<lb)return;
    if(lb<=l&&r<=rb)
    {
        ++tl[u];
        o[u].push_back(x);
        return;
    }
    int mid=(l+r)>>1;
    Add(l,mid,u<<1,lb,rb,x);
    Add(mid+1,r,u<<1|1,lb,rb,x);
}
void Query(int l,int r,int u)
{
    unsigned bef=e.size();
    for(int i=0;i<tl[u];++i)
    if(sam(o[u][i].F,o[u][i].S))
    {
        for(int j=l;j<=r;++j)printf("No\n");
        while(e.size()!=bef)
        {
            split(e.top());
            e.pop();
        }
        return;
    }
    else
    e.push(tog(o[u][i].F,o[u][i].S));
    if(l==r)
        printf("Yes\n");
    else
    {
        int mid=(l+r)>>1;
        Query(l,mid,u<<1);
        Query(mid+1,r,u<<1|1);
    }
    while(e.size()>bef)
    {
        split(e.top());
        e.pop();
    }
}
int main()
{
    scanf("%d%d%d",&n,&m,&k);
    for(int i=1;i<=n;++i)f[i]=i,sz[i]=1,w[i]=0;
    for(int i=0;i<m;++i)
    {
        int x,y,l,r;
        scanf("%d%d%d%d",&x,&y,&l,&r);
        if(l<r)Add(1,k,1,l+1,r,make_pair(x,y));
    }
    Query(1,k,1);
    return 0;
 }