#P16154. [2022国家队训练南京站]火车旅行

    ID: 15365 传统题 5000ms 1024MiB 尝试: 1 已通过: 1 难度: 10 上传者: 标签>CF3300数据结构单调栈线段树倍增

[2022国家队训练南京站]火车旅行

题目描述

某条铁路线(非环线)有 nn 站,依次编号为 1,…,n1,\ldots,n。这条线路上跑着 nn 类列车,编号为 1,…,n1,\ldots,n。每种列车都是双向运行的。

这条铁路线上的每个车站都有个旅客流量,旅客流量是一个 ≤n\le n 的正整数。车站 i (1≤i≤n)i\ (1\le i\le n) 的旅客流量为 aia_i。

第 jj 类列车(1≤j≤n1\le j\le n)在且只在旅客流量 ≥j\ge j 的车站停车。一名旅客可以从 xx 站出发,乘上任意一辆在 xx 停车的列车,沿着列车的方向行驶到该列车的下一个停车的车站 yy。如果列车是向左行驶的,即 y<xy<x,那么旅客需要花费 lxl_x ddtt 币;否则列车是向右行驶的,即 y>xy>x,此时旅客需要花费 rxr_x ddtt 币。

数据保证对于 1≤i≤n−11\le i\le n-1,有 li≤li+1l_i\le l_{i+1}、ri≥ri+1r_i\ge r_{i+1}。

现有 qq 名旅客,依次编号为 1,…,q1,\ldots,q,旅客 k (1≤k≤q)k\ (1\le k\le q) 的起点是车站 sks_k,终点是 tk (1≤sk,tk≤n)t_k\ (1\le s_k,t_k\le n)。假设这些旅客只能靠这条铁路线移动。

对于每名旅客,求这名旅客到达终点至少需要花费多少 ddtt 币。保证同一名旅客的起点与终点不同。允许走回头路。多组测试。

输入格式

第一行一个正整数 T (1≤T≤3⋅104)T\ (1\le T\le 3\cdot 10^4),表示数据组数。

接下来对于每组数据:

第一行包含两个整数 n,q (1≤n,q≤3⋅105)n,q\ (1\le n,q\le 3\cdot 10^5),表示车站数量和旅客数量。

第二行包含 nn 个整数 a1,…,ana_1,\ldots,a_n,表示车站的旅客流量。

接下来 nn 行,每行两个正整数 li,ri (1≤li,ri≤109)l_i,r_i\ (1\le l_i,r_i\le 10^9)。

接下来 qq 行,每行两个正整数 sk,tk (1≤sk,tk≤n)s_k,t_k\ (1\le s_k,t_k\le 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\sum n,\sum q\le 3\cdot 10^5,1≤li,ri≤1091\le l_i,r_i\le 10^9,1≤sk,tk≤n1\le s_k,t_k\le n。

保证 li≤li+1l_i\le l_{i+1}、ri≥ri+1r_i\ge r_{i+1}。

子任务 分值 限制
Subtask 1 3 pts 保证 ∑n≤400\sum n\le 400
Subtask 2 14 pts 保证 ∑n,∑q≤5000\sum n,\sum q\le 5000
Subtask 3 21 pts 保证 ∑n≤5000\sum n\le 5000
Subtask 4 20 pts 保证 li=ri=1 (1≤i≤n)l_i=r_i=1\ (1\le i\le n)
Subtask 5 42 pts 无特殊限制