当前你的浏览器版本过低,网站已在兼容模式下运行,兼容模式仅提供最小功能支持,网站样式可能显示不正常。
请尽快升级浏览器以体验网站在线编辑、在线运行等功能。

建议使用的浏览器:

谷歌Chrome 火狐Firefox Opera浏览器 微软Edge浏览器 QQ浏览器 360浏览器 傲游浏览器

7160:DOS Card

题目描述
DOS is a new single-player game that Kayzin came up with. At the beginning of the game you will be given n cards in a row, each with the number of value $a_i$.

In each "matching" operation you can choose any two cards (we assume that the subscripts of these two cards are $i,j (i < j)$. **Notice that $i$ is less than $j$**), and you will get a score of $(a_i+a_j)×(a_i-a_j)$.

Kayzin will ask you $m$ times. In the k-th query, you need to select four cards from the cards with subscripts $L_k$ to $R_k$, and "match" these four cards into two pairs (i.e., two matching operations, but the subscripts of the cards selected in the two matching operations must be different from each other. That is, a card can only be matched at most once. e.g., if you select four tickets with subscripts $a$, $b$, $c$, and $d$, matching $a$ with $b$ and $c$ with $d$, or matching $a$ with $c$ and $b$ with $d$ are legal, but matching $a$ with $b$ and $b$ with $c$ is not legal), please calculate the maximum value of the sum of the two matching scores.

Note that the queries are independent of each other.
输入解释
The first line contains an integer $T(T≤100)$ . Then $T$ test cases follow. For one case,

The first line contains two integer $n$ $(4≤n≤2×10^5)$ and $m$ $(1≤m≤10^5)$ , $n$ denotes the total number of cards , $m$ denotes the number of times Kayzin queries.

The second line contains $n$ integers $a_1,a_2,…,a_n$ $(1≤a_i≤10^8)$, denotes the value of each card.

The next $m$ lines contain Kayzin's queries. The $k$th line has two numbers, $L_k$ and $R_k$ $(1≤L_k≤R_k≤n)$, the input guarantees that $R_k-L_k≥3$.

It is guaranteed that the sum of $n$ over all test cases doesn't exceed $2×10^5$ and the sum of $m$ over all test cases doesn't exceed $2×10^5$.
输出解释
Print $m$ integer for each case, indicating the maximum scores that can be obtained by selecting four cards (two matching pairs)
输入样例
1
5 3
5 3 2 8 4
1 5
1 4
2 5
输出样例
69
-34
53

该题目是Virtual Judge题目,来自 杭电HDUOJ

源链接: HDU-7160

最后修改于 2022-09-15T06:17:06+00:00 由爬虫自动更新

共提交 0

通过率 --%
时间上限 内存上限
4000/2000MS(Java/Others) 524288/524288K(Java/Others)