POI2013 Maze 题解：从转弯序列到轴对齐多边形多边形的构造

题目分析

POI2013 Maze 要求我们根据一个由'L'（左转）和'P'（右转）组成的字符串，构造一个轴对齐的简单多边形迷宫。核心性质是：当沿着右手扶右手扶墙行走时，记录的转弯序列与输入字符串一致。

关键观察

1. 合法性条件：由于最终要形成封闭多边形（360°转向），左转(L)数量必须比右转(P)多4个（每个L贡献+90°，每个P贡献-90°，总和需为360°）。
2. 结构特性：除4个关键L外，其余L和P可两两匹配（类似括号匹配），每对匹配的转向对应多边形的一个"凸起"或"凹陷"。
3. 轴对齐要求：多边形的边必须平行于x轴或y轴，且相邻边互相垂直。

解题思路

核心思想

将问题转化为括号匹配+动态坐标维护：

• 把L看作左括号，P看作右括号（代码中统一替换为R便于处理）
• 除4个未匹配的L（构成矩形的4个角）外，其余L和R需两两匹配
• 用两个平衡树（Splay）动态维护x轴和y轴的分割点，确保坐标轴对齐且无交叉

算法步骤

1. 合法性检查：验证L的数量比P多4个
2. 匹配预处理：用双向链表记录转弯序列，队列存储可能的匹配起点
3. 递归匹配：消去所有可匹配的L/R对，直到只剩4个关键L
4. 坐标分配：用Splay树动态插入分割点，为每个转弯分配x/y坐标
5. 输出结果：根据Splay树的排名生成最终坐标

代码详解

1. 数据结构定义

// Splay树用于动态维护坐标轴分割点
struct Splay {
    static const int MAXND = 3e5;
    int node, root, ch[MAXND][2], siz[MAXND], fa[MAXND], lab[MAXND];

    Splay() {
        // 初始化根节点和两个哨兵
        newnd(), newnd(), root = fa[ch[1][1] = 2] = 1, siz[1] = 2;
    }

    // 新建节点
    inline int newnd() {
        return siz[++node] = 1, node;
    }

    // 更新节点大小
    inline void pushup(const int u) {
        siz[u] = siz[ch[u][0]] + siz[ch[u][1]] + 1;
    }

    // 旋转操作
    inline void rotate(const int u) {
        int v = fa[u], w = fa[v], k = ch[v][1] == u;
        if ((fa[u] = w)) ch[w][ch[w][1] == v] = u;
        if ((ch[v][k] = ch[u][!k])) fa[ch[v][k]] = v;
        pushup(ch[fa[v] = u][!k] = v), pushup(u);
    }

    // 伸展操作，将u旋转到tar的子节点
    inline void splay(const int u, const int tar) {
        for (int v, w; (v = fa[u]) != tar; rotate(u)) {
            if ((w = fa[v]) != tar) {
                rotate((v == ch[w][0]) == (u == ch[v][0]) ? v : u);
            }
        }
        if (!tar) root = u;
    }

    // 查询节点u的排名
    inline int rank(const int u) {
        splay(u, 0);
        return siz[ch[u][0]] + 1;
    }

    // 查询排名为k的节点
    inline int kth(int k) {
        int u = root;
        while (true) {
            if (k <= siz[ch[u][0]]) u = ch[u][0];
            else if (!(k -= siz[ch[u][0]] + 1)) return u;
            else u = ch[u][1];
        }
    }

    // 在排名rk处插入新节点
    inline int insertAs(const int rk) {
        assert(1 < rk && rk <= siz[root]);
        int u = kth(rk - 1), v = kth(rk);
        splay(u, 0), splay(v, u), assert(!ch[v][0]);
        fa[ch[v][0] = newnd()] = v, pushup(v), pushup(u);
        return ch[v][0];
    }

    // 为节点分配最终坐标（按中序遍历顺序）
    inline void relable(const int u) {
        if (!u) return ;
        relable(ch[u][0]), lab[u] = ++lab[0], relable(ch[u][1]);
    }
};

Splay树的核心作用是动态维护坐标轴上的分割点，支持高效插入和排名查询，确保我们能在O(log n)时间内找到新坐标的位置。

2. 主逻辑实现

2.1 预处理与合法性检查

int main() {
    scanf("%s", tur), n = strlen(tur);
    // 将P替换为R，统一处理左右转
    std::replace(tur, tur + n, 'P', 'R');

    // 检查L比R多4个
    int dlt = 0;
    rep (i, 0, n - 1) dlt += tur[i] == 'L' ? 1 : -1;
    if (dlt != 4) return puts("NIE"), 0;

    // 初始化双向链表和gap队列
    rep (i, 0, n - 1) {
        pre[i] = (i + n - 1) % n;  // 前一个转弯的索引
        suf[i] = (i + 1) % n;      // 后一个转弯的索引
        // 记录转向变化的位置（可能的匹配起点）
        if (tur[i] != tur[(i + 1) % n]) gap.push(i);
    }

    solve();  // 递归匹配转弯对
    // 分配最终坐标
    X.relable(X.root), Y.relable(Y.root);
    // 输出结果
    rep (i, 0, n - 1) printf("%d %d\n", X.lab[xid[i]], Y.lab[yid[i]]);
    return 0;
}

2.2 递归匹配核心函数

inline void solve() {
    // 终止条件：所有可匹配对都已处理，只剩4个L
    if (gap.empty()) {
        std::vector<int> rest;
        rep (i, 0, n - 1) if (!vis[i]) rest.push_back(i);
        assert(rest.size() == 4);  // 应该正好剩4个L
        
        // 插入分割点构造矩形
        X.insertAs(2), X.insertAs(3);
        Y.insertAs(2), Y.insertAs(3);
        
        // 为4个L分配坐标（构成矩形的4个顶点）
        rep (i, 0, 3) {
            xid[rest[i]] = !i || i == 3 ? 3 : 4;
            yid[rest[i]] = i < 2 ? 3 : 4;
        }
        return ;
    }

    // 取出一个可能的匹配起点
    int p = gap.front(), q = suf[p], s = pre[p], t = suf[q];
    gap.pop();
    
    // 检查p和q是否可匹配（必须是L和R的组合）
    if (vis[p] || vis[q] || tur[p] == tur[q]) return solve();
    
    // 标记p和q为已匹配，更新双向链表
    vis[p] = vis[q] = true;
    suf[s] = t;  // 跳过p和q，直接连接s和t
    pre[t] = s;
    
    // 如果s和t转向不同，加入gap作为新的匹配候选
    if (tur[s] != tur[t]) gap.push(s);
    
    // 先处理子问题
    solve();
    
    // 为p和q分配坐标
    if (yid[s] == yid[t]) {  // s和t在同一水平线上
        int sxr = X.rank(xid[s]), txr = X.rank(xid[t]);
        // 在s和t的x坐标之间插入新分割点
        xid[p] = xid[q] = X.insertAs(std::min(sxr, txr) + 1);
        yid[p] = yid[s];  // p与s同y坐标
        
        // 根据转向决定q的y坐标位置
        if ((tur[p] == 'L') == (sxr < txr)) {
            yid[q] = yid[t] = Y.insertAs(Y.rank(yid[p]) + 1);
        } else {
            yid[q] = yid[t] = Y.insertAs(Y.rank(yid[p]));
        }
    } else {  // s和t在同一垂直线上
        int syr = Y.rank(yid[s]), tyr = Y.rank(yid[t]);
        // 在s和t的y坐标之间插入新分割点
        yid[p] = yid[q] = Y.insertAs(std::min(syr, tyr) + 1);
        xid[p] = xid[s];  // p与s同x坐标
        
        // 根据转向决定q的x坐标位置
        if ((tur[p] == 'R') == (syr < tyr)) {
            xid[q] = xid[t] = X.insertAs(X.rank(xid[p]) + 1);
        } else {
            xid[q] = xid[t] = X.insertAs(X.rank(xid[p]));
        }
    }
}

3. 算法关键点解析

1. 匹配机制：通过双向链表高效删除已匹配的转弯对，队列gap记录可能的匹配起点，确保O(n)时间内完成所有匹配。

2. 坐标分配原则：

   • 每对匹配的转弯（p和q）的坐标基于其前后未匹配的转弯（s和t）推导
   • 新坐标始终插入在s和t的坐标之间，确保轴对齐且无交叉
   • 最终4个未匹配的L构成矩形的4个角，保证多边形封闭

3. Splay树的作用：

   • 动态维护坐标轴上的分割点，支持高效插入
   • 通过排名确定坐标值，确保坐标是递增的整数
   • 中序遍历分配最终坐标，保证几何一致性

复杂度分析

• 时间复杂度：O(n log n)，其中n是字符串长度。每个转弯最多被处理一次，Splay树的每次插入和查询操作都是O(log n)。
• 空间复杂度：O(n)，Splay树节点数和辅助数组大小均为O(n)。

总结

本题的核心是将几何构造问题转化为括号匹配+数据结构维护的问题。通过递归匹配L和R，并用Splay树动态维护坐标分割点，我们高效地构造出了符合要求的轴对齐多边形。这种将几何问题抽象为符号匹配和数据结构操作的思路，在处理复杂构造类问题时非常有用。