PA 2019 Runda 3 Terytoria 题解

题目分析

这道题要求在一个二维环面（即左右边界连通、上下边界连通的地图）上，找到被所有矩形覆盖的格子的最大可能数量。

关键点：

• 地图是环面结构，需要考虑边界情况
• 矩形边平行于坐标轴
• 需要找到所有矩形的最大公共覆盖区域

解题思路

核心观察

1. 环面性质：由于地图是环面，矩形可以跨越边界
2. 最大公共交集：问题转化为找到所有矩形在环面上的最大公共交集
3. 随机化哈希：使用随机哈希来标识不同的覆盖区域

算法设计

代码采用了坐标离散化 + 随机哈希 + 树状数组的方法：

主要步骤：

1. 坐标离散化：将原始坐标映射到离散的索引
2. 随机哈希：为每个矩形分配随机哈希值
3. 差分更新：使用树状数组记录每个区间的哈希值
4. 统计最大区间：统计相同哈希值的区间长度总和，找到最大值

代码详解

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef __int128 i128;
typedef pair<int, int> pii;

const int N = 1e6 + 10;

int val1[N], val2[N], n, m1, m2;
struct P {
    int l, r;
} a[N], b[N];

struct Tree {
    int tot;
    ull tree[N];
    
    void change(int x, ull s) {
        while (x <= tot) {
            tree[x] ^= s;
            x += x & -x;
        }
    }
    
    ull ask(int x) {
        ull sum = 0;
        while (x) {
            sum ^= tree[x];
            x -= x & -x;
        }
        return sum;
    }
} tree1, tree2;

unordered_map<ull, int> mp;

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    cin >> n >> m1 >> m2;

    // 读入矩形坐标
    for (int i = 1; i <= n; i++)
        cin >> a[i].l >> b[i].l >> a[i].r >> b[i].r;

    // 坐标离散化 - 收集所有坐标值
    val1[++tree1.tot] = 0, val1[++tree1.tot] = m1;
    val2[++tree2.tot] = 0, val2[++tree2.tot] = m2;

    for (int i = 1; i <= n; i++) {
        val1[++tree1.tot] = a[i].l, val1[++tree1.tot] = a[i].r;
        val2[++tree2.tot] = b[i].l, val2[++tree2.tot] = b[i].r;
    }

    // 排序并去重
    sort(val1 + 1, val1 + tree1.tot + 1);
    sort(val2 + 1, val2 + tree2.tot + 1);
    tree1.tot = unique(val1 + 1, val1 + tree1.tot + 1) - val1 - 1;
    tree2.tot = unique(val2 + 1, val2 + tree2.tot + 1) - val2 - 1;

    // 将原始坐标映射到离散索引
    for (int i = 1; i <= n; i++) {
        a[i].l = lower_bound(val1 + 1, val1 + tree1.tot + 1, a[i].l) - val1;
        a[i].r = lower_bound(val1 + 1, val1 + tree1.tot + 1, a[i].r) - val1;
        b[i].l = lower_bound(val2 + 1, val2 + tree2.tot + 1, b[i].l) - val2;
        b[i].r = lower_bound(val2 + 1, val2 + tree2.tot + 1, b[i].r) - val2;
    }

    // 生成随机哈希值并更新树状数组
    srand(time(0));
    for (int i = 1; i <= n; i++) {
        ull s = 1ll * rand() * rand() * rand() * rand();  // 随机哈希值
        tree1.change(a[i].l, s);
        tree1.change(a[i].r, s);
        tree2.change(b[i].l, s);
        tree2.change(b[i].r, s);
    }

    // 统计x方向的最大公共区间
    int c1 = 0, c2 = 0;
    for (int i = 1; i < tree1.tot; i++)
        mp[tree1.ask(i)] += val1[i + 1] - val1[i];
    
    for (auto v : mp)
        c1 = max(c1, v.second);
    
    // 统计y方向的最大公共区间
    mp.clear();
    for (int i = 1; i < tree2.tot; i++)
        mp[tree2.ask(i)] += val2[i + 1] - val2[i];
    
    for (auto v : mp)
        c2 = max(c2, v.second);

    // 输出结果
    cout << 1ll * c1 * c2 << '\n';
    return 0;
}

算法原理

为什么这样是正确的？

1. 哈希值表示覆盖模式：

   • 每个矩形分配一个随机哈希值
   • 树状数组记录每个位置的累积哈希值
   • 相同哈希值的位置表示被相同的矩形集合覆盖

2. 差分更新：

   • 在矩形开始位置添加哈希值
   • 在矩形结束位置再次添加相同的哈希值（异或操作抵消）
   • 这样区间内的哈希值表示该区间被哪些矩形覆盖

3. 环面处理：

   • 算法天然支持环面结构，因为哈希值的计算不依赖于绝对位置
   • 跨越边界的矩形会被正确处理

关键技巧

1. 坐标离散化：将大范围坐标映射到小范围索引，减少空间复杂度
2. 随机哈希：使用随机数避免哈希冲突，保证正确性
3. 树状数组：高效支持区间更新和单点查询

样例分析

对于样例输入：

2 10 7
2 1 8 6
5 2 4 4

算法会：

1. 离散化x坐标和y坐标
2. 为两个矩形生成随机哈希值
3. 计算x方向和y方向的最大公共覆盖区间
4. 输出面积乘积 15

复杂度分析

• 时间复杂度：$O(n \log n)$，主要来自排序和树状数组操作
• 空间复杂度：$O(n)$，存储离散化后的坐标和树状数组

总结

这道题的解题亮点：

1. 巧妙的哈希设计：用随机哈希标识覆盖模式
2. 差分技巧：高效处理区间覆盖问题
3. 离散化优化：处理大坐标范围
4. 环面适应性：算法天然支持环面结构

这种"哈希+差分"的方法在解决多个区间的公共交集问题时非常有效，特别是在需要处理复杂空间结构的情况下。