2384 . 小祥愛騎車
TopCoder
Tags
Description
小祥從 F1 退役之後決定轉戰摩托車比賽，加入 MotoGP。MotoGP 是由施巨砲 (GP) 舉辦的摩托車賽事，每場比賽都有許多人參加，但是因為小祥跟施巨砲太強了，所以今年度的 MotoGP 儼然成為了小祥跟施巨砲的一對一對決。
MotoGP 中，有 $N$ 個可選的比賽賽道，從左到右為第 $1$ 個到第 $N$ 個。小祥跟施巨砲各自熟悉不同的賽道，因此對於第 $i$ 個賽道來說，小祥的技能值為 $A_i$，施巨砲的技能值為 $B_i$。在一場 MotoGP 的賽事中，會選取一段區間 $[i,j]$ ，並用第 $i$ 個到第 $j$ 個賽道進行比賽。對於小祥來說，他想要讓他與施巨砲的技能值差距越大；同時，因為他覺得他的體力比施巨砲好（每多一場比賽，他就比施巨砲好 $K$ 個單位的體能），他也想要讓比賽的賽道數量越多越好。因此，對於一段區間 $[i,j]$ 來說，小祥對它的好感度為 $\max_{i \leq v \leq j} A_v - \max_{i \leq v \leq j} B_v + K * (j - i + 1)$。
接下來會舉行連續 $Q$ 天的賽事，每天只有第 $L$ 到第 $R$ 條賽道是能比賽的，比賽委員會會在這些賽道內選擇一段連續的區間 $[i,j]$ 比賽 ($L \leq i \leq j \leq R$)。小祥靠著關係賄賂了比賽委員會，讓他可以選擇要選哪些賽道比賽。請幫他寫一個程式，計算對於每天的比賽，他的最大好感度為何（注意好感度可能為負數）。
Input Format
第一行有兩個整數 $N,K$，意義如題目所述
第二行有 $N$ 個正整數 $A_1 ,\dots ,A_N$，代表小祥對賽道的技能值
第三行有 $N$ 個正整數 $B_1, \dots ,B_N$，代表施巨砲對賽道的技能值
第四行有一個正整數 $Q$ ，代表詢問數量
接下來的 $Q$ 行中，每行有兩個正整數 $L_i,R_i$ ，代表當天有比賽的賽道
對於所有測試資料：
- $1 \leq N,Q \leq 100000$
- $0 \leq K \leq 10 ^ 8$
- $1 \leq A_i, B_i \leq 10 ^ {13}$
Output Format
請輸出 $Q$ 行，每行輸出一個整數，代表第 $i$ 天的最大好感度。
Sample Input 1
8 4 5 3 9
2 6 1 2 10
4
1 5
1 3
2 3
4 5
Sample Output 1
8
6
3
Sample Input 2
88 16 42 15 94 65 3 9 98 4
50 3 95 36 25 59 35 77 1 69
6
1 10
5 9
2 4
5 10
9 10
2 10
Sample Output 2
102
18
102
102
102
Hints
範例測資 1 解釋：
對於第 $1$ 天，小祥可以選擇 $[1,4]$，此時好感度為 $8-6+2\cdot (4-1+1)=10$。
對於第 $2$ 天，小祥可以選擇 $[1,3]$，此時好感度為 $8-6+2\cdot (3-1+1)=8$。
對於第 $3$ 天，小祥可以選擇 $[3,3]$，此時好感度為 $5-1+2\cdot (3-3+1)=6$。
對於第 $4$ 天，小祥可以選擇 $[4,4]$，此時好感度為 $3-2+2\cdot (4-4+1)=3$。
Problem Source
2024 MotoGP 系列賽可以在 YouTube SPOTV Asia 免費收看喔～
Subtasks
| No. | Testdata Range | Constraints | Score |
|---|---|---|---|
| 1 | 0~1 | 範例測資 | 0 |
| 2 | 0~6 | $N,Q \leq 100$ | 7 |
| 3 | 0~11 | $N \leq 2000$ | 14 |
| 4 | 3, 8, 12~17 | $K=0$ | 15 |
| 5 | 18~26 | $Q=1$、$L_1 = 1$、$R_1 = N$ | 26 |
| 6 | 0~39 | 無特別限制 | 38 |