#2197. 火车旅行

    ID: 2197 传统题 1000ms 256MiB 尝试: 0 已通过: 0 难度: 省选/NOI- 上传者: 标签>TEAM赛事:contest1649来源:qoj.ac数据:公开样例二分答案

火车旅行

火车旅行

题目描述

标题: 火车旅行 - Problem - QOJ.ac

#8366. 火车旅行

Statistics

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