[EGOI2021] Lanterns / 灯笼
题目背景
Day 1 Problem D.
题面译自 [EGOI2021 lantern](https://stats.egoi.org/media/task_description/2021_lantern_en.pdf)。
题目描述
农夫约翰带着他的奶牛群在阿尔卑斯山进行了一次徒步旅行!一段时间后,天色转暗,旅行结束了。然而,一些奶牛仍然被困在山脉的各个地方,现在约翰需要营救它们!
现在牛群正在穿越的山脉用平面直角坐标系中的 $n$ 个点表示。我们称这些点为“山峰”。山峰被依次编号为 $1\sim n$。第 $i$ 座山峰的坐标为 $(i,h_i)$。值 $h_i$ 代表第 $i$ 座山峰的**海拔高度**。保证 $h_1,h_2,\ldots h_n$ 构成一个 $1\sim n$ 的排列。
山峰 $i$ 和山峰 $i+1$ 用一条线段相连。
由于现在是晚上,约翰必须携带至少一盏正常工作的灯笼才能上山。幸运的是,有 $k$ 个灯笼可供购买。第 $j$ 个灯笼可以在山峰 $p_j$ 以 $c_j$ 法郎的价格购买。
不幸的是,第 $j$ 个灯笼只有在约翰的海拔在 $[a_j,b_j]$ 时才能正常工作。换句话说,如果约翰的海拔严格低于 $a_j$ 或严格高于 $b_j$,第 $j$ 个灯笼不会正常工作。需要注意的是,灯笼在离开海拔范围时不会损坏。例如,当约翰的海拔超过 $b_j$ 时,第 $j$ 个灯笼会停止工作,但只要约翰返回到海拔 $b_j$,灯笼会重新开始工作。
如果约翰现在在山峰 $p$,他可以执行以下三种操作之一:
- 他可以买一个在 $p$ 处售卖的灯笼。购买灯笼后,他可以永久使用。
- 如果 $p > 1$,他可以走到山峰 $p-1$。
- 如果 $p < n$,他可以走到山峰 $p+1$。
约翰在没有正常工作的灯笼时不能移动。他必须保证每个时刻都有至少一盏灯笼正常工作,才能在两座山峰间移动。(在行走过程中不必是同一盏灯笼。)
例如,假设农夫约翰目前在海拔为 $4$ 的山峰上,希望走到高度为 $1$ 的相邻山峰。如果约翰有海拔范围为 $[1,3]$ 和 $[3,4]$ 的两盏灯笼,他可以从一个山峰走到另一个山峰。
但是,如果约翰只有海拔范围为 $[1,1]$ 和 $[2,5]$ 的两盏灯笼,他无法在这两座山峰间行走:例如,他没有灯笼能在海拔 $1.47$ 处正常工作。
你需要给出多个独立问题的答案。
对于每个满足 $a_j\le h_{p_j}\le b_j$ 的 $1\le j\le k$,假设约翰一开始在山峰 $p_j$ 并买下第 $j$ 个灯笼。为了搜索整个山脉,他必须重复执行上面提到的三种操作。对于每个 $j$,求出约翰至少需要花几法郎,才能搜索整个山脉。(这个花费包括初始时买的第 $j$ 个灯笼。)
输入输出格式
输入格式
第一行两个整数 $n,k$——山峰个数和灯笼个数。
第二行 $n$ 个整数 $h_1,h_2,\ldots,h_n$:每座山峰的海拔。保证 $h_i$ 构成一个 $1\sim n$ 的排列。
接下来 $k$ 行,每行四个整数 $p_j,c_j,a_j,b_j$——第 $j$ 个灯笼的售卖位置、价格和海拔范围。
输出格式
对于每个 $1\le j\le k$,输出一行:
- 若 $h_{p_j}$ 不在 $[a_j,b_j]$ 内,输出 $-1$。
- 否则,如果约翰一开始购买第 $j$ 个灯笼,无法搜索整个山脉,输出 $-1$。
- 否则,输出此时的最少花费。
输入输出样例
输入样例 #1
7 8
4 2 3 1 5 6 7
3 1 2 4
1 2 1 3
4 4 1 7
6 10 1 7
6 20 6 6
6 30 5 5
7 40 1 6
7 50 7 7
输出样例 #1
7
-1
4
10
30
-1
-1
-1
说明
**样例解释**
如果约翰从第 $3$ 座山峰开始,购买第 $1$ 个灯笼,他可以如下操作:
- 向左走两次,到达山峰 $1$。
- 购买灯笼 $2$。
- 向右走到山峰 $4$。
- 购买灯笼 $3$。
- 向右走到山峰 $7$。
此时,约翰到达了每座山峰至少一次,花费了 $1+2+4=7$ 法郎。
约翰不能从购买灯笼 $2,6,7$ 开始,因为它们在购买的海拔处不工作。因此,它们的答案为 $-1$。
如果约翰从购买灯笼 $3,4$ 开始,他不用购买其他灯笼就可以访问每座山峰。
如果约翰从购买灯笼 $5$ 开始,他必须购买灯笼 $4$。
如果约翰从购买灯笼 $8$ 开始,他会被困在山峰 $7$。即使他购买了灯笼 $7$,他依然无法从山峰 $7$ 走到山峰 $6$。
---
**数据范围**
对于全部数据,$1\le n,k\le 2\times 10^3$,$1\le h_i\le n$ 且 $h_i$ 构成一个 $1\sim n$ 的排列,$1\le p_j\le n$,$1\le c_j\le 10^6$,$1\le a_j\le b_j\le n$。
- 子任务一($9$ 分):$n\le 20$,$k\le 6$。
- 子任务二($12$ 分):$n,k\le 70$。
- 子任务三($23$ 分):$n,k\le 300$,$h_i=i$。
- 子任务四($16$ 分):$n,k\le 300$。
- 子任务五($40$ 分):无特殊限制。