P3352 [ZJOI2016] Segment Tree

Little Yuuka encountered a problem: given a sequence $a_1, a_2, \ldots, a_n$ and $q$ operations. In each operation, choose an interval $[l, r]$ and set all numbers in that interval to the maximum value within the interval. After all operations, what is the final value of each number? Little Yuuka quickly solved this using a segment tree. Then the wise Little Yuuka wondered: what if the operations are random? That is, in each of the $q$ operations, we choose an interval $[l, r]$ uniformly at random among all intervals with $1 \leq l \leq r \leq n$, and then set all numbers in that interval to the interval maximum (note that there are $\frac{n(n+1)}{2}$ such intervals). What is the expected final value of each number? Little Yuuka loves randomness, so the input sequence is also random (see Constraints and conventions in the Hint). For each position, output its expectation multiplied by $\left(\frac{n(n+1)}{2} \right)^q$, then taken modulo $10^9+7$.

The first line contains two positive integers $n, q$, the number of elements in the sequence and the number of operations. The second line contains $n$ non-negative integers $a_1, a_2, \ldots, a_n$.

Output a single line containing $n$ integers, the answer for each position.

For all testdata, the values in the sequence are at most $10^9$, and each number is a random integer between $0$ and $10^9$. | Test point ID | $n$ | $q$ | |:-:|:-:|:-:| | 1 | $\leq 5$ | $\leq 5$ | | 2 | $\leq 8$ | $\leq 400$ | | 3 | $\leq 12$ | $\leq 400$ | | 4 | $\leq 30$ | $\leq 400$ | | 5 | $\leq 50$ | $\leq 400$ | | 6 | $\leq 100$ | $\leq 400$ | | 7 | $\leq 100$ | $\leq 400$ | | 8 | $\leq 400$ | $\leq 400$ | | 9 | $\leq 400$ | $\leq 400$ | | 10 | $\leq 400$ | $\leq 400$ | Translated by ChatGPT 5