题目重述

有 $100$ 个房间排成一排，房间 $i$ 与房间 $i+1$ 之间有一道门（共 $99$ 道门）。初始所有门都是未锁的（即可通行）。

已知：

• 爱丽丝在区间 $[l, r]$ 中的某个房间（$l < r$）；
• 鲍勃在区间 $[L, R]$ 中的某个房间（$L < R$）；
• 两人在不同的房间。

我们不知道具体位置，只能通过锁门来阻止他们互相到达（即他们之间至少有一道门是锁上的）。

问：最少需要锁多少道门，才能保证无论他们在各自区间内的哪个房间（只要不同），都无法互相到达？

---

第一步：转化为区间交集问题

如果两个区间有重叠，那么他们可能出现在重叠部分的不同房间。
如果两个区间不相交，那么他们之间隔着一些房间，但中间的门初始是开的，所以也能互相到达。

我们要阻止“任何可能的情况”下他们相遇，就要考虑最坏情况。

定义：

$$l_1 = l,\quad r_1 = r,\quad l_2 = L,\quad r_2 = R$$

---

第二步：最坏情况分析

考虑他们可能相遇的最近位置：

• 爱丽丝最靠右的位置是 $r_1$；
• 鲍勃最靠左的位置是 $l_2$。

如果他们之间没有锁门，那么当爱丽丝在 $r_1$，鲍勃在 $l_2$ 时，他们可以互相到达（如果 $r_1 < l_2$，中间门全开）。

同样，爱丽丝在最左 $l_1$，鲍勃在最右 $r_2$ 也是危险情况。

因此，我们必须锁上所有可能让“最近的两端”连通的门。

---

第三步：区间相交的情况

当两个区间有重叠时，设：

$$\text{start} = \max(l_1, l_2),\quad \text{end} = \min(r_1, r_2) $$

重叠区间为 $[\text{start}, \text{end}]$，长度为 $\text{end} - \text{start}$。

在重叠区间内部，任何两个相邻的房间都可能被两人分别占据（例如爱丽丝在 $i$，鲍勃在 $i+1$）。
因此，重叠区间的每一道门都必须锁上。
这些门位于房间 $\text{start}$ 与 $\text{start}+1$ 之间、……、房间 $\text{end}-1$ 与 $\text{end}$ 之间。

数量为：

$$\text{end} - \text{start}$$

---

第四步：边界额外锁门

考虑重叠区间的左边界 $\text{start}$。

• 如果 $l_1 \neq l_2$，意味着其中一个区间的左端点更靠左。
• 那么，爱丽丝可能位于 $l_1$，鲍勃位于 $\text{start}$（即另一个区间的左端）。
• 如果 $l_1 < l_2$，则房间 $l_2 - 1$ 与 $l_2$ 之间的门必须锁上，否则爱丽丝在 $l_2 - 1$（属于 $[l_1, r_1]$ 因为 $l_2 > l_1$）时能走到鲍勃在 $l_2$。
• 同理，如果 $l_1 > l_2$，对称情况。

因此，只要 $l_1 \neq l_2$，就需要额外锁 1 道门（重叠区左外侧的门）。

同理，考虑重叠区右边界 $\text{end}$。

• 如果 $r_1 \neq r_2$，也需要额外锁 1 道门（重叠区右外侧的门）。

---

第五步：区间不相交的情况

如果两个区间不相交，即 $\max(l_1, l_2) > \min(r_1, r_2)$。

例如 $[1,2]$ 与 $[4,5]$，中间隔着房间 $3$ 及其两边的门。
那么，爱丽丝最右是 $2$，鲍勃最左是 $4$，他们之间的门是 $(2,3)$ 和 $(3,4)$。
我们只需锁其中 1 道门（比如 $(3,4)$）即可阻止所有情况，因为无论他们具体在哪儿，都会经过这道门。

因此，不相交时答案 = $1$。

---

第六步：公式总结

设：

$$\text{start} = \max(l, L),\quad \text{end} = \min(r, R) $$

如果 $\text{start} \le \text{end}$（相交）：

$$\text{ans} = (\text{end} - \text{start}) + [l \neq L] + [r \neq R] $$

如果 $\text{start} > \text{end}$（不相交）：

$$\text{ans} = 1$$

其中 $[P]$ 是艾弗森括号，条件成立时为 $1$，否则 $0$。

---

第七步：验证样例

1. $[1,2]$ 与 $[3,4]$：$\text{start}=3$，$\text{end}=2$，不相交 $\Rightarrow$ $1$ ✅
2. $[2,5]$ 与 $[2,5]$：$\text{start}=2$，$\text{end}=5$，相交 $\Rightarrow$ $(5-2) + 0 + 0 = 3$ ✅
3. $[3,7]$ 与 $[6,7]$：$\text{start}=6$，$\text{end}=7$，相交 $\Rightarrow$ $(7-6) + 1 + 0 = 2$ ✅
4. $[4,5]$ 与 $[2,8]$：$\text{start}=4$，$\text{end}=5$，相交 $\Rightarrow$ $(5-4) + 1 + 1 = 3$ ✅

完全符合。

---

第八步：最终代码（标程）

#include <bits/stdc++.h>
using namespace std;

int main() {
    int t;
    cin >> t;
    while (t--) {
        int l, r, L, R;
        cin >> l >> r >> L >> R;
        
        int start = max(l, L);
        int end = min(r, R);
        
        int ans;
        if (start <= end) {
            ans = (end - start) + (l != L) + (r != R);
        } else {
            ans = 1;
        }
        
        cout << ans << "\n";
    }
    return 0;
}

---

复杂度分析

• 每个测试用例 $O(1)$ 时间。
• 总复杂度 $O(t)$，$t \le 10^4$，非常快。
• 空间复杂度 $O(1)$。

---

这样我们就完成了该题的详细题解。