题目描述

Farmer John 的奶牛们认为人类做得并不好，于是决定自己创办一家航空公司。它们的目标客户是居住在密歇根湖西岸的奶牛。每天早晨，飞机从最北端的农场向南飞往 Chicowgo，沿途停靠多个站点；傍晚则从南端飞回北端。

你需要帮助它们决定每天运送的乘客。海岸线上有编号为 1 到 N（1 ≤ N ≤ 10,000）的农场（1 为最北端，N 为最南端）。当天共有 K（1 ≤ K ≤ 50,000）组奶牛希望旅行，每组奶牛从起点农场 S 到终点农场 E（S ≠ E）。飞机容量为 C（1 ≤ C ≤ 100）。部分搭载是允许的，但一旦登机，奶牛必须到达目的地才能下机。

求在满足容量限制的前提下，早晚航班最多能运送的奶牛总数。

输入格式

• 第 1 行：三个整数 K, N, C
• 第 2 至 K+1 行：每组旅行的三个整数 S, E, M（M 为该组奶牛数量）

输出格式

• 第 1 行：早晚航班运送的奶牛总数最大值

输入样例

4 8 3
1 3 2
2 8 3
4 7 1
8 3 2

输出样例

6

提示

• 输入解释：4 组奶牛，8 个农场，飞机容量为 3。
• 输出解释：早晨运送 2（1→3） + 1（2→8） + 1（4→7），傍晚运送 2（8→3），总计 6。

题解思路

将问题分为南向（早晨）和北向（傍晚）两个独立部分处理：

1. 南向航班（S < E）：

   • 将每组请求的区间视为 [S, E)，按终点升序排序。
   • 使用线段树维护区间最大值，贪心分配座位。

2. 北向航班（S > E）：

   • 将每组请求的区间视为 [E, S)，按终点升序排序。
   • 同样使用线段树维护区间最大值，贪心分配座位。

线段树操作：

• 区间最大值查询：确定当前区间的最大占用座位数。
• 区间加法更新：分配座位后更新区间占用。

最终结果为南向与北向运送量之和。

关键点：按终点排序确保后续请求不影响已处理请求的座位分配，线段树高效维护区间操作。