CF1117G Recursive Queries

有一个长度为 $n$ 的排列 $p_1,p_2,\dots,p_n$，还有 $q$ 次询问，每次询问一段区间 $[l_i, r_i]$，你需要计算出 $f(l_i, r_i)$。 定义 $m_{l, r}$ 表示 $p_l, p_{l+1}, \dots, p_r$ 这一段数列的最大值的出现位置，则 $$f(l, r) =\begin{cases}(r-l+1)+f(l,m_{l,r}-1)+f(m_{l,r}+1,r)&\text{if $l

第一行两个整数 $n$ 和 $q$，表示排列的长度和询问的个数 $(1\le n\le 10^6,1\le q\le 10^6)$。 第二行 $n$ 个整数，表示排列 $p$ 。 第三行 $q$ 个整数，依次表示每一次询问的左端点。 第四行 $q$ 个整数，依次表示每一次询问的右端点。 数据保证 $1\le l_i\le r_i\le n$。

输出一行 $q$ 个整数，表示每一次询问的答案。

Description of the queries: 1. $ f(2, 2) = (2 - 2 + 1) + f(2, 1) + f(3, 2) = 1 + 0 + 0 = 1 $ ; 2. $ f(1, 3) = (3 - 1 + 1) + f(1, 2) + f(4, 3) = 3 + (2 - 1 + 1) + f(1, 0) + f(2, 2) = 3 + 2 + (2 - 2 + 1) = 6 $ ; 3. $ f(1, 4) = (4 - 1 + 1) + f(1, 2) + f(4, 4) = 4 + 3 + 1 = 8 $ ; 4. $ f(2, 4) = (4 - 2 + 1) + f(2, 2) + f(4, 4) = 3 + 1 + 1 = 5 $ ; 5. $ f(1, 1) = (1 - 1 + 1) + 0 + 0 = 1 $ .