洛谷 P4246 [SHOI2008] 堵塞的交通 题解

问题描述

在一个1×n的网格中，每个格子有一个状态（堵塞或未堵塞）。初始时所有格子均未堵塞。有两种操作：1. 堵塞某个格子；2. 查询两个指定格子之间是否存在一条不经过堵塞格子的路径。路径可以左右移动，且只能在未堵塞格子中移动。

分析思路

本题需高效维护区间连通性，采用线段树数据结构。每个节点存储区间端点连接状态、区间内通路类型及堵塞信息，通过合并子节点信息判断整体连通性与端点连接。

线段树节点定义

struct Node {
    int l, r;          // 区间范围
    bool left_up;      //左端点上是否有连接
    bool left_down;    //左端点下是否有连接
    bool right_up;     //右端点上是否有连接
    bool right_down;   //右端点下是否有连接
    bool vertical;     //区间内是否有垂直通路
    bool horizontal;   //区间内是否有水平通路
    bool blocked;      //整个区间是否堵塞};

合并操作逻辑

• 若整个区间堵塞，所有状态均为false
• 水平通路：左/右子区间有水平通路或端点连接
• 垂直通路：左/右子区间有垂直通路或端点连接
• 更新端点连接状态时考虑子区间水平通路影响

代码实现

#include <cstdio>
#include <algorithm>
using namespace std;

const int MAXN =

【超多注释 | 正确题解】洛谷 P4246 [SHOI2008] 堵塞的交通 [线段树维护区间连通性]-CSDN博客