基础函数练习题

YSGH is our red sun.

YSGH 有一个 $1 \sim n$ 的排列 $p$ 和一个长度为 $n$ 的整数序列 $w$。 定义： $$ F(l, r) = \begin{cases} \max(F(l, m - 1), F(m + 1, r)) + w_m & , l \le r \\ 0 & , l > r \end{cases} $$ 其中 $m$ 为 $p$ 的区间 $[l, r]$ 的最大值的下标。 $q$ 次询问 $F(l, r)$ 的值。

第一行两个正整数 $n, q$，意义同题目描述。 第二行共 $n$ 个正整数，第 $i$ 个表示 $p_i$，意义同题目描述。 第三行共 $n$ 个整数，第 $i$ 个表示 $w_i$，意义同题目描述。 接下来共 $q$ 行，每行两个正整数 $l, r$（$1 \le l \le r \le n$），表示询问 $F(l,r)$。

输出共 $q$ 行，每行一个整数，表示答案。

5 2
2 1 5 3 4
2 5 1 2 4
3 5
1 1

7
2

**本题采用捆绑测试。** - Subtask 1（10 points）：$n, q \le 5 \times {10}^3$。 - Subtask 2（10 points）：保证 $p$ 是随机的。 - 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）：无特殊限制。 对于 $100\%$ 的数据，$1 \le n, q \le 5 \times {10}^5$，$|w_i| \le 10^9$，$1 \le p_i \le n$，保证 $p$ 是一个 $1 \sim n$ 的排列。