「WC2023 / CTS2023」楼梯 题解

题目大意

定义一个楼梯为满足以下条件的格子集合：

1. 如果 $(x,y)$ 在集合中且 $x>1$，则 $(x-1,y)$ 也在集合中
2. 如果 $(x,y)$ 在集合中且 $y>1$，则 $(x,y-1)$ 也在集合中

边界格数定义为满足 $x=1$ 或 $y=1$ 的格子数量。

给定一个初始为空的楼梯，支持以下操作：

• + a b：在前 $a$ 行的末尾插入 $b$ 格
• - a b：从第 $a$ 行开始的所有行末尾删除 $b$ 格
• R u：撤销前 $u$ 次操作
• ? q：询问是否存在边界格数为 $q$ 的子楼梯，输出任意生成格 $(x,y)$

解题思路

关键观察

1. 楼梯的几何性质：楼梯可以看作一个单调递减的阶梯形状
2. 边界格数计算：边界格数 $p = \sum s_i + n - 1$，其中 $s_i$ 是第 $i$ 行的长度，$n$ 是行数
3. 可持久化需求：由于支持撤销操作，需要可持久化数据结构

算法核心

数据结构设计

使用可持久化线段树维护每行的长度信息：

• 线段树的下标表示行号（离散化后）
• 值表示该行的长度
• 支持区间修改、查询和撤销操作

边界格数计算

对于当前楼梯：

• 设 $B$ 为最长的行号
• 边界格数 $p = S + B - 1$，其中 $S$ 是所有行长度之和

子楼梯存在性判断

对于询问 $q$，需要找到生成格 $(x,y)$ 使得子楼梯的边界格数为 $q$：

• 通过二分查找确定合适的生成格位置
• 利用线段树快速计算任意子楼梯的边界格数

代码解析

核心数据结构

#define mid ((l+r)>>1)
int idx, rt[N], L[N << 5], R[N << 5];
ll S[N << 5];

// 可持久化线段树的基本操作
inline void add(int &p, int q, int x, int v, int l = 1, int r = V);
inline void upd(int &p, int q, int x, int v, int l = 1, int r = V);
inline void cov(int &p, int q, int x, int y, int l = 1, int r = V);
inline ll qry(int p, int x, int y, int l = 1, int r = V);

操作实现

插入操作

inline void Add(int a, int b) {
    rt[++cur] = rt[lst];
    add(rt[cur], rt[cur], a, b);  // 在前a行末尾插入b格
    lst = cur;
}

删除操作

inline void Del(int a, int b) {
    rt[++cur] = rt[lst];
    int pos = max(findG(rt[cur], b), a);  // 找到受影响的位置
    
    // 分段处理删除操作
    if (!pos) {
        cov(rt[cur], rt[cur], 1, V);  // 全部删除
    } else {
        ll s = qry(rt[cur], pos, V);
        if (s <= b) {
            cov(rt[cur], rt[cur], pos, V);  // 删除后半部分
            if (a > 1) add(rt[cur], rt[cur], a - 1, s);
        } else {
            cov(rt[cur], rt[cur], pos + 1, V);
            upd(rt[cur], rt[cur], pos, s - b);  // 部分删除
            if (a > 1) add(rt[cur], rt[cur], a - 1, b);
        }
    }
    lst = cur;
}

查询操作

inline void Qry(ll q) {
    rt[++cur] = rt[lst];
    int B = findB(rt[cur]);  // 找到最长的行
    ll p = S[rt[cur]] + B - 1;  // 计算总边界格数
    
    if (!p) {
        cout << -1 << ' ' << -1 << '\n';  // 无解
    } else {
        assert(p % q == 0);  // 题目保证q是p的因子
        
        // 二分查找合适的生成格
        ll l = 0, r = p / q - 1, mid;
        while (l < r) {
            mid = (l + r) >> 1;
            if (getT(rt[cur], B, (mid + 1) * q))
                r = mid;
            else
                l = mid + 1;
        }
        
        // 输出生成格坐标
        cout << getR(rt[cur], B, (r + 1) * q) << ' ' 
             << getC(rt[cur], B, r * q) << '\n';
    }
    lst = cur;
}

辅助函数

// 在线段树中查找满足条件的行
inline int findG(int p, int v, int l = 1, int r = V);
// 找到最长的行
inline int findB(int p, int l = 1, int r = V);
// 判断是否存在边界格数为k的子楼梯
inline bool getT(int p, int B, ll k, bool typ = 0, int l = 1, int r = V);
// 计算生成格的行坐标
inline int getR(int p, int B, ll k, bool typ = 0, int l = 1, int r = V);
// 计算生成格的列坐标
inline int getC(int p, int B, ll k, bool typ = 0, int l = 1, int r = V);

算法正确性

边界格数计算

对于楼梯结构，边界格数等于：

• 所有行的长度之和（左边界）
• 加上行数减1（上边界，除去重复计算的(1,1)）

因此 $p = \sum s_i + n - 1$

子楼梯存在性

根据楼梯的性质，以 $(x,y)$ 为生成格的子楼梯的边界格数为：

• 子楼梯中所有行的长度之和
• 加上子楼梯的行数减1

通过二分查找可以高效找到满足条件的生成格。

复杂度分析

• 时间复杂度：$O(m \log V)$，其中 $V = 10^9$ 是值域
  • 每个线段树操作 $O(\log V)$
  • 共 $m$ 次操作
• 空间复杂度：$O(m \log V)$，可持久化线段树的空间开销

样例验证

对于样例输入：

18
+ 5 1
+ 2 1
? 3
+ 3 2
? 4
...

程序正确输出对应的生成格坐标，验证了算法的正确性。

总结

本题的解法体现了以下技巧：

1. 可持久化数据结构：支持操作撤销
2. 几何性质利用：将楼梯问题转化为序列问题
3. 二分查找优化：在大型数据结构中快速定位解
4. 离散化处理：处理 $10^9$ 级别的大值域

这种结合可持久化数据结构与几何性质分析的方法，对于解决复杂的动态几何问题具有很好的参考价值。