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<=r$}\\0&\text{else}\end{cases}$$ ## 输入输出格式 ### 输入格式： 第一行两个整数$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$个整数，表示每一次询问的答案。

题目描述

You are given a permutation $ p_1, p_2, \dots, p_n $ . You should answer $ q $ queries. Each query is a pair $ (l_i, r_i) $ , and you should calculate $ f(l_i, r_i) $ . Let's denote $ m_{l, r} $ as the position of the maximum in subsegment $ p_l, p_{l+1}, \dots, p_r $ . Then $ f(l, r) = (r - l + 1) + f(l, m_{l,r} - 1) + f(m_{l,r} + 1, r) $ if $ l \le r $ or $ 0 $ otherwise.

输入输出格式

输入格式

The first line contains two integers $ n $ and $ q $ ( $ 1 \le n \le 10^6 $ , $ 1 \le q \le 10^6 $ ) — the size of the permutation $ p $ and the number of queries. The second line contains $ n $ pairwise distinct integers $ p_1, p_2, \dots, p_n $ ( $ 1 \le p_i \le n $ , $ p_i \neq p_j $ for $ i \neq j $ ) — permutation $ p $ . The third line contains $ q $ integers $ l_1, l_2, \dots, l_q $ — the first parts of the queries. The fourth line contains $ q $ integers $ r_1, r_2, \dots, r_q $ — the second parts of the queries. It's guaranteed that $ 1 \le l_i \le r_i \le n $ for all queries.

输出格式

Print $ q $ integers — the values $ f(l_i, r_i) $ for the corresponding queries.

输入输出样例

输入样例 #1

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

输出样例 #1

1 6 8 5 1 

说明

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 $ .