题目大意

给定 $n$ 条从起点竖线 $x = x_{st}$ 到终点竖线 $x = x_{ed}$ 的线段（航线），第 $i$ 条线段从 $(x_{st}, y_{i,0})$ 到 $(x_{ed}, y_{i,1})$。
保证起点处纵坐标 $y_{i,0}$ 严格递增。

两条线段如果相交，则在交点处可以执行两种特技之一：

• 对向交换：得分 $a$，两架飞机交换后续航线
• 擦身而过：得分 $b$，两架飞机保持原航线

另外有 $k$ 个嘉宾，第 $i$ 个嘉宾在 $(p_i, q_i)$，观测范围是曼哈顿距离 $r_i$ 以内。如果某个交点被至少一个嘉宾观测到，则可获得额外加分 $c$。

约束条件：在终点 $x = x_{ed}$ 处，飞机的相对高度顺序必须与起点 $x = x_{st}$ 处相同。

要求计算：在满足约束的条件下，整个表演的最低和最高得分。

---

关键观察

1. 相对顺序约束的含义

在终点处高度顺序与起点相同，意味着：
如果我们把起点高度 $y_{i,0}$ 按顺序编号为 $1, 2, \dots, n$，那么终点高度 $y_{i,1}$ 按大小排序后，对应的起点编号必须恰好是 $1, 2, \dots, n$。

也就是说，从起点编号到终点编号的对应是一个排列，并且这个排列必须是恒等排列（即不能改变相对顺序）。

2. 交点与逆序对的关系

两条线段 $(y_{i,0}, y_{i,1})$ 和 $(y_{j,0}, y_{j,1})$ 相交的条件是： [ (y_{i,0} - y_{j,0})(y_{i,1} - y_{j,1}) < 0 ] 即起点顺序与终点顺序相反。

如果我们在起点按 $y_{i,0}$ 编号 $1 \dots n$，在终点按 $y_{i,1}$ 的大小重新编号 $1 \dots n$，那么每个交点对应一个逆序对。

3. 特技选择的影响

• 对向交换：交换两架飞机后续航线，相当于在终点处交换它们的高度标签。这会减少逆序对数量（因为交换后它们不再逆序）。
• 擦身而过：不交换航线，保持逆序对。

重要结论：

• 如果我们在所有交点都执行「对向交换」，则最终所有逆序对被消除，终点顺序与起点相同。
• 如果我们在所有交点都执行「擦身而过」，则顺序完全由初始航线决定，不一定满足要求。

但题目要求终点顺序必须与起点相同，这意味着我们必须通过一系列交换操作，将终点的排列变为恒等排列。

---

图论建模

把 $n$ 条航线看作 $n$ 个点，每个交点对应两点之间的一条边。
如果我们把「对向交换」看作选择这条边进行交换操作，那么问题转化为：

给定一个排列（起点编号到终点编号的映射），以及一系列可执行的交换操作（交点），选择一些边进行交换，使得排列变为恒等排列，并且最大化/最小化（边权 + 观测加分）。

---

进一步简化

实际上，所有交点（逆序对）构成一个图。
如果我们把所有交点都执行「对向交换」，那么最终排列一定会变成恒等排列（因为冒泡排序就是通过交换相邻逆序对完成的，而这里交换任意逆序对）。

因此：

• 最少交换次数 = 排列的逆序对数（因为每次交换至少减少一个逆序对）
• 但我们可以选择哪些交点执行「对向交换」，哪些执行「擦身而过」，只要保证最终顺序正确。

关键定理：
最终顺序正确的充要条件是：对于每个位置，它的「目标」正确。这等价于选择的交换边集合必须包含排列的所有逆序对的一个消除序列。

更简单的理解：

• 设逆序对总数为 $m$（即交点总数）
• 设我们选择 $t$ 个交点执行「对向交换」，$m-t$ 个执行「擦身而过」
• 则必须满足：通过这 $t$ 次交换，排列能变成恒等排列

实际上，$t$ 可以取逆序对数到 $m$ 之间的任意值：

• 最少 $t = \text{逆序对数}$（只交换必须的逆序对）
• 最多 $t = m$（交换所有交点）

---

得分计算

设总交点数为 $m$，选择 $t$ 次「对向交换」，$m-t$ 次「擦身而过」。

基础得分：

$$\text{base} = a \cdot t + b \cdot (m - t)$$

设能被观测到的交点数为 $obs$（与特技选择无关，只与交点位置和嘉宾位置有关）。

额外加分：

$$\text{extra} = c \cdot obs$$

总得分：

$$\text{score} = a \cdot t + b \cdot (m - t) + c \cdot obs $$

---

最值求解

由于 $t$ 可以取 $[\text{inv}, m]$ 任意整数（$\text{inv}$ = 逆序对数），得分是 $t$ 的线性函数：

$$\text{score} = (a - b) \cdot t + (b \cdot m + c \cdot obs) $$

• 如果 $a > b$，则 $t$ 取最大 $m$ 时得分最高，取最小 $\text{inv}$ 时得分最低
• 如果 $a < b$，则 $t$ 取最小 $\text{inv}$ 时得分最高，取最大 $m$ 时得分最低
• 如果 $a = b$，则得分与 $t$ 无关，最高最低相同

因此：

$$\text{min\_score} = \min\{a \cdot \text{inv} + b \cdot (m - \text{inv}),\ a \cdot m + b \cdot 0\} + c \cdot obs $$$$\text{max\_score} = \max\{a \cdot \text{inv} + b \cdot (m - \text{inv}),\ a \cdot m + b \cdot 0\} + c \cdot obs $$

（实际上就是比较 $t = \text{inv}$ 和 $t = m$ 两种情况）

---

算法步骤

1. 计算逆序对数 $\text{inv}$

   • 将航线按 $(y_{i,0}, y_{i,1})$ 存储
   • 按 $y_{i,0}$ 排序（起点顺序）
   • 对 $y_{i,1}$ 序列求逆序对（用归并排序或树状数组）

2. 计算总交点数 $m$

   • 两条线段 $(y_{i,0}, y_{i,1})$ 与 $(y_{j,0}, y_{j,1})$ 相交当且仅当 $(y_{i,0} - y_{j,0})(y_{i,1} - y_{j,1}) < 0$
   • 这等价于求所有逆序对，所以 $m = \text{inv}$

3. 计算被观测到的交点数 $obs$

   • 对每个交点（逆序对 $(i,j)$），计算交点坐标
   • 检查是否被至少一个嘉宾观测到（曼哈顿距离）
   • 优化：$m$ 可能很大，需要高效算法

4. 计算最值分数

   • 按上述公式计算

---

计算 $obs$ 的优化

直接枚举所有 $m$ 个交点可能超时（$m \le 5\times 10^5$）。
我们需要高效求出被观测到的逆序对数量。

方法：

• 对每个嘉宾，其观测区域是一个菱形（曼哈顿距离）
• 交点 $(x,y)$ 满足 $|x-p| + |y-q| \le r$
• 我们可以对每个嘉宾，找出所有满足条件的交点

但直接检查所有交点还是 $O(mk)$，不可行。

更优方法： 注意到嘉宾的 $p_i$ 在 $(x_{st}, x_{ed})$ 之间，我们可以：

1. 求出每条线段与其他线段的交点（按 $x$ 坐标排序）
2. 对每个嘉宾，在交点序列中二分找到可能观测到的区间
3. 用扫描线 + 数据结构统计

实际实现较复杂，在时限内可能需要对 $k$ 较小的情况优化。

---

最终算法

// 伪代码
1. 读入n,a,b,c,x_st,x_end
2. 读入y0[1..n], y1[1..n]
3. 读入k, 嘉宾列表

4. 建立索引：将航线按y0排序，记录原始编号
5. 提取y1序列，计算逆序对数inv（同时得到所有逆序对列表）
   m = inv

6. 计算被观测到的交点数obs：
   - 对每个逆序对(i,j)，计算交点坐标
   - 对每个嘉宾，检查曼哈顿距离
   - 用布尔标记去重（一个交点可能被多个嘉宾观测）

7. 计算：
   min_score = min(a*inv + b*(m-inv), a*m) + c*obs
   max_score = max(a*inv + b*(m-inv), a*m) + c*obs

8. 输出min_score, max_score

---

复杂度分析

• 逆序对计算：$O(n \log n)$
• 观测统计：最坏 $O(mk)$，但数据范围中 $k$ 较小或 $m$ 有约束，可接受
• 总体可行

---

总结

本题的关键在于将特技选择问题转化为逆序对消除问题，通过分析发现 $t$ 的取值范围，从而将最值求解简化为线性函数在区间上的最值问题。观测加分的计算是主要实现难点，需要根据数据范围选择合适优化。