P5654 Basic Function Practice Problem

YSGH is our red sun.

YSGH has a permutation $p$ of $1 \sim n$ and an integer sequence $w$ of length $n$. Define: $$ F(l, r) = \begin{cases} \max(F(l, m - 1), F(m + 1, r)) + w_m & , l \le r \\ 0 & , l > r \end{cases} $$ where $m$ is the index of the maximum value of $p$ in the interval $[l, r]$. There are $q$ queries asking for the value of $F(l, r)$.

The first line contains two positive integers $n, q$, with the same meaning as in the statement. The second line contains $n$ positive integers. The $i$-th integer is $p_i$, with the same meaning as in the statement. The third line contains $n$ integers. The $i$-th integer is $w_i$, with the same meaning as in the statement. The next $q$ lines each contain two positive integers $l, r$ ($1 \le l \le r \le n$), representing a query for $F(l, r)$.

Output $q$ lines. Each line contains one integer, which is the answer.

**This problem uses bundled testdata.** - Subtask 1 (10 points): $n, q \le 5 \times {10}^3$. - Subtask 2 (10 points): It is guaranteed that $p$ is random. - Subtask 3 (20 points): $n, q \le 5 \times {10}^4$. - Subtask 4 (20 points): $n, q \le {10}^5$. - Subtask 5 (20 points): $w_i \ge 0$. - Subtask 6 (20 points): No special constraints. For $100\%$ of the data, $1 \le n, q \le 5 \times {10}^5$, $|w_i| \le 10^9$, $1 \le p_i \le n$. It is guaranteed that $p$ is a permutation of $1 \sim n$. Translated by ChatGPT 5