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