2025_ICPC_NERC_Northern_Eurasia_Finals——D. Doorway（扫描线的本质就是遍历一个出一个）（扫描线特别适合处理区间重合相关问题） · znzryb
## 题目大意
## 题目总结：D. Doorway
说白了就是告诉你**滑动门两边的墙壁**，告诉你**从左到右的滑动门的这个长度**。然后有**好几层的**这样子的子的**滑动门系统**问你这样子的系统**能够张开的最大口子长度**是多少。
**问题描述**
在一个多层滑动门系统中，共有 $n$ 层。每一层可以看作一个水平区间，由左侧墙壁 $x_{i,1}$ 和右侧墙壁 $x_{i,2}$ 限定。每一层包含若干扇固定长度的滑动门，门可以在该层的墙壁范围内自由左右滑动，但不能相互重叠，也不能越过墙壁。
**目标**
寻找一个最大的**开口（Opening）**。开口定义为一个水平区间，使得在所有层中，该区间内的任何位置都没有任何门或墙壁遮挡。你需要通过调整每一层门的位置，使得这个公共开口的长度最大化。
---
**输入格式**
- 第一行：层数 $n$ ($1 \le n \le 10^5$)。
- 接下来的 $n$ 行，每行描述一层：
- 三个整数：门数量 $k_i$、左墙坐标 $x_{i,1}$、右墙坐标 $x_{i,2}$ ($0 \le x_{i,1} < x_{i,2} \le 10^9$)。
- $k_i$ 个整数：该层从左到右每扇门的长度 $l_{i,j}$。
- 数据保证 $\sum k_i \le 3 \cdot 10^5$。
**输出格式**
- 一个整数，表示通过移动门所能达到的最大公共开口长度。
---
**样例解释**
**样例 1**
- **输入：**
- 第 1 层：墙在 $[2, 11]$，门长 3 和 2。
- 第 2 层：墙在 $[4, 12]$，门长 1, 1 和 2。
- **逻辑：**
所有层的共同墙壁限制区间为 $[\max(x_{i,1}), \min(x_{i,2})]$，即 $[4, 11]$，长度为 7。
- 在第 1 层中，如果将长为 3 的门推到最左，长为 2 的门推到最右，中间会留出空隙。
- 在第 2 层中，通过合理分配门的位置，可以使得在 $[4, 11]$ 这个范围内，所有层共同暴露出的最大空白区间长度为 **4**。
**样例 2**
- **输入：**
- 第 1 层：墙在 $[0, 7]$，门长 2 和 4（总长 6，空隙 1）。
- 第 2 层：墙在 $[4, 9]$，门长 4（总长 4，空隙 1）。
- **逻辑：**
第一层有效范围 $[0, 7]$，第二层有效范围 $[4, 9]$，它们的交集是 $[4, 7]$，长度仅为 3。由于两层中都存在长度大于或等于交集长度的门或门组限制，无法在所有层中腾出一个完全没有遮挡的公共区间。
- **输出：** **0**
**注意**
这个示例展示了第一个例子的解决方案。墙壁填充黑色，门填充各种灰色，开口是白色。当每层的第一个门向左移动，其余的门向右移动时，我们得到了最大的开口为4。
_403dc475.png)
## 思路讲解
还是一样的思路啊，就是当你发现你只知道起始位置的时候，你会发现计算这个东西啊，其实不是很容易。
当然，我们上面所指的起始位置，其实是指的**总体的起始位置**。考虑到，虽然说总体的起始位置，知道总体的起始位置，然后我们去进行一个这个操作，它其实也是需要 $O(N)$ 吧。
那我们曾经提及过非常多次，当我们发现**采用总体的想法碰壁**的时候，我们应该怎么样？我们应该**采用更加细颗粒度的东西**，是不是？因此我们可以采用每一个起始位置，就是***每一个滑窗系统的起始位置***，去解决以及考虑这个问题。
::: AI 的模拟
这道题维护的是：**每层的"gap 右端点"，一共** $N$ **个值**。
具体来说，multiset 里始终有 $N$ 个数，第 $i$ 层占一个位置，表示"在当前扫描位置下，第 $i$ 层的空隙最远能延伸到哪里"。
我画一下扫描过程，用样例来说明。
## 样例模拟
```
2
2 2 11 3 2
3 4 12 1 1 2
```
层 1：$x_1=2$，$x_2=11$，门 $=[3,2]$，$w=4$。gap-start 候选：$2, 5, 7$，对应 rightend：$6, 9, 11$。
层 2：$x_1=4$，$x_2=12$，门 $=[1,1,2]$，$w=4$。gap-start 候选：$4, 5, 6, 8$，对应 rightend：$8, 9, 10, 12$。
所有事件排序：
| 扫到 $g$ | 属于哪层 | 新 rightend | multiset 状态 | $\min - g$ |
| --- | --- | --- | --- | --- |
| $2$ | 层1 | $6$ | $\{6, -\infty\}$ | 层2还没激活 |
| $4$ | 层2 | $8$ | $\{6, 8\}$ | $6-4=2$ |
| $5$ | 层1 | $9$ | $\{9, 8\}$ | $8-5=3$ |
| $5$ | 层2 | $9$ | $\{9, 9\}$ | $9-5=\mathbf{4}$ |
| $6$ | 层2 | $10$ | $\{9, 10\}$ | $9-6=3$ |
| $7$ | 层1 | $11$ | $\{11, 10\}$ | $10-7=3$ |
| $8$ | 层2 | $12$ | $\{11, 12\}$ | $11-8=3$ |
答案 = $4$，在 $g=5$ 时取到。
**multiset 里的含义**：在扫描位置 $g=5$ 时，层 1 的空隙最远能到 $9$，层 2 的空隙最远能到 $9$。取最小值 $9$，opening = $9 - 5 = 4$。
所以维护的东西就是这 $N$ 个"每层能延伸到多远"的值，用 multiset 随时拿最小值。
:::
[2025 United Kingdom and Ireland Programming Contest (UKIEPC 2025) 2025 英国 ICPC——B. Brickwork（判断砖块是否重叠）（扫描线的本质就是遍历一个出一个）（维护一个当前生效的集合）](/2026/02/06/20260206-95397573)
为什么这道题目你需要**去塞一个负无穷**呢？是这样子的，这个是因为啊，我们另外一道题目就是这个 brick work 是处理***这个不相交问题***，但这道题目我们处理的是相交问题。不相交问题你自然是还没有启用的区间，你自然是不用往里面去塞的。但是**集合相交问题**，还没有启用的集合，**需要往里塞一个未启用值**，就是未生效值。因为它都没启用，它肯定是不相交的对吧，为了避免这种情况影响我们的最终判断，我们需要往里面塞一个未启用值？
```cpp
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](https://codeforces.com/contest/2181/submission/362349671)
::: 源代码
```cpp
/**
* Problem: D. Doorway
* Contest: 2025
* Judge: Codeforces
* URL: https://codeforces.com/contest/2181/problem/D
* Created: 2026-02-11 00:56:58
* Author: Gospel_rock
*
* Powered by AutoCp https://github.com/Pushpavel/AutoCp
*/
#include <bits/stdc++.h>
#define all(vec) vec.begin(),vec.end()
#define lson(o) (o<<1)
#define rson(o) (o<<1|1)
#define SZ(a) ((long long) a.size())
#define debug(var) cerr << #var <<" = ["<<var<<"]"<<"\n";
#include <iostream>
#define debug1d(a) do { \
std::cerr << #a << " = ["; \
bool first = true; \
for (const auto &x : a) { \
if (!first) std::cerr << ", "; \
std::cerr << x; \
first = false; \
} \
std::cerr << "]\n"; \
} while (0)
#define debug2d(a) do { \
std::cerr << #a << " = [\n"; \
for (const auto &row : a) { \
std::cerr << " ["; \
bool first = true; \
for (const auto &x : row) { \
if (!first) std::cerr << ", "; \
std::cerr << x; \
first = false; \
} \
std::cerr << "]\n"; \
} \
std::cerr << "]\n"; \
} while (0)
#define debug3d(a) do { \
std::cerr << #a << " = [\n"; \
for (const auto &mat : a) { \
std::cerr << " [\n"; \
for (const auto &row : mat) { \
std::cerr << " ["; \
bool first = true; \
for (const auto &x : row) { \
if (!first) std::cerr << ", "; \
std::cerr << x; \
first = false; \
} \
std::cerr << "]\n"; \
} \
std::cerr << " ]\n"; \
} \
std::cerr << "]\n"; \
} while (0)
#define cend cerr<<"\n-----------\n"
#define fsp(x) fixed<<setprecision(x)
using namespace std;
using ll = long long;
using ull = unsigned long long;
using DB = double;
// using i128 = __int128;
using CD = complex<double>;
static constexpr ll MAXN = (ll) 1e6 + 10, INF = (1ll << 61) - 1;
static constexpr ll mod = 998244353; // (ll)1e9+7;
static constexpr double eps = 1e-8;
const double pi = acos(-1.0);
ll lT, testcase;
/*
*
*/
struct Wall_pos {
ll x1, x2;
};
struct Event {
ll idx/*,x1*/, x2;
// bool operator<(const Event &o) const {
// if (x1!=o.x1) return x1<o.x1;
// return idx<o.idx;
// }
};
void Solve() {
ll N;
cin >> N;
vector<vector<ll> > door_mtx(N + 2);
vector<Wall_pos> wall_pos(N + 2);
ll mxx1 = 0, mnx2 = INF;
for (int i = 1; i <= N; ++i) {
ll K, x1, x2;
cin >> K >> x1 >> x2;
wall_pos[i] = {x1, x2};
mxx1 = max(mxx1, x1);
mnx2 = min(mnx2, x2);
door_mtx[i].resize(K);
for (auto &v: door_mtx[i]) {
cin >> v;
}
}
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);
}
// #ifdef LOCAL
// debug2d(x1_idx_x2_mtx);
// #endif
cout << ans << "\n";
}
signed main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
cout.tie(nullptr);
#ifdef LOCAL
cout.setf(ios::unitbuf); // 无缓冲流，方便我们调试
#endif
// cin >> lT;
// for (testcase=1;testcase<=lT;++testcase)
Solve();
return 0;
}
/*
AC
https://codeforces.com/contest/2181/submission/362349671
*/
```
:::
## 心路历程（WA，TLE，MLE……）
::: AI 提示
好，我来认真讲一下这道 Doorway 的扫描线，以及和 Brickwork 的对比。
## Doorway 扫描线的精妙之处
这道题的扫描线，最精妙的地方有**三层递进**：
### 第一层：观察到 gap 宽度是定值
每层的门总长是固定的，墙的区间也是固定的，所以**每层的空隙宽度** $w_i = x_2 - x_1 - \sum l_j$ **是一个常数**。不管你怎么滑动门，空隙的大小不变，变的只是空隙的位置。
这意味着原问题从"怎么安排门"变成了"从每层选一个空隙位置，使得所有层的空隙的**交集最大**"。
### 第二层：最优 st 必在 gap-start 处（这个说白了傻子都知道，所谓的**gap start就是每层都有K种选择**，纯纯是傻逼。）
opening 的左端点 st 如果确定了，那每层的最优策略就是：把空隙尽量往右推（把尽可能多的门放到 st 左边），这样右端点 $\text{rightend}_i(\text{st})$ 最大。
关键性质：**在两个相邻的 gap-start 之间，所有层的 rightend 都不变，但 st 在递增**，所以 $\min(\text{rightend}_i) - \text{st}$ 严格递减。
结论：**最优 st 必然是某层的某个 gap-start 位置**。候选点总共就 $\sum(k_i + 1)$ 个。
### 第三层：扫描线 + multiset 做到 O(sum_k * log n)
如果对每个候选 st 暴力算所有层的 rightend，复杂度是 $O(\sum k_i \times n)$，太慢。
精妙之处：**把所有候选 st 排序后从左到右扫描，每次只有一层的 rightend 发生变化**（就是当前 gap-start 所属的那一层）。用 multiset 维护所有层的 rightend，$O(\log n)$ 就能查到全局最小值。
这和 Brickwork 里的扫描线"每次只有一个矩形进入/离开 activates 集合"是同一个道理。
## 和 Brickwork 的对比
| | Brickwork（砖墙） | Doorway（门） |
| --- | --- | --- |
| **消除的维度** | 扫描 x 坐标，把 2D 矩形重叠问题变成 1D 区间重叠问题 | 扫描 gap-start 位置，把"多层选位置求交集最大"变成"逐步更新单层 rightend" |
| **事件类型** | 矩形左边进入（op=1）、右边离开（op=0） | gap-start 出现（更新该层的 rightend） |
| **维护的集合** | `set<pair<ll,ll>>` 维护当前所有**激活的 y 区间**，保证互不重叠 | `multiset<ll>` 维护每层当前的 **rightend**，追踪全局最小值 |
| **每次事件的操作** | 插入时检查前驱/后继是否重叠；删除时直接 erase | 更新一层的 rightend（erase 旧值 + insert 新值），查 `*begin()` |
| **核心不变量** | activates 中所有区间互不重叠 | multiset 中恰好 N 个值，每层一个 |
| **判定条件** | 每次插入都不和邻居重叠 → yes | `*begin() - g` 的最大值就是答案 |
### 相同点
1. **都是把高维问题降到一维**：Brickwork 把 2D 重叠检测降到 1D 区间检测；Doorway 把"多层 gap 位置选择"降到一维扫描。
1. **每次事件只影响一个元素**：Brickwork 每次只有一个区间进/出；Doorway 每次只有一层的 rightend 变化。这是扫描线高效的根本原因。
1. **都依赖有序集合**：利用 `set`/`multiset` 的 $O(\log n)$ 操作来维护全局信息。
### 不同点
1. **目标不同**：Brickwork 是判定问题（有没有重叠）；Doorway 是最优化问题（最大 opening）。
1. **集合语义不同**：Brickwork 的 `activates` 存的是**当前活跃的区间**，需要保证互不重叠，所以只需查前驱后继；Doorway 的 multiset 存的是**每层一个标量值**（rightend），需要的是全局最小值，所以用 `begin()`。
1. **事件的对称性**：Brickwork 有"进入"和"离开"两种事件，是对称的；Doorway 只有一种事件（gap-start），每层的 rightend 只增不减，没有"离开"。
:::
::: 错误的代码（然后采用类似于懒更新的策略。但是呢，要记住一件事情啊，\*\*懒更新\*\*，你不能把更加优秀的东西塞入\*\*这个你的集合里面\*\*）
```cpp
/**
* Problem: D. Doorway
* Contest: 2025
* Judge: Codeforces
* URL: https://codeforces.com/contest/2181/problem/D
* Created: 2026-02-10 17:09:28
* Author: Gospel_rock
*
* Powered by AutoCp https://github.com/Pushpavel/AutoCp
*/
#include <bits/stdc++.h>
#define all(vec) vec.begin(),vec.end()
#define lson(o) (o<<1)
#define rson(o) (o<<1|1)
#define SZ(a) ((long long) a.size())
#define debug(var) cerr << #var <<" = ["<<var<<"]"<<"\n";
#define debug1d(a) \
cerr << #a << " = ["; \
for (int i = 0; i < (int)(a).size(); i++) \
cerr << (i ? ", " : "") << a[i]; \
cerr << "]\n";
#define debug2d(a) \
cerr << #a << " = [\n"; \
for (int i = 0; i < (int)(a).size(); i++) \
{ \
cerr << " ["; \
for (int j = 0; j < (int)(a[i]).size(); j++) \
cerr << (j ? ", " : "") << a[i][j]; \
cerr << "]\n"; \
} \
cerr << "]\n";
#define debug3d(a) \
cerr << #a << " = [\n"; \
for (int i = 0; i < (int)(a).size(); i++) \
{ \
cerr << " [\n"; \
for (int j = 0; j < (int)(a[i]).size(); j++) \
{ \
cerr << " ["; \
for (int k = 0; k < (int)(a[i][j]).size(); k++) \
cerr << (k ? ", " : "") << a[i][j][k]; \
cerr << "]\n"; \
} \
cerr << " ]\n"; \
} \
cerr << "]\n";
#define cend cerr<<"\n-----------\n"
#define fsp(x) fixed<<setprecision(x)
using namespace std;
using ll = long long;
using ull = unsigned long long;
using DB = double;
// using i128 = __int128;
using CD = complex<double>;
static constexpr ll MAXN = (ll)1e6+10, INF = (1ll<<61)-1;
static constexpr ll mod = 998244353; // (ll)1e9+7;
static constexpr double eps = 1e-8;
const double pi = acos(-1.0);
ll lT,testcase;
/*
*
*/
struct Wall_pos {
ll x1,x2;
};
// struct Event {
// ll st,ed;
// // 这里要使用 Auto 的自动推导类型。
// auto operator<=>(const Event&) const = default;
// };
void Solve() {
ll N;
cin >> N;
vector<vector<ll>> door_mtx(N+2);
vector<Wall_pos> wall_pos(N+2);
ll mxx1=0,mnx2=INF;
for (int i=1;i<=N;++i) {
ll K,x1,x2;
cin>>K>>x1>>x2;
wall_pos[i]={x1,x2};
mxx1=max(mxx1,x1);
mnx2=min(mnx2,x2);
door_mtx[i].resize(K);
for (auto &v:door_mtx[i]) {
cin>>v;
}
}
// vector<Event> event_ls;
map<ll,vector<ll>> event_mtx;
multiset<ll> ed_st;
for (int i=1;i<=N;++i) {
// vector<ll> suf_sum(SZ(door_mtx[i]));
// partial_sum(door_mtx[i].rbegin(),door_mtx[i].rend(),suf_sum.rbegin());
// suf_sum.push_back(0);
ll sum=accumulate(all(door_mtx[i]),0ll);
auto [x1,x2]=wall_pos[i];
// event_ls.push_back({x1,x2-sum});
event_mtx[x1].push_back(x2-sum);
ed_st.insert(x2-sum);
ed_st.insert(x2);
x2-=sum;
for (auto v:door_mtx[i]) {
x1+=v;
x2+=v;
// event_ls.push_back({x1,x2});
event_mtx[x1].push_back(x2);
ed_st.insert(x2);
}
}
ll ans=0;
for (auto it=event_mtx.begin();it!=event_mtx.end();++it) {
for (auto ed:it->second) {
auto it_erase=ed_st.find(ed);
if (it_erase!=ed_st.end()) {
ed_st.erase(it_erase);
}
}
if (it->first<mxx1) {
continue;
}
auto nex_it=next(it);
if (nex_it==event_mtx.end()) {
continue;
}
ll lans=*ed_st.begin()-(nex_it->first);
ans=max(ans,lans);
}
cout<<ans<<"\n";
}
signed main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
cout.tie(nullptr);
#ifdef LOCAL
cout.setf(ios::unitbuf); // 无缓冲流，方便我们调试
#endif
// cin >> lT;
// for (testcase=1;testcase<=lT;++testcase)
Solve();
return 0;
}
/*
*/
```
:::
```cpp
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});
}
}
```