P6187 [NOI Online #1 Senior] Minimum Cycle

You are given a sequence of positive integers $a_i$ of length $n$, indexed starting from $1$. We view this sequence as a ring where the first and last elements are adjacent. More specifically, for two numbers $a_i$ and $a_j$ with indices $i$, $j$ ($i \leqslant j$), their distance is defined as $\min(j-i, i+n-j)$. Now you are also given $m$ integers $k_1, k_2, \ldots, k_m$. For each $k_i$ ($i=1, 2, \ldots, m$), you need to rearrange the sequence $a_i$ so that the sum of products of every pair of numbers on the ring whose distance is $k_i$ is maximized.

The first line contains two positive integers $n$ and $m$, representing the sequence length and the number of queries. The next line contains $n$ positive integers, representing $a_i$. The next $m$ lines each contain one non-negative integer, representing $k_i$.

Output $m$ lines. Each line contains one integer, representing the answer.

#### Explanation for Sample Input/Output 1 - When $k=0$: the answer is the sum of squares of all numbers. - When $k=1$: one optimal arrangement is $\{3,1,2,4,6,5\}$. The answer is $3 \times 1 + 1 \times 2 + 2 \times 4 + 4 \times 6 + 6 \times 5 + 5 \times 3 = 82$. - When $k=2$: one optimal arrangement is $\{3,6,1,4,2,5\}$. The answer is $3 \times 1 + 1 \times 2 + 2 \times 3 + 6 \times 4 + 4 \times 5 + 5 \times 6 = 85$. - When $k=3$: one valid arrangement is $1,5,3,2,6,4$, and the answer is $88$. Note that the answer here is not $44$. --- #### Constraints and Hints For all testdata: $1 \leqslant m \leqslant n \leqslant 2 \times 10^5$, $0 \leqslant k \leqslant \lfloor n/2\rfloor$, $1 \leqslant a_i \leqslant 10^5$. | Test Point ID | $n \leqslant$ | Special Property | | :--- | :--- | :--- | | 1 | $10$ | None | | 2 | $18$ | None | | 3 | $36$ | $n$ is even and $m=1$, $k=2$ | | 4,5 | $1000$ | $m \leqslant 10$, $k=1$ | | 6 | $50$ | $m \leqslant 10$, $k \leqslant 2$ | | 7,8 | $3000$ | None | | 9,10 | $2 \times 10^5$ | None | Translated by ChatGPT 5