P15347 [TOIP 2025] Superposition Maximum Value

In a positive integer array or subarray, for each distinct number, multiply the number by its number of occurrences; this is called its superposition value. A “subarray” means a part of an array made up of consecutive elements. For example, in the array $[4, 5, 2, 3, 4, 2, 2]$, the superposition value of $5$ is $5\times1=5$, the superposition value of $4$ is $4\times2=8$, the superposition value of $3$ is $3\times1=3$, and the superposition value of $2$ is $2\times3=6$. Given a positive integer array of length $n$ and a positive integer $k$, this problem asks for the maximum superposition value in every subarray of length $k$. There are $n-k+1$ subarrays of length $k$ in total. Output the sum of these $n-k+1$ maximum superposition values. For example, the input array is $[4, 5, 2, 3, 4, 2, 2, 5]$, with $n=8$ and $k=5$. The maximum superposition values of each subarray are: * For $[4, 5, 2, 3, 4]$, the maximum superposition value is $4\times2=8$. * For $[5, 2, 3, 4, 2]$, the maximum superposition value is $5\times1=5$. * For $[2, 3, 4, 2, 2]$, the maximum superposition value is $2\times3=6$. * For $[3, 4, 2, 2, 5]$, the maximum superposition value is $5\times1=5$. The sum of all maximum superposition values is $8+5+6+5=24$.

$$ \begin{aligned} &n \; k \\ &c_0 \; c_1 \; \cdots \; c_{n-1} \end{aligned} $$ - $n$ is the length of the array. - $k$ is the required subarray length. - $c_i$ is the $i$-th positive integer in the array.

$X$ - $X$ is the sum of all maximum superposition values.

### Constraints * $1 \le n\le 10^5$. * $1 \le k \le n$. * $1 \le c_i < 2^{31}$. ### Scoring This problem has three subtasks with the following constraints. Each subtask may contain one or more testdata files. You will get the score for a subtask only if you answer all testdata in that subtask correctly. | Subtask | Score | Additional Input Constraints | | :-----: | :---: | ---------------------------- | | 1 | 6 | The input satisfies $N \le 1000$, and $c_i \le 10^6$. | | 2 | 38 | The input satisfies that all numbers in the array are pairwise distinct. | | 3 | 56 | No additional constraints. | Translated by ChatGPT 5