PA 2019 Runda 5 Osady i warownie 2 题解

题目分析

这道题要求在一个动态网格上维护从左上角到右下角的路径存在性。每次操作可能添加障碍，需要判断添加后是否仍然存在路径。

关键点：

• 网格大小可达 $10^5 \times 10^5$，不能直接存储整个网格
• 需要高效判断路径存在性
• 操作是动态的，且包含异或加密

解题思路

核心观察

1. 路径性质：从 $(0,0)$ 到 $(n-1,m-1)$ 的路径必须向右和向下移动
2. 关键点：如果存在路径，那么所有路径会形成从左上到右下的"前沿"
3. 数据结构：使用集合维护关键的前沿点

算法设计

代码采用了双前沿维护的方法：

主要组件：

1. 两个前沿集合：

   • sx[], sy[]：维护从左上角可达的右下前沿
   • tx[], ty[]：维护从右下角可达的左上前沿
   • wx[], wy[]：临时工作集合

2. DFS扩展：

   • dfs0：从新障碍点向左上扩展，更新可达前沿
   • dfs1：从新障碍点向右下扩展，更新反向可达前沿

代码详解

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

const int N = 1e5 + 10;
int n, m, q;
set<int> sx[N], sy[N], tx[N], ty[N], wx[N], wy[N];

// 从(x,y)向左上扩展可达前沿
void dfs0(int x, int y) {
    wx[x].erase(y); wy[y].erase(x);
    sx[x].insert(y); sy[y].insert(x);
    
    // 向左扩展
    if (x > 0) {
        auto it = wx[x - 1].upper_bound(y + 1);
        if (it != wx[x - 1].begin())
            dfs0(x - 1, *prev(it));
    }
    
    // 向上扩展  
    if (y + 1 < m) {
        auto it = wy[y + 1].lower_bound(x - 1);
        if (it != wy[y + 1].end())
            dfs0(*it, y + 1);
    }
}

// 从(x,y)向右下扩展反向可达前沿
void dfs1(int x, int y) {
    wx[x].erase(y); wy[y].erase(x);
    tx[x].insert(y); ty[y].insert(x);
    
    // 向右扩展
    if (y > 0) {
        auto it = wy[y - 1].upper_bound(x + 1);
        if (it != wy[y - 1].begin())
            dfs1(*prev(it), y - 1);
    }
    
    // 向下扩展
    if (x + 1 < n) {
        auto it = wx[x + 1].lower_bound(y - 1);
        if (it != wx[x + 1].end())
            dfs1(x + 1, *it);
    }
}

int main() {
    cin >> n >> m >> q;
    int o = 0;  // 加密变量
    
    for (int i = 0; i < q; i++) {
        int r, c, z;
        cin >> r >> c >> z;
        int x = (r ^ o) % n, y = (c ^ o) % m;
        
        bool result = [&]() -> bool {
            // 如果点已经是障碍或在某个前沿中，忽略
            if (sx[x].count(y) || tx[x].count(y) || wx[x].count(y))
                return false;
                
            // 判断点的位置关系
            bool cond1 = (x == n - 1 || y == 0 || 
                         sx[x + 1].lower_bound(y - 1) != sx[x + 1].end() ||
                         sy[y - 1].upper_bound(x + 1) != sy[y - 1].begin());
                         
            bool cond2 = (x == 0 || y == m - 1 ||
                         tx[x - 1].upper_bound(y + 1) != tx[x - 1].begin() ||
                         ty[y + 1].lower_bound(x - 1) != ty[y + 1].end());
            
            int case_val = (cond1 << 1) | cond2;
            
            switch (case_val) {
            case 3:  // 两个方向都可达 - 是关键点
                o ^= z;
                return true;
                
            case 2:  // 只从左上前沿可达
                wx[x].insert(y); wy[y].insert(x);
                dfs0(x, y);
                break;
                
            case 1:  // 只从右下前沿可达  
                wx[x].insert(y); wy[y].insert(x);
                dfs1(x, y);
                break;
                
            case 0:  // 两个方向都不可达 - 暂时存储
                wx[x].insert(y); wy[y].insert(x);
                break;
            }
            return false;
        }();
        
        cout << (result ? "TAK" : "NIE") << endl;
    }
    
    return 0;
}

算法原理

双前沿维护

1. 左上前沿 (s)：从 $(0,0)$ 可达的最右下位置

   • 对于每行 $x$，sx[x] 存储该行可达的最右列
   • 对于每列 $y$，sy[y] 存储该列可达的最下行

2. 右下前沿 (t)：从 $(n-1,m-1)$ 反向可达的最左上位置

   • 对于每行 $x$，tx[x] 存储该行反向可达的最左列
   • 对于每列 $y$，ty[y] 存储该列反向可达的最上行

关键点判断

一个点 $(x,y)$ 是关键点当且仅当：

• 它同时位于左上前沿和右下前沿
• 阻塞它会破坏所有路径

这种情况对应代码中的 case 3。

DFS扩展逻辑

• dfs0：当添加障碍时，如果它影响左上前沿，需要重新计算受影响的可达区域
• dfs1：类似地处理右下前沿的更新

复杂度分析

• 时间复杂度：每个点最多被每个DFS访问一次，总体 $O(k \log k)$
• 空间复杂度：$O(n + m)$，存储各个集合

样例解析

对于样例输入，算法会：

1. 初始时整个网格都可通行
2. 逐个处理操作，判断每个点是否为关键点
3. 当遇到关键点时输出 TAK 并更新加密变量
4. 否则输出 NIE 并可能更新前沿

总结

这道题的解题亮点：

1. 双前沿技术：通过维护两个方向的可达前沿来高效判断连通性
2. 惰性更新：只在必要时进行DFS扩展
3. 集合优化：使用 set 高效维护有序的前沿点
4. 加密处理：正确处理异或加密的输入

算法避免了直接处理巨大的网格，而是通过维护关键信息来高效回答路径存在性查询，是处理大规模网格连通性问题的经典方法。