7429. 直线与询问 II (Lines and Queries II)
时间限制：1000 MS 内存限制：512 MB
题目描述
# 直线与询问 II (Lines and Queries II) 时间限制：$1.00\text{ s}$ 空间限制：$512\text{ MB}$ ## 题目描述 您的任务是高效地处理以下两类操作： 1. 添加一条形如 $y = ax + b$ 的直线，该直线仅在区间 $[l, r]$ 内有效。 2. 查询在给定的横坐标 $x$ 处，当前所有在该位置有效的直线中对应的最大 $y$ 值。 ## 输入格式 第一行包含一个整数 $n$：操作的数量。 接下来的 $n$ 行描述这些操作。每行的格式为 `1 a b l r`（表示添加一条在 $[l, r]$ 区间有效的直线 $y = ax+b$）或 `2 x`（表示查询横坐标为 $x$ 处的最大值）。 ## 输出格式 对于每个类型 $2$ 的查询，输出对应的最大 $y$ 值。如果在该横坐标处当前没有任何直线有效，输出 `NO`。 ## 输入输出样例 ### 输入 #1 ```text 6 1 1 2 1 3 2 3 2 4 1 0 4 1 5 2 3 2 4 ``` ### 输出 #1 ```text 5 NO 5 4 ``` ## 说明/提示 ### 数据规模与约定 - $1 \le n \le 2 \cdot 10^5$ - $-10^9 \le a, b \le 10^9$ - $0 \le x \le 10^5$ - $0 \le l \le r \le 10^5$