题解：P17066 [ICPC 2017 Shenyang R] Bridge

· · 题解

题意简述

动态维护一张 2\times n 的梯形网格图。每次加入或删除一条原网格中的边，且操作后整张图仍然连通。求每次操作后的桥数。

解题思路

称连接同一列两个结点的边为竖边，连接同一行相邻列的边为横边。

梯形图中的简单环一定由两条竖边和它们之间上下两条完整横链组成。事实上，环每次经过竖边都会切换所在行。若切换超过两次，某一行中用于连接这些竖边的区间会相互覆盖，环便会重复经过结点。因此，判断一条边是否为桥，只需判断它能否处于这样的矩形环上。

把当前存在的竖边按列排序。考虑两条相邻竖边 l<r，它们之间没有其他竖边。

若 l,r 都是真实竖边，区间内至多缺少一条横边。若同一行缺少两条横边，两处缺口之间的结点无法通过竖边离开该行。若上下两行各缺一条，设缺口分别位于 p\le q。把上行不超过 p 的结点和下行不超过 q 的结点放在一侧，其余结点放在另一侧。这个割的两条横边都恰好是缺边，区间内部又没有竖边，图会断开。这两种情况都与连通性矛盾。

第一条竖边左侧和最后一条竖边右侧不能缺少横边，否则缺口外侧的一段结点没有任何竖边可用于换行，也会与整张图断开。

因此，每个相邻竖边区间只需要记录一个状态：没有缺口，或者唯一缺失横边的位置。缺口位于哪一行不影响桥的数量。

在有序集合中加入哨兵 0,n+1。对相邻元素 l<r，令 gap_l 表示其中唯一缺失横边的位置，没有缺口时为 0。

先计算区间内横边的贡献 H(l,r)。

于是：

H(l,r)= \begin{cases} 2(r-l-1) & l=0\lor r=n+1 \\ 2(r-l)-1 & gap_l\ne0 \\ 0 & gap_l=0 \end{cases}

再计算真实竖边 x 的贡献。它能进入环，当且仅当左侧或右侧至少有一个内部区间没有缺口。若两侧分别接触边界或含有缺口，就不存在经过 x 的环。由于整张图连通，此时 x 是桥。

定义区间为阻断区间，当且仅当它接触哨兵或含有缺口。设 l,r 是 x 左右最近的竖边，则：

V(x)=[(l,x)\text{ 被阻断}]\cdot[(x,r)\text{ 被阻断}]

总桥数就是所有相邻竖边区间的 H 之和，再加所有真实竖边的 V。

一次修改只会改变常数个局部贡献。

修改横边时，先找到它所在的相邻竖边区间 (l,r)。修改前减去 H(l,r)+V(l)+V(r)，改变 gap_l，再把这三项的新值加回。

加入列 x 的竖边时，原区间 (l,r) 被拆成 (l,x) 和 (x,r)。原缺口若位于 x 左侧，就留在左区间；否则移到右区间。修改前删除 H(l,r),V(l),V(r)，修改后加入两个新区间的横边贡献和 V(l),V(x),V(r)。

删除竖边执行相反过程。区间 (l,x) 与 (x,r) 合并为 (l,r)。连通性保证两个旧区间不可能同时含有缺口，所以把唯一可能存在的缺口转移给 gap_l 即可。

初始图的所有区间都完整。当 n\ge2 时每条边都处于某个矩形环中，桥数为 0；当 n=1 时，唯一竖边是桥。

有序集合用升序提示插入，可在线性时间内初始化。每次修改只进行常数次集合操作，时间复杂度为 O(\log n)。空间复杂度为 O(n)。

参考代码

#include <bits/stdc++.h>
using namespace std;

const int N=200005;
int n,ans;
int gap[N];
set<int> s;
bool broken(int l,int r)
{
    return l==0||r==n+1||gap[l]!=0;
}
int horizontal(int l,int r)
{
    if(l==0||r==n+1)return 2*(r-l-1);
    if(gap[l])return 2*(r-l)-1;
    return 0;
}
int vertical(int x)
{
    if(x==0||x==n+1)return 0;
    auto it=s.find(x);
    return broken(*prev(it),x)&&broken(x,*next(it));
}
void add_vertical(int x)
{
    auto it=s.lower_bound(x);
    int l=*prev(it);
    int r=*it;
    ans-=horizontal(l,r)+vertical(l)+vertical(r);
    int k=gap[l];
    gap[l]=gap[x]=0;
    if(k<x)gap[l]=k;
    else gap[x]=k;
    s.insert(x);
    ans+=horizontal(l,x)+horizontal(x,r)+vertical(l)+vertical(x)+vertical(r);
}
void del_vertical(int x)
{
    auto it=s.find(x);
    int l=*prev(it);
    int r=*next(it);
    ans-=horizontal(l,x)+horizontal(x,r)+vertical(l)+vertical(x)+vertical(r);
    if(!gap[l])gap[l]=gap[x];
    gap[x]=0;
    s.erase(it);
    ans+=horizontal(l,r)+vertical(l)+vertical(r);
}
void change_horizontal(int op,int x)
{
    auto it=s.upper_bound(x);
    int l=*prev(it);
    int r=*it;
    ans-=horizontal(l,r)+vertical(l)+vertical(r);
    if(op==1)gap[l]=0;
    else gap[l]=x;
    ans+=horizontal(l,r)+vertical(l)+vertical(r);
}
void solve()
{
    int m;
    cin>>n>>m;
    fill(gap,gap+n+2,0);
    s.clear();
    for(int i=0;i<=n+1;i++)s.insert(s.end(),i);
    ans=n==1;
    while(m--)
    {
        int op,x,y,u,v;
        cin>>op>>x>>y>>u>>v;
        if(x!=u)
        {
            if(op==1)add_vertical(y);
            else del_vertical(y);
        }
        else change_horizontal(op,min(y,v));
        cout<<ans<<'\n';
    }
}
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int T;
    cin>>T;
    while(T--)solve();
    return 0;
}