generator 3 - 题解

标签与难度

标签: 计算几何, 凸包, 数论, 周期性, 倍增, 稀疏表, 线性同余生成器难度: 2500

题目大意喵~

你好呀，未来的算法大师！本喵今天带来一个看起来有点吓人的问题，但别担心，跟着本喵的思路，我们一定能轻松解决它，喵~

题目是这样子的：我们需要计算 $n$ 个二维平面上的点构成的凸包的面积。但是呢，这个 $n$ 特别特别大（可能高达 $10^{18}$ ！），所以我们不能一个一个地把点都生成出来。

这些点 $(x_i, y_i)$ 是通过一个线性同余生成器（LCG）产生的：

给你初始值 $x_0, y_0$ 和一些参数 $a_x, a_y, b_x, b_y, p_x, p_y$ 。
点的坐标由以下公式递推得出： $x_i = (a_x \cdot x_{i-1} + b_x) \pmod{p_x}$ $y_i = (a_y \cdot y_{i-1} + b_y) \pmod{p_y}$
我们需要计算由点集 $\{(x_i, y_i) | 0 \le i < n\}$ 构成的凸包的面积。

这里的关键线索是， $n$ 很大，但是模数 $p_x$ 和 $p_y$ 相对较小（最大 $2 \cdot 10^5$ ）。这就像是在暗示我们，这些点坐标的生成序列里一定有规律可循，对吧？

解题思路分析

面对这么大的 $n$ ，暴力生成所有点然后跑凸包算法是绝对行不通的。我们的突破口就在于生成公式中的模运算 mod。这使得 $x$ 和 $y$ 的坐标序列必然是周期性的！就像小猫咪喜欢绕着毛线球转圈圈一样，喵~

咱们一步一步来拆解这个问题。

第一步：发现周期的猫爪印

一个序列在一个有限的集合（比如 $0$ 到 $p_x-1$ ）里不断生成新值，迟早会遇到一个曾经出现过的值。一旦某个值重复出现，整个序列就会开始一个循环。

这个序列通常分为两部分：

非周期部分（尾巴）：序列开头的一段，里面的值都是第一次出现。
周期部分（圈圈）：紧跟在尾巴后面，序列会在这里无限循环。

我们可以用一个 visited_at 数组来轻松找到这个循环。visited_at[v] = i 表示值 v 第一次在索引 i 处出现。当我们生成一个新的值 x_k，如果发现它在 visited_at 中已经有记录了（比如在 s_x 处），那么我们就找到了循环！

非周期部分的长度就是 $s_x$ 。
周期部分的长度是 $c_x = k - s_x$ 。

对 $x$ 和 $y$ 序列分别进行这个操作，我们就能得到它们各自的非周期起始点 $s_x, s_y$ 和周期长度 $c_x, c_y$ 。

第二步：聪明的猎手，简化问题

想一想，哪些点才有可能成为凸包的顶点呢？

对于任意一个固定的 x 坐标，比如 $x_{val}$ ，可能会有很多个点 $(x_{val}, y_1), (x_{val}, y_2), \dots$ 。在这些点中，只有 y 坐标最大和最小的两个点，即 $(x_{val}, y_{\max})$ 和 $(x_{val}, y_{\min})$ ，才有资格成为凸包的顶点。所有其他的点都被它们俩“包”在里面了。

所以，我们的问题就转化成了： 对于每一个可能出现的 x 坐标，找出在所有 $n$ 个点中，与它配对的 y 坐标的最小值和最大值是多少。

我们将这些“候选点”（即每个 x 对应的 y-min 和 y-max 点）收集起来，再对这个大大缩减后的点集求凸包，问题就解决啦！

第三步：雷霆一击，计算 Min/Max Y

这是最核心的部分。我们怎么在不遍历所有 $n$ 个点的情况下，找到每个 x 对应的 y 范围呢？

我们可以把点按索引 $i$ 分成两部分处理：

“尾巴”部分 ( $i < \max(s_x, s_y)$ )：这部分点的数量是可控的。我们直接生成这些点，并用它们来更新每个 $x$ 坐标对应的 min_y 和 max_y 数组。小菜一碟，喵~
“圈圈”部分 ( $i \ge s_x$ )：当 $x$ 序列进入循环后，事情变得有趣起来。
- 考虑一个在 $x$ 循环中出现的 $x_{val}$ ，它首次出现在索引 $i$ 处（ $s_x \le i < s_x + c_x$ ）。
- 之后，它会以 $c_x$ 为周期反复出现，即在索引 $i, i+c_x, i+2c_x, \dots$ 处。
- 对应的 y 坐标序列就是 $y_i, y_{i+c_x}, y_{i+2c_x}, \dots$ 。
- 我们需要求这个 y 子序列的最小值和最大值。注意，这个子序列的索引在 $y$ 的序列中是按一个固定的步长 $c_x$ 跳跃的！
这是一个典型的可以用 倍增（Binary Lifting） 或 稀疏表（Sparse Table） 解决的查询问题。我们可以像猫咪在屋顶间跳跃一样，快速地跨越很长的距离！
倍增预处理：
- 我们为 $y$ 的循环部分（长度为 $c_y$ ）建立一个稀疏表。
- st_max[j][k] 表示：从 $y$ 循环的第 $k$ 个位置开始，每次跳 $c_x$ 步，总共跳 $2^j$ 次，这期间遇到的所有 $y$ 值的最大值。
- 递推关系如下： $\text{st\_max}[j][k] = \max(\text{st\_max}[j-1][k], \text{st\_max}[j-1][(k + (2^{j-1}) \cdot c_x) \pmod{c_y}])$
- st_min 的递推同理。
查询：
- 对于每个在 $x$ 循环中的 $x_i$ ，我们计算出它在 $n$ 个点中总共出现了多少次，记为 count。
- 然后，我们利用预处理好的稀疏表，在 $O(\log(\text{count}))$ 的时间内查询出对应的 $y$ 子序列的最小值和最大值。
- 用查询结果更新全局的 min_y[x_i] 和 max_y[x_i]。

第四步：收获战利品！求凸包与面积

经过上面的步骤，我们已经成功找到了所有候选点。接下来就简单啦：

建立凸包：将所有候选点 $(x, \min\_y[x])$ 和 $(x, \max\_y[x])$ 收集起来。使用经典的 Andrew's Monotone Chain 算法，先按 x 坐标排序，然后分别构造上凸壳和下凸壳，最后合并成一个完整的凸包。
计算面积：使用 鞋带公式（Shoelace Formula） 计算凸包面积。对于凸包上按顺序排列的顶点 $(x_0, y_0), (x_1, y_1), \dots, (x_{k-1}, y_{k-1})$ ，其面积为： $\text{Area} = \frac{1}{2} \left| \sum_{i=0}^{k-1} (x_i y_{i+1} - x_{i+1} y_i) \right| = \frac{1}{2} \left| \sum_{i=0}^{k-1} \text{cross}((x_i, y_i), (x_{i+1}, y_{i+1})) \right|$ （其中 $(x_k, y_k) = (x_0, y_0)$ ）。题目通常要求输出两倍的面积，也就是上面公式中求和部分的值。

好啦，思路已经非常清晰了！让我们把这个计划付诸实践吧，喵~

代码实现

cpp

#include <iostream>
#include <vector>
#include <algorithm>
#include <map>

// 为了防止 long long 溢出，使用 __int128
using int128 = __int128_t;

// 定义点结构体
struct Point {
    long long x, y;
};

// 叉积计算，用于凸包和面积
long long cross_product(Point a, Point b, Point c) {
    return (b.x - a.x) * (c.y - a.y) - (b.y - a.y) * (c.x - a.x);
}

// 找到序列的非周期部分和周期部分
std::pair<int, int> find_cycle(long long start_val, long long a, long long b, long long p, std::vector<long long>& sequence) {
    std::map<long long, int> visited_at;
    long long current_val = start_val;
    int i = 0;
    while (visited_at.find(current_val) == visited_at.end()) {
        visited_at[current_val] = i;
        sequence.push_back(current_val);
        current_val = (a * current_val + b) % p;
        i++;
    }
    return {visited_at[current_val], i - visited_at[current_val]};
}

const int MAX_P = 200005;
const int LOG_N = 62;
const long long INF = 4e18; // 一个足够大的数

// 全局的y坐标范围
long long global_min_y[MAX_P];
long long global_max_y[MAX_P];

// 稀疏表
long long st_min[LOG_N][MAX_P];
long long st_max[LOG_N][MAX_P];

int main() {
    // 加速输入输出，喵~
    std::ios_base::sync_with_stdio(false);
    std::cin.tie(NULL);

    long long x0, y0, ax, ay, bx, by, px, py, n;
    std::cin >> x0 >> y0 >> ax >> ay >> bx >> by >> px >> py >> n;

    // 1. 找到 x 和 y 序列的周期
    std::vector<long long> seq_x, seq_y;
    auto [sx, cx] = find_cycle(x0, ax, bx, px, seq_x);
    auto [sy, cy] = find_cycle(y0, ay, by, py, seq_y);

    // 2. 初始化全局y范围数组
    for (int i = 0; i < px; ++i) {
        global_min_y[i] = INF;
        global_max_y[i] = -INF;
    }

    // 3. 处理 "尾巴" 部分的点
    int pre_len = std::min((long long)seq_x.size(), n);
    for (int i = 0; i < pre_len; ++i) {
        long long current_x = seq_x[i];
        long long current_y = (i < seq_y.size()) ? seq_y[i] : seq_y[sy + (i - sy) % cy];
        global_min_y[current_x] = std::min(global_min_y[current_x], current_y);
        global_max_y[current_x] = std::max(global_max_y[current_x], current_y);
    }

    // 4. 如果 n 足够大，处理 "圈圈" 部分
    if (n > seq_x.size()) {
        // 4.1 预处理 y 循环的稀疏表
        for (int k = 0; k < cy; ++k) {
            st_min[0][k] = st_max[0][k] = seq_y[sy + k];
        }
        for (int j = 1; j < LOG_N; ++j) {
            for (int k = 0; k < cy; ++k) {
                long long next_k_idx = (k + (static_cast<int128>(1) << (j - 1)) * cx) % cy;
                st_min[j][k] = std::min(st_min[j - 1][k], st_min[j - 1][next_k_idx]);
                st_max[j][k] = std::max(st_max[j - 1][k], st_max[j - 1][next_k_idx]);
            }
        }

        // 4.2 对 x 循环中的每个点进行查询
        for (int i = sx; i < seq_x.size(); ++i) {
            if (i >= n) break;
            long long count = (n - 1 - i) / cx + 1;
            
            long long current_min = INF;
            long long current_max = -INF;
            long long y_start_idx_in_cycle = (i < seq_y.size()) ? (i - sy >= 0 ? (i - sy) % cy : (i - sy + cy) % cy) : (sy + (i - sy) % cy - sy) % cy;
            if(i < sy) y_start_idx_in_cycle = (i-sy) % cy; if(y_start_idx_in_cycle < 0) y_start_idx_in_cycle += cy;

            for (int j = LOG_N - 1; j >= 0; --j) {
                if ((count >> j) & 1) {
                    current_min = std::min(current_min, st_min[j][y_start_idx_in_cycle]);
                    current_max = std::max(current_max, st_max[j][y_start_idx_in_cycle]);
                    y_start_idx_in_cycle = (y_start_idx_in_cycle + (static_cast<int128>(1) << j) * cx) % cy;
                }
            }
            
            long long current_x = seq_x[i];
            global_min_y[current_x] = std::min(global_min_y[current_x], current_min);
            global_max_y[current_x] = std::max(global_max_y[current_x], current_max);
        }
    }

    // 5. 收集候选点并构建凸包
    std::vector<Point> candidates;
    for (int i = 0; i < px; ++i) {
        if (global_min_y[i] != INF) {
            candidates.push_back({(long long)i, global_min_y[i]});
            if (global_min_y[i] != global_max_y[i]) {
                candidates.push_back({(long long)i, global_max_y[i]});
            }
        }
    }
    
    // Andrew's Monotone Chain 算法
    std::sort(candidates.begin(), candidates.end(), [](Point a, Point b) {
        return a.x < b.x || (a.x == b.x && a.y < b.y);
    });

    std::vector<Point> hull;
    for (const auto& p : candidates) {
        while (hull.size() >= 2 && cross_product(hull[hull.size() - 2], hull.back(), p) <= 0) {
            hull.pop_back();
        }
        hull.push_back(p);
    }
    int lower_hull_size = hull.size();
    for (int i = candidates.size() - 2; i >= 0; --i) {
        const auto& p = candidates[i];
        while (hull.size() > lower_hull_size && cross_product(hull[hull.size() - 2], hull.back(), p) <= 0) {
            hull.pop_back();
        }
        hull.push_back(p);
    }
    hull.pop_back(); // 最后一个点和第一个点重复了

    // 6. 计算面积 (鞋带公式)
    int128 area = 0;
    if (hull.size() > 2) {
        for (size_t i = 0; i < hull.size(); ++i) {
            Point p1 = hull[i];
            Point p2 = hull[(i + 1) % hull.size()];
            area += static_cast<int128>(p1.x) * p2.y - static_cast<int128>(p2.x) * p1.y;
        }
    }
    
    long long final_area = area > 0 ? (long long)area : (long long)-area;
    std::cout << final_area << std::endl;

    return 0;
}

复杂度分析

时间复杂度: $O(p_x \log n + p_y \log n + P \log P)$ ，其中 $P$ 是候选点的数量，最大为 $2 \cdot p_x$ 。
- find_cycle: 找到两个序列的周期，最多遍历 $p_x+p_y$ 个元素，复杂度是 $O(p_x+p_y)$ 。
- 稀疏表预处理：需要 $O(c_y \log n)$ 的时间，因为我们需要 $O(\log n)$ 层，每层计算 $c_y$ 个状态。
- 查询：对 $x$ 循环中的每个点（最多 $c_x$ 个）进行一次 $O(\log n)$ 的查询。总共是 $O(c_x \log n)$ 。
- 凸包构建：对最多 $2 \cdot p_x$ 个候选点进行排序和构建，复杂度是 $O(p_x \log p_x)$ 。
- 综合起来，主要瓶颈在于稀疏表和凸包部分，总时间复杂度近似为 $O((p_x+p_y)\log n + p_x \log p_x)$ 。
空间复杂度: $O(p_x + p_y + c_y \log n)$ 。
- seq_x, seq_y 数组需要 $O(p_x+p_y)$ 的空间。
- global_min_y, global_max_y 需要 $O(p_x)$ 的空间。
- 稀疏表需要 $O(c_y \log n)$ 的空间。
- 候选点和凸包数组需要 $O(p_x)$ 的空间。

知识点总结

这真是一次酣畅淋漓的狩猎，喵！我们解决这道题用到了好几种强大的工具呢：

线性同余生成器（LCG）的周期性：这是发现问题突破口的关键。任何在有限域内的递推序列都是有周期的。
问题转化：将“求点集的凸包”转化为“求每个x坐标对应的y坐标极值点集的凸包”，大大减少了需要处理的点的数量。
倍增/稀疏表：用于高效地查询一个序列中等差索引子序列的区间最值。这是解决 $n$ 超大问题的核心技术。
Andrew's Monotone Chain 算法：一种高效构建凸包的经典算法。
鞋带公式：计算多边形面积的利器。

通过组合这些知识点，我们就能够优雅地解决这个看似非常棘手的问题啦！希望这篇题解能帮到你，继续加油哦，未来的大触！喵~

generator 3 - 题解 ​

标签与难度 ​

题目大意喵~ ​

解题思路分析 ​

第一步：发现周期的猫爪印 ​

第二步：聪明的猎手，简化问题 ​

第三步：雷霆一击，计算 Min/Max Y ​

第四步：收获战利品！求凸包与面积 ​

代码实现 ​

复杂度分析 ​

知识点总结 ​