Znzryb's Blog
0%

2025_ICPC_NERC_Northern_Eurasia_Finals——D. Doorway（扫描线的本质就是遍历一个出一个）（扫描线特别适合处理区间重合相关问题）

Posted on Edited on

题目大意

题目总结：D. Doorway

说白了就是告诉你滑动门两边的墙壁，告诉你从左到右的滑动门的这个长度。然后有好几层的这样子的子的滑动门系统问你这样子的系统能够张开的最大口子长度是多少。

问题描述

在一个多层滑动门系统中，共有 nn 层。每一层可以看作一个水平区间，由左侧墙壁 xi,1x_{i,1} 和右侧墙壁 xi,2x_{i,2} 限定。每一层包含若干扇固定长度的滑动门，门可以在该层的墙壁范围内自由左右滑动，但不能相互重叠，也不能越过墙壁。

目标

寻找一个最大的开口（Opening）。开口定义为一个水平区间，使得在所有层中，该区间内的任何位置都没有任何门或墙壁遮挡。你需要通过调整每一层门的位置，使得这个公共开口的长度最大化。

输入格式

  • 第一行：层数 nn (1≤n≤1051 \le n \le 10^5)。

  • 接下来的 nn 行，每行描述一层：

    • 三个整数：门数量 kik_i、左墙坐标 xi,1x_{i,1}、右墙坐标 xi,2x_{i,2} (0≤xi,1<xi,2≤1090 \le x_{i,1} < x_{i,2} \le 10^9)。
    • kik_i 个整数：该层从左到右每扇门的长度 li,jl_{i,j}。

  • 数据保证 ∑ki≤3⋅105\sum k_i \le 3 \cdot 10^5。

输出格式

  • 一个整数，表示通过移动门所能达到的最大公共开口长度。

样例解释

样例 1

  • 输入：

    • 第 1 层：墙在 [2,11][2, 11]，门长 3 和 2。
    • 第 2 层：墙在 [4,12][4, 12]，门长 1, 1 和 2。

  • 逻辑：
    所有层的共同墙壁限制区间为 [max⁡(xi,1),min⁡(xi,2)][\max(x_{i,1}), \min(x_{i,2})]，即 [4,11][4, 11]，长度为 7。

    • 在第 1 层中，如果将长为 3 的门推到最左，长为 2 的门推到最右，中间会留出空隙。
    • 在第 2 层中，通过合理分配门的位置，可以使得在 [4,11][4, 11] 这个范围内，所有层共同暴露出的最大空白区间长度为 4。

样例 2

  • 输入：

    • 第 1 层：墙在 [0,7][0, 7]，门长 2 和 4（总长 6，空隙 1）。
    • 第 2 层：墙在 [4,9][4, 9]，门长 4（总长 4，空隙 1）。

  • 逻辑：
    第一层有效范围 [0,7][0, 7]，第二层有效范围 [4,9][4, 9]，它们的交集是 [4,7][4, 7]，长度仅为 3。由于两层中都存在长度大于或等于交集长度的门或门组限制，无法在所有层中腾出一个完全没有遮挡的公共区间。

  • 输出： 0

注意

这个示例展示了第一个例子的解决方案。墙壁填充黑色，门填充各种灰色，开口是白色。当每层的第一个门向左移动，其余的门向右移动时，我们得到了最大的开口为4。

image

思路讲解

还是一样的思路啊，就是当你发现你只知道起始位置的时候，你会发现计算这个东西啊，其实不是很容易。

当然，我们上面所指的起始位置，其实是指的总体的起始位置。考虑到，虽然说总体的起始位置，知道总体的起始位置，然后我们去进行一个这个操作，它其实也是需要 O(N)O(N) 吧。

那我们曾经提及过非常多次，当我们发现采用总体的想法碰壁的时候，我们应该怎么样？我们应该采用更加细颗粒度的东西，是不是？因此我们可以采用每一个起始位置，就是每一个滑窗系统的起始位置，去解决以及考虑这个问题。


为什么这道题目你需要去塞一个负无穷呢？是这样子的，这个是因为啊，我们另外一道题目就是这个 brick work 是处理这个不相交问题，但这道题目我们处理的是相交问题。不相交问题你自然是还没有启用的区间，你自然是不用往里面去塞的。但是集合相交问题，还没有启用的集合，需要往里塞一个未启用值，就是未生效值。因为它都没启用，它肯定是不相交的对吧，为了避免这种情况影响我们的最终判断，我们需要往里面塞一个未启用值？

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
multiset<ll> ri_st;
// vector<Event> event_ls;
vector<ll> i_ri_ls(N + 2);
map<ll, vector<Event> > x1_idx_x2_mtx;
for (int i = 1; i <= N; ++i) {
    ll sum = accumulate(all(door_mtx[i]), 0ll);
    auto [x1,x2] = wall_pos[i];
    x2 -= sum;
    // 在没有碰到自己的左端点之前，这个滑动系统不应该贡献任何的这个有效的右端点。
    ri_st.insert(-INF);
    i_ri_ls[i] = -INF;
    x1_idx_x2_mtx[x1].push_back({i, x2});
    for (auto v: door_mtx[i]) {
        x1 += v;
        x2 += v;
        x1_idx_x2_mtx[x1].push_back({i, x2});
    }
}
ll ans = 0;
for (auto &[x1,vec]: x1_idx_x2_mtx) {
    for (auto &[id,x2]: vec) {
        ri_st.erase(ri_st.find(i_ri_ls[id]));
        ri_st.insert(x2);
        i_ri_ls[id] = x2;
    }
    ans = max(ans, *ri_st.begin() - x1);
}

AC代码

AC
https://codeforces.com/contest/2181/submission/362349671

心路历程（WA，TLE，MLE……）

1
2
3
4
5
6
7
8
9
10
11
12
13
14
for (int i = 1; i <= N; ++i) {
    ll sum = accumulate(all(door_mtx[i]), 0ll);
    auto [x1,x2] = wall_pos[i];
    x2 -= sum;
    // 在没有碰到自己的左端点之前，这个滑动系统不应该贡献任何的这个有效的右端点。
    ri_st.insert(-INF);
    i_ri_ls[i] = -INF;
    x1_idx_x2_mtx[x1].push_back({i, x2});
    for (auto v: door_mtx[i]) {
        x1 += v;
        x2 += v;
        x1_idx_x2_mtx[x1].push_back({i, x2});
    }
}