A. DBMB and the Array

项目	限制
时间限制	1 second
空间限制	256 megabytes

题目描述

English

DBMB had a birthday yesterday. He was gifted an array $a$ of $n$ elements and a number $x$. But there is one problem: he only likes arrays where the sum of the elements equals $s$. To make the array appealing to him, you can perform the following operation any number of times:

• Choose an index $i$ ($1 \leqslant i \leqslant n$) and add $x$ to the number $a_i$.

For example, if he was given the array $[1, 2, 3, 5]$ and $x = 2$, you can choose index $3$ and get the array $[1, 2, 5, 5]$. Your task is to determine whether the array can appeal to DBMB after any number of operations.

中文翻译

DBMB 昨天过生日。他收到了一个包含 $n$ 个元素的数组 $a$ 和一个数字 $x$。但有一个问题：他只喜欢数组中元素之和等于 $s$ 的情况。为了让这个数组变得合他心意，你可以进行任意次如下操作：

• 选择一个下标 $i$（$1 \leqslant i \leqslant n$），并将 $x$ 加到 $a_i$ 上。

例如，如果他得到的数组是 $[1, 2, 3, 5]$ 且 $x = 2$，你可以选择下标 $3$，从而得到数组 $[1, 2, 5, 5]$。你的任务是判断经过任意次操作后，该数组能否让 DBMB 满意。

输入描述

English

Each test consists of several test cases. The first line contains a single integer $t$ ($1 \leqslant t \leqslant 1000$) — the number of test cases. The following describes the test cases.

The first line of each test case contains three integers $n$, $s$, $x$ ($1 \leqslant n, x \leqslant 10$, $1 \leqslant s \leqslant 100$).

The second line of each test case contains $n$ integers $a_1, a_2, \dots a_n$ ($1 \leqslant a_i \leqslant 10$) — the elements of the array gifted to DBMB.

中文翻译

每个测试包含多个测试用例。第一行包含一个整数 $t$（$1 \leqslant t \leqslant 1000$）——测试用例的数量。接下来描述各个测试用例。

每个测试用例的第一行包含三个整数 $n$，$s$，$x$（$1 \leqslant n, x \leqslant 10$，$1 \leqslant s \leqslant 100$）。

每个测试用例的第二行包含 $n$ 个整数 $a_1, a_2, \dots a_n$（$1 \leqslant a_i \leqslant 10$）——送给 DBMB 的数组元素。

输出描述

English

For each test case, output YES if the array can appeal to DBMB. Otherwise, output NO.

You can output each letter in any case (lowercase or uppercase). For example, the strings yEs, yes, Yes, and YES will be accepted as a positive answer.

中文翻译

对于每个测试用例，如果该数组能让 DBMB 满意，则输出 YES。否则，输出 NO。

每个字母可以以任意大小写形式输出（小写或大写）。例如，字符串 yEs、yes、Yes 和 YES 都将被视为肯定回答。

样例 #1

Input

6
3 3 5
1 1 1
3 8 2
1 2 3
4 7 2
1 1 1 1
3 15 1
2 4 10
2 100 5
4 6
5 12 1
1 2 2 3 2

output

YES
YES
NO
NO
YES
YES

注释

English

In the second test case, $a = [1, 2, 3]$, applying the operation on $a_2$ gives us $a = [1, 4, 3]$. The sum of the array equals $s$.

中文翻译

在第二个测试用例中，$a = [1, 2, 3]$，对 $a_2$ 进行操作后得到 $a = [1, 4, 3]$。数组元素之和等于 $s$。

题解

给定数组 $a$ 我们对其求和得到 $s_a$，如果存在 $t\in \mathbb{N}$ 使得 $s_a+tx=s$ 成立，所以我们可以得到 $x\mid (s_a-s)$，确保 $(s_a-s)\%x=0$ 即输入 Yes，否则输出 No，复杂度 $O(1)$。

AC Code

A.cc

// WIP

B. Reverse a Permutation

项目	限制
时间限制	2 seconds
空间限制	256 megabytes

题目描述

English

A permutation of length $n$ is an array consisting of $n$ distinct integers from $1$ to $n$ in arbitrary order. For example, $[2,3,1,5,4]$ is a permutation, but $[1,2,2]$ and $[1,3,4]$ are not permutations.

You are given a permutation $p$ of length $n$. You can perform the following operation exactly once:

• Choose two integers $\ell,$ $r$ ($1\leqslant \ell\leqslant r\leqslant n$).
• Reverse the segment $[\ell, r]$ in the permutation $p$.

Your task is to output the lexicographically maximum permutation that can be obtained by performing this operation. A permutation $a$ is lexicographically greater than a permutation $b$ if for the first position $i$ where they differ, it holds that $a_i> b_i$.

中文翻译

长度为 $n$ 的排列是指一个包含 $1$ 到 $n$ 之间所有整数各恰好一次、顺序任意的数组。例如，$[2,3,1,5,4]$ 是一个排列，但 $[1,2,2]$ 和 $[1,3,4]$ 不是排列。

给定一个长度为 $n$ 的排列 $p$。你可以恰好执行一次以下操作：

• 选择两个整数 $\ell,$ $r$ ($1\leqslant \ell\leqslant r\leqslant n$)。
• 将排列 $p$ 中从位置 $\ell$ 到 $r$ 的子数组反转。

你的任务是输出执行此操作后能得到的字典序最大的排列。如果两个排列在第一个不同的位置 $i$ 处满足 $a_i > b_i$，则称排列 $a$ 的字典序大于排列 $b$。

输入描述

English

Each test consists of several test cases. The first line contains a single integer $t$ ($1\leqslant t\leqslant10^4$) — the number of test cases. The description of the test cases follows.

The first line of each test case contains the number $n$ ($1\leqslant n\leqslant 2\cdot 10^5$).

The second line of each test case contains $n$ distinct integers $p_1, p_2,...,p_n$ $(1\leqslant p_i\leqslant n)$.

It is guaranteed that the sum of the values of $n$ across all test cases does not exceed $2\cdot 10^5$.

中文翻译

每个测试包含多个测试用例。第一行包含一个整数 $t$（$1\leqslant t\leqslant 10^4$）——测试用例的数量。接下来是各个测试用例的描述。

每个测试用例的第一行包含整数 $n$（$1\leqslant n\leqslant 2\cdot 10^5$）。

每个测试用例的第二行包含 $n$ 个互不相同的整数 $p_1, p_2,...,p_n$ $(1\leqslant p_i\leqslant n)$。

保证所有测试用例中 $n$ 的总和不超过 $2\cdot 10^5$。

输出描述

English

For each test case, output the lexicographically maximum permutation that can be obtained with one operation.

中文翻译

对于每个测试用例，输出通过一次操作能够得到的字典序最大的排列。

样例

Input

4
4
3 2 1 4
3
3 1 2
4
4 3 2 1
2
2 1

output

4 1 2 3 
3 2 1 
4 3 2 1 
2 1

注释

English

For the first test case, the best segment is $[1, 4]$. After reversing, $a = [4, 1, 2, 3]$. For the second test case, the best segment is $[2, 3]$. After reversing, $a = [3, 2, 1]$.

中文翻译

对于第一个测试用例，最佳区间是 $[1, 4]$。反转后，$a = [4, 1, 2, 3]$。对于第二个测试用例，最佳区间是 $[2, 3]$。反转后，$a = [3, 2, 1]$。

题解

首先我们将 $p$ 进行倒序排序，那么得到的一定是最大的字典序排列，例如 $n=5,p_{\max}=[5,4,3,2,1]$，我们将输入的 $p$ 与 $p_{\max}$ 进行比对，找出第一个不同的地方，例如 $p=[5,4,2,1,3]$ 那么第一次不同的下标记为 $\ell$ 则在本例中 $\ell=3$，那么接下来找到 $p_i=\ell$ 的 $i$ 的值，本例中为 $p_5=\ell=3$，那么将 $r$ 记为 $5$，反转 $[3,5]$ 为本题最大，即 $p=[5,4,3,1,2]$。单个用例时间复杂度为 $O(n)$。

AC Code

B.cc

// WIP

C. Replace and Sum

项目	限制
时间限制	2 seconds
空间限制	256 megabytes

题目描述

English

Today, KQ has an exam at the Grail Academy. A strict teacher gave a task that KQ could not solve. He was given two arrays $a$ and $b$ of length $n$. KQ is allowed to perform the following operations on the arrays:

• Choose an index $i$ ($1\leqslant i< n$) and replace $a_i$ with $a_{i+1}$.
• Choose an index $i$ ($1\leqslant i\leqslant n$) and replace $a_i$ with $b_i$.

Now he has $q$ queries. Each query is described by two numbers $\ell$ and $r$. His task is to find the maximum value of the sum $(a_\ell + a_{\ell +1} + a_{\ell +2} + \dots + a_r)$ for each query, if he can perform any number of operations on any elements of the array. Since he is not skilled enough for this, he asks for your help.

中文翻译

今天，KQ 在圣杯学院有一场考试。一位严格的老师布置了一道 KQ 无法解决的任务。他拿到了两个长度为 $n$ 的数组 $a$ 和 $b$。KQ 被允许对数组执行以下操作：

• 选择一个下标 $i$（$1\leqslant i < n$），将 $a_i$ 替换为 $a_{i+1}$。
• 选择一个下标 $i$（$1\leqslant i \leqslant n$），将 $a_i$ 替换为 $b_i$。

现在他有 $q$ 个查询。每个查询由两个数字 $\ell$ 和 $r$ 描述。他的任务是针对每个查询，求出在可以对数组中的任意元素执行任意次操作的情况下，和 $(a_\ell + a_{\ell +1} + a_{\ell +2} + \dots + a_r)$ 的最大值。由于他在这方面的能力不足，他请求你的帮助。

输入描述

English

Each test consists of several test cases. The first line contains one integer $t$ ($1\leqslant t\leqslant 10^4$) — the number of test cases. The description of the test cases follows.

The first line of each test case contains two integers $n$, $q$ $(1\leqslant n, q\leqslant 2 \cdot 10^5)$.

The second line of each test case contains $n$ integers $a_1, a_2,...,a_n$ $(1\leqslant a_i\leqslant 10^4)$.

The third line of each test case contains $n$ integers $b_1, b_2,...,b_n$ $(1\leqslant b_i\leqslant 10^4)$.

The following $q$ lines contain two integers $\ell$ and $r$ $(1\leqslant \ell\leqslant r\leqslant n)$.

It is guaranteed that the sum of the values of $n$ and the sum of the values of $q$ across all test cases do not exceed $2 \cdot 10^5$.

中文翻译

每个测试包含多个测试用例。第一行包含一个整数 $t$（$1\leqslant t\leqslant 10^4$）——测试用例的数量。接下来是各个测试用例的描述。

每个测试用例的第一行包含两个整数 $n$，$q$ $(1\leqslant n, q\leqslant 2 \cdot 10^5)$。

每个测试用例的第二行包含 $n$ 个整数 $a_1, a_2,...,a_n$ $(1\leqslant a_i\leqslant 10^4)$。

每个测试用例的第三行包含 $n$ 个整数 $b_1, b_2,...,b_n$ $(1\leqslant b_i\leqslant 10^4)$。

接下来的 $q$ 行包含两个整数 $\ell$ 和 $r$ $(1\leqslant \ell\leqslant r\leqslant n)$。

保证所有测试用例中 $n$ 的总和以及 $q$ 的总和均不超过 $2 \cdot 10^5$。

输出描述

English

For each test case, output $q$ numbers separated by spaces — the maximum values of the sums $(a_\ell + a_{\ell+1} + a_{\ell+2} + \dots + a_r)$.

中文翻译

对于每个测试用例，输出 $q$ 个用空格分隔的数字——即和 $(a_\ell + a_{\ell+1} + a_{\ell+2} + \dots + a_r)$ 的最大值。

样例

Input

4
3 1
3 2 1
1 2 3
1 3
1 1
1
2
1 1
3 2
6 7 5
9 6 8
1 2
2 3
4 3
4 3 2 1
5 1 3 1
1 2
2 4
3 4

output

9
2
17 16
8 7 4

注释

English

Consider the first test case. Replace $a_3$ with $b_3$, $a = [3, 2, 3]$. Replace $a_2$ with $a_3$, $a = [3, 3, 3]$. The sum $a_1 + a_2 + a_3 = 9$.

中文翻译

考虑第一个测试用例。将 $a_3$ 替换为 $b_3$，得到 $a = [3, 2, 3]$。再将 $a_2$ 替换为 $a_3$，得到 $a = [3, 3, 3]$。此时和 $a_1 + a_2 + a_3 = 9$。

题解

考虑贪心求解全局最大值，首先对于 $\exist ~ i\in [1,n]$ 如果有 $b_i>a_i$ 那就使得 $a_i:=b_i$，这保证了从突破自身限制从外部获取了最大值，其次 $\exist ~ i\in [1,n)$ 如果有 $a_{i+1}>a_i$ 那就使得 $a_i:=a_{i+1}$，这样保证了 $a$ 一定是最大的可能数组，这样 $\sum_{i=\ell}^{r} a_i$ 一定是最大的可能值。

那么如果对于 $q$ 次询问，每次都对 $[\ell,r]$ 求和复杂度极端情况下来到了 $O(nq)$，这需要我们使用前缀和维护。设数组

$$S_i=\sum_{i=0}^{i}a_i$$

令 $a_0=0$，那么

$$\sum_{i=\ell}^{r} a_i=S_r-S_{\ell-1}$$

即可求出，时间复杂度 $O(n)$，空间复杂度 $O(n)$。

AC Code

C.cc

// WIP

D. Monster Game

项目	限制
时间限制	2 seconds
空间限制	256 megabytes

题目描述

English

You have been gifted a new game called "Elatyh". In the game, you are given $n$ swords, each with its own strength. In particular, the sword numbered $i$ has a strength of $a_i$. The game consists of $n$ levels, each of which features a monster.

You start at level $1$ and progress further. To pass level $i$ and move on to level $i + 1$, you need to defeat the monster at level $i$. To defeat the monster at level $i$, you need to deal it $b_i$ sword strikes. The swords in the game are very fragile, so they can only deal one strike before breaking. If you complete level $n$ or run out of swords, you can finish the game and proceed to score calculation.

Before the game, you are allowed to choose the difficulty level. If you choose difficulty $x$, swords with a strength less than $x$ will not affect the monsters. The game score in this case is equal to $x$ multiplied by the number of levels completed. Your task is to choose the game difficulty in such a way as to maximize the game score.

中文翻译

你获得了一款新游戏，名为“Elatyh”。在游戏中，你会得到 $n$ 把剑，每把剑都有自己的力量值。具体来说，编号为 $i$ 的剑力量为 $a_i$。游戏包含 $n$ 个关卡，每个关卡都有一只怪物。

你从第 $1$ 关开始，逐渐推进。要通过第 $i$ 关并进入第 $i+1$ 关，你需要击败第 $i$ 关的怪物。为了击败第 $i$ 关的怪物，你需要用剑攻击它 $b_i$ 次。游戏中的剑非常脆弱，每把剑在攻击一次后就会损坏。如果你完成了第 $n$ 关或者剑用完了，就可以结束游戏并进入得分计算阶段。

在游戏开始前，你可以选择难度等级。如果你选择难度 $x$，那么力量小于 $x$ 的剑将无法对怪物造成影响。此时游戏得分等于 $x$ 乘以完成的关卡数。你的任务是选择合适的游戏难度，以使游戏得分最大化。

输入描述

English

Each test consists of several test cases. The first line contains a single integer $t$ ($1\leqslant t\leqslant 10^4$) — the number of test cases. The following describes the test cases.

The first line of each test case contains a single integer $n$ ($1\leqslant n\leqslant 2 \cdot 10^5$).

The second line of each test case contains $n$ integers $a_1, a_2, \dots, a_n$ $(1\leqslant a_i\leqslant 10^9)$.

The third line of each test case contains $n$ integers $b_1, b_2, \dots, b_n$ $(1\leqslant b_i\leqslant n)$.

It is guaranteed that the sum of the values of $n$ across all test cases does not exceed $2 \cdot 10^5$.

中文翻译

每个测试包含多个测试用例。第一行包含一个整数 $t$（$1\leqslant t\leqslant 10^4$）——测试用例的数量。接下来是各个测试用例的描述。

每个测试用例的第一行包含一个整数 $n$（$1\leqslant n\leqslant 2 \cdot 10^5$）。

每个测试用例的第二行包含 $n$ 个整数 $a_1, a_2, \dots, a_n$ $(1\leqslant a_i\leqslant 10^9)$。

每个测试用例的第三行包含 $n$ 个整数 $b_1, b_2, \dots, b_n$ $(1\leqslant b_i\leqslant n)$。

保证所有测试用例中 $n$ 的总和不超过 $2 \cdot 10^5$。

输出描述

English

For each test case, output a single integer — the maximum game score.

中文翻译

对于每个测试用例，输出一个整数——即游戏的最大得分。

样例

Input

5
3
1 3 4
2 1 1
2
2 3
1 1
4
1 2 3 4
2 2 1 1
6
4 4 1 4 5 4
2 2 4 1 2 2
10
1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000
1 1 1 1 1 1 1 1 1 1

output

3
4
3
8
10000000000

注释

English

Consider the first test case. Optimal difficulty to choose is $3$. If difficulty is $3$, you can deal strikes with swords number $2$ and $3$. With $2$ swords you can complete $1$ level, so the game score is $3\cdot 1 = 3$.

中文翻译

考虑第一个测试用例。最优选择的难度是 $3$。如果难度设为 $3$，你可以使用编号为 $2$ 和 $3$ 的剑进行攻击。拥有 $2$ 把剑，你可以完成 $1$ 关，因此游戏得分为 $3 \cdot 1 = 3$。

题解

考虑难度 $x$ 选择应为力量 $a_i$，且 $a_i$ 除了对难度选择外没有任何影响，那么我们贪心地将其倒序排序，依次选择最大的 $a_i$ 作为 $x$，那么就可以在游戏中攻击 $i$ 次。

设通关数为 $t$ 那么有通关数组 $c$ 表示通过 $t$ 关需要攻击 $c_t$ 次，$c_t$ 数组正好是 $b_i$ 的前缀和，举个例子，$b=[2,2,1,1]$，那么 $c=[2,4,5,6]$，则通过 $2$ 关就是需要攻击 $c_2=4$ 次。

枚举 $c_i$，求 $c_i\cdot a_{c_i}$ 的最大值，复杂度为 $O(n)$。

AC Code

D.cc

// WIP

E. Product Queries

项目	限制
时间限制	3 seconds
空间限制	256 megabytes

题目描述

English

Today, Sabyrzhan was called to the board with an array $a$ of length $n$ and was assigned an officer's task — to answer $n$ questions.

In the $i$-th question, it is required to determine the minimum number of elements from the array that need to be selected from the board (it is allowed to use the same element multiple times) so that their product is exactly equal to $i$, or to report that it is impossible to achieve such a product.

Note that at least one element must be selected.

中文翻译

今天，Sabyrzhan 被叫到黑板前，拿到了一个长度为 $n$ 的数组 $a$，并接到一项艰巨的任务——回答 $n$ 个问题。

在第 $i$ 个问题中，需要确定从黑板的数组里最少选择多少个元素（允许多次使用同一个元素），才能使它们的乘积恰好等于 $i$；如果无法得到这样的乘积，则报告不可能。

注意：至少必须选择一个元素。

输入描述

English

Each test consists of several test cases. The first line contains one integer $t$ ($1 \leqslant t \leqslant 10^4$) — the number of test cases. The description of the test cases follows.

The first line of each test case contains one integer $n$ ($1 \leqslant n \leqslant 3 \cdot 10 ^ 5$).

The second line of each test case contains $n$ integers $a_1, a_2, \ldots, a_n$ ($1 \leqslant a_i \leqslant n$).

It is guaranteed that the sum of the values of $n$ across all test cases does not exceed $3 \cdot 10 ^ 5$.

中文翻译

每个测试包含多个测试用例。第一行包含一个整数 $t$（$1 \leqslant t \leqslant 10^4$）——测试用例的数量。接下来是各个测试用例的描述。

每个测试用例的第一行包含一个整数 $n$（$1 \leqslant n \leqslant 3 \cdot 10 ^ 5$）。

每个测试用例的第二行包含 $n$ 个整数 $a_1, a_2, \ldots, a_n$（$1 \leqslant a_i \leqslant n$）。

保证所有测试用例中 $n$ 的总和不超过 $3 \cdot 10 ^ 5$。

输出描述

English

For the $i$-th question, output one integer — the minimum number of elements from the array required to obtain a product equal to $i$, or $−1$ if it is impossible to achieve such a product.

中文翻译

对于第 $i$ 个问题，输出一个整数——要使乘积等于 $i$ 所需的最少数组元素个数；如果无法实现这样的乘积，则输出 $-1$。

样例

Input

6
8
3 2 2 3 7 3 6 7
5
1 2 3 4 5
3
1 1 1
10
2 1 2 1 3 5 5 7 7 7
4
1 1 2 2
1
1

output

-1 1 1 2 -1 1 1 3
1 1 1 1 1
1 -1 -1
1 1 1 2 1 2 1 3 2 2
1 1 -1 2
1

注释

English

Consider the first test case. The products can be obtained as follows:

• $1$ cannot be obtained.
• $2$ can be obtained by selecting $a_2$.
• $3$ can be obtained by selecting $a_1$.
• $4$ can be obtained by selecting $a_2$ twice.
• $5$ cannot be obtained.
• $6$ can be obtained by selecting $a_7$.
• $7$ can be obtained by selecting $a_5$.
• $8$ can be obtained by selecting $a_2$ three times.

中文翻译

考虑第一个测试用例。乘积可以通过以下方式得到：

• $1$ 无法得到。
• $2$ 可以通过选择 $a_2$ 得到。
• $3$ 可以通过选择 $a_1$ 得到。
• $4$ 可以通过选择 $a_2$ 两次得到。
• $5$ 无法得到。
• $6$ 可以通过选择 $a_7$ 得到。
• $7$ 可以通过选择 $a_5$ 得到。
• $8$ 可以通过选择 $a_2$ 三次得到。

题解

筛法，首先我们先对数组去重并排序后，生成 $[1..n]$ 的一维表格并初始化为最大值，那么对于一个 $a_i$，有 $1\times a_i,2\times a_i,\cdots,t\times a_i$ 直到超出数组 $n$ 为止，并在 $1\times a_i,2\times a_i,\cdots,t\times a_i$ 的值上更新更小的值即可。总的操作次数类似于 $\sum_{i=1}^{n} \frac{n}{i}$，这是一个典型的调和级数，复杂度为 $O(n \log n)$。

最后还有一个 $1$ 特判即可，如果最大值就输出 $-1$，否则输出标记值。

AC Code

E.cc

// WIP

F. Pizza Delivery

项目	限制
时间限制	2 seconds
空间限制	256 megabytes

题目描述

English

Courier YF has earned the title of the best pizza delivery person GR. The manager does not like him, so he decided to give him a very difficult task. The manager provided him with $n$ coordinates of houses $(x_i, y_i)$ where he needs to deliver the pizza. He will deliver the pizza in the following way:

• GR pizza is prepared at the point ($Ax, Ay$) and YF starts the delivery from this point.
• To deliver the pizza, he can move from the point ($x, y$) to three points ($x+1, y$), ($x, y+1$), ($x, y-1$).
• After he has delivered all the pizzas, he returns home to the point ($Bx, By$).

Each move takes him exactly one second, and handing over the pizza to the customer takes $0$ seconds. The manager wants the delivery to be as fast as possible. You need to find the minimum delivery time for all GR pizzas. It is guaranteed that delivery is always possible.

中文翻译

快递员 YF 荣获了 GR 地区最佳披萨送餐员的称号。经理并不喜欢他，于是决定交给他一项非常艰巨的任务。经理给了他 $n$ 个送餐住户的坐标 $(x_i, y_i)$。他将按以下方式配送披萨：

• 起点： GR 披萨在点 $(Ax, Ay)$ 制作，YF 从该点出发开始配送。
• 移动规则： 在配送过程中，他可以从当前点 $(x, y)$ 移动到以下三个点：$(x+1, y)$、$(x, y+1)$ 和 $(x, y-1)$。
• 终点： 在送完所有披萨后，他需要回到位于点 $(Bx, By)$ 的家中。

每次移动恰好耗时 1 秒，而将披萨交给客户的时间为 0 秒。经理希望配送速度越快越好。你需要计算送完所有 GR 披萨所需的最短时间。题目保证配送总是可以完成的。

输入描述

English

Each test consists of several test cases. The first line contains one integer $t$ ($1 \leqslant t \leqslant 10^4$) — the number of test cases. The description of the test cases follows.

The first line of each test case contains five integers $n$, $Ax$, $Ay$, $Bx$, $By$ ($1 \leqslant n \leqslant 2 \cdot 10^5$, $1 \leqslant Ax, Ay, Bx, By \leqslant 10^9$) — the number of houses for delivery, as well as the coordinates of the start and end points.

The second line of each test case contains $n$ integers $x_1, x_2, \dots, x_n$ ($Ax \lt x_i \lt Bx$).

The third line of each test case contains $n$ integers $y_1, y_2, \dots, y_n$ ($1 \leqslant y_i \leqslant 10^9$).

It is guaranteed that the sum of the values of $n$ across all test cases does not exceed $2 \cdot 10^5$.

中文翻译

每组测试包含多个测试用例。第一行包含一个整数 $t$（$1 \leqslant t \leqslant 10^4$）——测试用例的数量。测试用例的描述如下。

每个测试用例的第一行包含五个整数 $n$、$Ax$、$Ay$、$Bx$、$By$（$1 \leqslant n \leqslant 2 \cdot 10^5$，$1 \leqslant Ax, Ay, Bx, By \leqslant 10^9$）——待配送房屋的数量以及起点和终点的坐标。

每个测试用例的第二行包含 $n$ 个整数 $x_1, x_2, \dots, x_n$（$Ax < x_i < Bx$）。

每个测试用例的第三行包含 $n$ 个整数 $y_1, y_2, \dots, y_n$（$1 \leqslant y_i \leqslant 10^9$）。

保证所有测试用例中 $n$ 的值的总和不超过 $2 \cdot 10^5$。

输出描述

English

For each test case, output a single integer on a separate line — the minimum time required for pizza delivery.

中文翻译

对于每个测试用例，在单独的一行上输出一个整数——即送披萨所需的最短时间。

样例

Input

4
1 2 3 5 2
4
4
3 1 3 5 2
3 4 3
5 4 1
6 1 2 7 3
5 2 3 5 5 3
6 4 3 1 4 1
5 6 9 8 6
7 7 7 7 7
3 1 8 8 3

output

6
13
19
15

题解

每一次做决策实际上只和 $y$ 的极端值与上一次走到的位置有关，而且方向只有三个方向，对于 $x$ 来说就是不走回头路，那么我们考虑对 $(x_i,y_i)$ 按照 $x_i$ 的大小进行从小到大结构化排序。

其次，对于在同一个 $x$ 坐标下的几个点位 $(x,y_1),(x,y_2),(x,y_3)$，那么我们对 $y_i$ 从小到大排序，设 $y_1\leqslant y_2\leqslant y_3$，那么我们根据上一次进入的 $y_p$ 计算跑到 $y_1,y_3$ 的最短距离和，即计算

$$d=\min\{\left | y_1-y_3 \right | +\left | y_p-y_1 \right | ,\left | y_1-y_3 \right | +\left | y_p-y_3 \right | \}$$

但是 $y_1$ 和 $y_3$ 会影响下一个 $y_p$ 的取值，所以我们需要分别计算并记录到 $y_1$ 和 $y_3$，并为下一次决策的 $y_p$ 提供两种方向，我们简化思维模型，设 $dp[i][0]$ 表示从 $0\sim i$ 到 $x_i$ 的最低点 $y_\ell$ 所获得的最大值。$dp[i][1]$ 表示从 $0\sim i$ 到 $x_i$ 的最高点 $y_h$ 所获得的最大值。那么就有下面的转移方程成立：

$$dp[i][0] = \min(dp[i - 1][0] + d(h_{i-1}, \ell_i), dp[i - 1][1] + d(\ell_{i-1}, \ell_i)) + d(\ell_i, h_i);\\ dp[i][1] = \min(dp[i - 1][0] + d(h_{i-1}, h_i), dp[i - 1][1] + d(\ell_{i-1}, h_i)) + d(h_i, \ell_i);$$

边界条件为 $dp[0][0] = 0$ 和 $dp[0][1] = 0$，其中 $d(a,b)$ 表示 $a\rightarrow b$ 的距离。时间复杂度为 $O(n\log 2n)$

贡献者

Timothy Starman

版权所有

版权归属：Timothy Starman

许可证：署名-非商业性-相同方式共享 4.0 国际 (CC-BY-NC-SA-4.0)

编辑此页

上一页CFR 1074 div4 题解

下一页CFR 1077 div1-2 题解