#2197. 火车旅行
火车旅行
火车旅行
题目描述
标题: 火车旅行 - Problem - QOJ.ac
#8366. 火车旅行
The problem was used in the following contests:
题目描述
某条铁路线(非环线)有 n 站,依次编号为 1,…,n。这条线路上跑着 n 类列车,编号为 1,…,n。每种列车都是双向运行的。
这条铁路线上的每个车站都有个旅客流量,旅客流量是一个 ≤n 的正整数。车站 i(1≤i≤n) 的旅客流量为 ai 。
第 j 类列车 (1≤j≤k) 在且只在旅客流量 ≥j 的车站停车。一名旅客可以从 x 站出发,乘上任意一辆在 x 停车的列车,沿着列车的方向行驶到该列车的下一个停车的车站 y 。如果列车是向左行驶的,即 y<x ,那么旅客需要花费 lx ddtt 币,否则列车是向右行驶的,即 y>x ,此时旅客需要花费 rx ddtt 币。
数据保证对于 1≤i≤n−1 ,有 li≤li+1,ri≥ri+1 。
现有 q 名旅客,依次编号为 1,…,q,旅客 k(1≤k≤q) 的起点是车站 sk,终点是 tk (1≤sk,tk≤n)。假设这些旅客只能靠这条铁路线移动。
对于每名旅客,求这名旅客到达终点至少需要花费多少 ddtt 币。保证同一名旅客的起点与终点不同。允许走回头路。多组测试。
输入格式
第一行一个正整数 T(1≤T≤3⋅104) ,表示数据组数。
接下来对于每组数据,第一行包含两个整数 n,q(1≤n,q≤3⋅105) ,表示车站数量和旅客数量。
第二行包含 n 个整数 a1,…,an ,表示车站的旅客流量。
接下来 n 行,每行两个正整数 li,ri(1≤li,ri≤109,li≤li+1,ri≥ri+1) 。
接下来 q 行,每行两个正整数 sk,tk(1≤sk,tk≤n) 。
输出格式
对每名旅客,输出他到达终点至少需要花费的 ddtt 币数量。
样例输入 1
1
9 6
1 7 3 4 9 9 1 2 2
1 11
1 11
5 11
7 10
8 6
8 4
8 3
9 1
10 1
1 9
5 1
3 1
7 6
2 6
1 1
样例输出 1
33
9
6
8
17
0
数据范围
保证 ∑n,∑q≤3⋅105,1≤li,ri≤109,1≤sk,tk≤n 。
保证 li≤li+1,ri≥ri+1 。
subtask1(3pts):保证 ∑n≤400 。
subtask2(14pts):保证 ∑n,∑q≤5000 。
subtask3(21pts):保证 ∑n≤5000 。
subtask4(20pts):保证 li=ri=1(1≤i≤n) 。
subtask5(42pts):无特殊限制。
时间限制:5s
空间限制:1GB
输入格式
(见题面原文)
输出格式
(见题面原文)
数据范围
(见题面原文)
样例
样例 1
1
9 6
1 7 3 4 9 9 1 2 2
1 11
1 11
5 11
7 10
8 6
8 4
8 3
9 1
10 1
1 9
5 1
3 1
7 6
2 6
1 1
33
9
6
8
17
0