309618: CF1707E. Replace
Memory Limit:1024 MB
Time Limit:1 S
Judge Style:Text Compare
Creator:
Submit:0
Solved:0
Description
Replace
题意翻译
### 题目描述 给定一个长为 $n$ 的序列 $a_1,\ldots,a_n$,其中对于任意的 $i$ 满足 $1 \leq a_i \leq n$。 定义一个二元组函数如下: $$f((l,r))=(\min\{a_l,\ldots,a_r\},\max\{a_l,\ldots,a_r\})(l \leq r)$$ 你需要回答 $q$ 次询问,每次给定 $(l_i,r_i)$,问其最少经过多少次 $f$ 的调用(即 $(l,r) \rightarrow f((l,r))$)使得 $(l_i,r_i)$ 变成 $(1,n)$,若无解请输出 `-1`。 ### 输入格式 第一行包含两个整数 $n,q(1 \leq n,q \leq 10^5)$,表示序列长度和询问次数。 第二行包含 $n$ 个整数 $a_i(1 \leq a_i \leq n)$,表示序列 $a$。 接下来 $q$ 行每行两个整数 $l_i,r_i(1 \leq l_i \leq r_i \leq n)$,表示每组询问。 ### 输出格式 对每一个询问,输出其最小次数,或无解输出 `-1`。 ### 样例解释 第一个样例中,$a=\{2,5,4,1,3\}$。 对于第一个询问,$(4,4) \rightarrow (1,1) \rightarrow (2,2) \rightarrow (5,5) \rightarrow (3,3) \rightarrow (4,4) \rightarrow \cdots$,故无解。 对于第二个询问,已经有 $(l_i,r_i)=(1,n)$,需要 $0$ 次。 对于第三个询问,$(1,4) \rightarrow (1,5)$,需要 $1$ 次。 对于第四个询问,$(3,5) \rightarrow (1,4) \rightarrow (1,5)$,需要 $2$ 次。 对于第五个询问,$(4,5) \rightarrow (1,3) \rightarrow (2,5) \rightarrow (1,5)$,需要 $3$ 次。 对于第六个询问,$(2,3) \rightarrow (4,5) \rightarrow (1,3) \rightarrow (2,5) \rightarrow (1,5)$,需要 $4$ 次。题目描述
You are given an integer array $ a_1,\ldots, a_n $ , where $ 1\le a_i \le n $ for all $ i $ . There's a "replace" function $ f $ which takes a pair of integers $ (l, r) $ , where $ l \le r $ , as input and outputs the pair $ $f\big( (l, r) \big)=\left(\min\{a_l,a_{l+1},\ldots,a_r\},\, \max\{a_l,a_{l+1},\ldots,a_r\}\right). $ $ </p><p>Consider repeated calls of this function. That is, from a starting pair $ (l, r) $ we get $ f\\big((l, r)\\big) $ , then $ f\\big(f\\big((l, r)\\big)\\big) $ , then $ f\\big(f\\big(f\\big((l, r)\\big)\\big)\\big) $ , and so on.</p><p>Now you need to answer $ q $ queries. For the $ i $ -th query you have two integers $ l\_i $ and $ r\_i $ ( $ 1\\le l\_i\\le r\_i\\le n $ ). You must answer the minimum number of times you must apply the "replace" function to the pair $ (l\_i,r\_i) $ to get $ (1, n)$, or report that it is impossible.输入输出格式
输入格式
The first line contains two positive integers $ n $ , $ q $ ( $ 1\le n,q\le 10^5 $ ) — the length of the sequence $ a $ and the number of the queries. The second line contains $ n $ positive integers $ a_1,a_2,\ldots,a_n $ ( $ 1\le a_i\le n $ ) — the sequence $ a $ . Each line of the following $ q $ lines contains two integers $ l_i $ , $ r_i $ ( $ 1\le l_i\le r_i\le n $ ) — the queries.
输出格式
For each query, output the required number of times, or $ -1 $ if it is impossible.
输入输出样例
输入样例 #1
5 6
2 5 4 1 3
4 4
1 5
1 4
3 5
4 5
2 3
输出样例 #1
-1
0
1
2
3
4
输入样例 #2
6 3
2 3 4 6 1 2
5 6
2 5
2 3
输出样例 #2
5
1
3
输入样例 #3
5 3
3 2 2 4 1
2 5
1 3
1 5
输出样例 #3
-1
-1
0
说明
In the first example, $ n=5 $ and $ a=[2,5,4,1,3] $ . For the first query: $ (4,4)\to(1,1)\to(2,2)\to(5,5)\to(3,3)\to(4,4)\to\ldots $ , so it's impossible to get $ (1,5) $ . For the second query, you already have $ (1,5) $ . For the third query: $ (1,4)\to(1,5) $ . For the fourth query: $ (3,5)\to(1,4)\to(1,5) $ . For the fifth query: $ (4,5)\to(1,3)\to(2,5)\to(1,5) $ . For the sixth query: $ (2,3)\to(4,5)\to(1,3)\to(2,5)\to(1,5) $ .Input
题意翻译
### 题目描述 给定一个长为 $n$ 的序列 $a_1,\ldots,a_n$,其中对于任意的 $i$ 满足 $1 \leq a_i \leq n$。 定义一个二元组函数如下: $$f((l,r))=(\min\{a_l,\ldots,a_r\},\max\{a_l,\ldots,a_r\})(l \leq r)$$ 你需要回答 $q$ 次询问,每次给定 $(l_i,r_i)$,问其最少经过多少次 $f$ 的调用(即 $(l,r) \rightarrow f((l,r))$)使得 $(l_i,r_i)$ 变成 $(1,n)$,若无解请输出 `-1`。 ### 输入格式 第一行包含两个整数 $n,q(1 \leq n,q \leq 10^5)$,表示序列长度和询问次数。 第二行包含 $n$ 个整数 $a_i(1 \leq a_i \leq n)$,表示序列 $a$。 接下来 $q$ 行每行两个整数 $l_i,r_i(1 \leq l_i \leq r_i \leq n)$,表示每组询问。 ### 输出格式 对每一个询问,输出其最小次数,或无解输出 `-1`。 ### 样例解释 第一个样例中,$a=\{2,5,4,1,3\}$。 对于第一个询问,$(4,4) \rightarrow (1,1) \rightarrow (2,2) \rightarrow (5,5) \rightarrow (3,3) \rightarrow (4,4) \rightarrow \cdots$,故无解。 对于第二个询问,已经有 $(l_i,r_i)=(1,n)$,需要 $0$ 次。 对于第三个询问,$(1,4) \rightarrow (1,5)$,需要 $1$ 次。 对于第四个询问,$(3,5) \rightarrow (1,4) \rightarrow (1,5)$,需要 $2$ 次。 对于第五个询问,$(4,5) \rightarrow (1,3) \rightarrow (2,5) \rightarrow (1,5)$,需要 $3$ 次。 对于第六个询问,$(2,3) \rightarrow (4,5) \rightarrow (1,3) \rightarrow (2,5) \rightarrow (1,5)$,需要 $4$ 次。Output
**题目大意:**
给定一个长度为 $ n $ 的序列 $ a_1, \ldots, a_n $,其中每个元素 $ a_i $ 满足 $ 1 \leq a_i \leq n $。定义一个二元组函数 $ f $ 如下:
$$
f((l, r)) = (\min\{a_l, \ldots, a_r\}, \max\{a_l, \ldots, a_r\}) \quad (l \leq r)
$$
你需要回答 $ q $ 次询问,每次询问给定一个二元组 $ (l_i, r_i) $,要求计算最少需要调用多少次函数 $ f $,才能使得 $ (l_i, r_i) $ 变为 $ (1, n) $。如果无法通过有限次调用达到目标,则输出 `-1`。
**输入格式:**
第一行包含两个整数 $ n, q $($ 1 \leq n, q \leq 10^5 $),分别表示序列的长度和询问的次数。
第二行包含 $ n $ 个整数 $ a_1, \ldots, a_n $($ 1 \leq a_i \leq n $),表示序列 $ a $ 的元素。
接下来 $ q $ 行,每行包含两个整数 $ l_i, r_i $($ 1 \leq l_i \leq r_i \leq n $),表示每次询问的内容。
**输出格式:**
对于每个询问,输出最少需要调用的次数,如果无解则输出 `-1`。
**样例解释:**
在第一个样例中,序列 $ a = \{2, 5, 4, 1, 3\} $。
- 对于第一个询问 $ (4, 4) $,无论调用多少次函数 $ f $,都无法变为 $ (1, n) $,因此输出 `-1`。
- 对于第二个询问 $ (1, 5) $,已经是最初要求的序列范围,不需要调用函数,输出 `0`。
- 对于第三个询问 $ (1, 4) $,调用一次函数后变为 $ (1, 5) $,输出 `1`。
- 对于第四个询问 $ (3, 5) $,需要调用两次函数才能变为 $ (1, 5) $,输出 `2`。
- 对于第五个询问 $ (4, 5) $,需要调用三次函数才能变为 $ (1, 5) $,输出 `3`。
- 对于第六个询问 $ (2, 3) $,需要调用四次函数才能变为 $ (1, 5) $,输出 `4`。**题目大意:** 给定一个长度为 $ n $ 的序列 $ a_1, \ldots, a_n $,其中每个元素 $ a_i $ 满足 $ 1 \leq a_i \leq n $。定义一个二元组函数 $ f $ 如下: $$ f((l, r)) = (\min\{a_l, \ldots, a_r\}, \max\{a_l, \ldots, a_r\}) \quad (l \leq r) $$ 你需要回答 $ q $ 次询问,每次询问给定一个二元组 $ (l_i, r_i) $,要求计算最少需要调用多少次函数 $ f $,才能使得 $ (l_i, r_i) $ 变为 $ (1, n) $。如果无法通过有限次调用达到目标,则输出 `-1`。 **输入格式:** 第一行包含两个整数 $ n, q $($ 1 \leq n, q \leq 10^5 $),分别表示序列的长度和询问的次数。 第二行包含 $ n $ 个整数 $ a_1, \ldots, a_n $($ 1 \leq a_i \leq n $),表示序列 $ a $ 的元素。 接下来 $ q $ 行,每行包含两个整数 $ l_i, r_i $($ 1 \leq l_i \leq r_i \leq n $),表示每次询问的内容。 **输出格式:** 对于每个询问,输出最少需要调用的次数,如果无解则输出 `-1`。 **样例解释:** 在第一个样例中,序列 $ a = \{2, 5, 4, 1, 3\} $。 - 对于第一个询问 $ (4, 4) $,无论调用多少次函数 $ f $,都无法变为 $ (1, n) $,因此输出 `-1`。 - 对于第二个询问 $ (1, 5) $,已经是最初要求的序列范围,不需要调用函数,输出 `0`。 - 对于第三个询问 $ (1, 4) $,调用一次函数后变为 $ (1, 5) $,输出 `1`。 - 对于第四个询问 $ (3, 5) $,需要调用两次函数才能变为 $ (1, 5) $,输出 `2`。 - 对于第五个询问 $ (4, 5) $,需要调用三次函数才能变为 $ (1, 5) $,输出 `3`。 - 对于第六个询问 $ (2, 3) $,需要调用四次函数才能变为 $ (1, 5) $,输出 `4`。
给定一个长度为 $ n $ 的序列 $ a_1, \ldots, a_n $,其中每个元素 $ a_i $ 满足 $ 1 \leq a_i \leq n $。定义一个二元组函数 $ f $ 如下:
$$
f((l, r)) = (\min\{a_l, \ldots, a_r\}, \max\{a_l, \ldots, a_r\}) \quad (l \leq r)
$$
你需要回答 $ q $ 次询问,每次询问给定一个二元组 $ (l_i, r_i) $,要求计算最少需要调用多少次函数 $ f $,才能使得 $ (l_i, r_i) $ 变为 $ (1, n) $。如果无法通过有限次调用达到目标,则输出 `-1`。
**输入格式:**
第一行包含两个整数 $ n, q $($ 1 \leq n, q \leq 10^5 $),分别表示序列的长度和询问的次数。
第二行包含 $ n $ 个整数 $ a_1, \ldots, a_n $($ 1 \leq a_i \leq n $),表示序列 $ a $ 的元素。
接下来 $ q $ 行,每行包含两个整数 $ l_i, r_i $($ 1 \leq l_i \leq r_i \leq n $),表示每次询问的内容。
**输出格式:**
对于每个询问,输出最少需要调用的次数,如果无解则输出 `-1`。
**样例解释:**
在第一个样例中,序列 $ a = \{2, 5, 4, 1, 3\} $。
- 对于第一个询问 $ (4, 4) $,无论调用多少次函数 $ f $,都无法变为 $ (1, n) $,因此输出 `-1`。
- 对于第二个询问 $ (1, 5) $,已经是最初要求的序列范围,不需要调用函数,输出 `0`。
- 对于第三个询问 $ (1, 4) $,调用一次函数后变为 $ (1, 5) $,输出 `1`。
- 对于第四个询问 $ (3, 5) $,需要调用两次函数才能变为 $ (1, 5) $,输出 `2`。
- 对于第五个询问 $ (4, 5) $,需要调用三次函数才能变为 $ (1, 5) $,输出 `3`。
- 对于第六个询问 $ (2, 3) $,需要调用四次函数才能变为 $ (1, 5) $,输出 `4`。**题目大意:** 给定一个长度为 $ n $ 的序列 $ a_1, \ldots, a_n $,其中每个元素 $ a_i $ 满足 $ 1 \leq a_i \leq n $。定义一个二元组函数 $ f $ 如下: $$ f((l, r)) = (\min\{a_l, \ldots, a_r\}, \max\{a_l, \ldots, a_r\}) \quad (l \leq r) $$ 你需要回答 $ q $ 次询问,每次询问给定一个二元组 $ (l_i, r_i) $,要求计算最少需要调用多少次函数 $ f $,才能使得 $ (l_i, r_i) $ 变为 $ (1, n) $。如果无法通过有限次调用达到目标,则输出 `-1`。 **输入格式:** 第一行包含两个整数 $ n, q $($ 1 \leq n, q \leq 10^5 $),分别表示序列的长度和询问的次数。 第二行包含 $ n $ 个整数 $ a_1, \ldots, a_n $($ 1 \leq a_i \leq n $),表示序列 $ a $ 的元素。 接下来 $ q $ 行,每行包含两个整数 $ l_i, r_i $($ 1 \leq l_i \leq r_i \leq n $),表示每次询问的内容。 **输出格式:** 对于每个询问,输出最少需要调用的次数,如果无解则输出 `-1`。 **样例解释:** 在第一个样例中,序列 $ a = \{2, 5, 4, 1, 3\} $。 - 对于第一个询问 $ (4, 4) $,无论调用多少次函数 $ f $,都无法变为 $ (1, n) $,因此输出 `-1`。 - 对于第二个询问 $ (1, 5) $,已经是最初要求的序列范围,不需要调用函数,输出 `0`。 - 对于第三个询问 $ (1, 4) $,调用一次函数后变为 $ (1, 5) $,输出 `1`。 - 对于第四个询问 $ (3, 5) $,需要调用两次函数才能变为 $ (1, 5) $,输出 `2`。 - 对于第五个询问 $ (4, 5) $,需要调用三次函数才能变为 $ (1, 5) $,输出 `3`。 - 对于第六个询问 $ (2, 3) $,需要调用四次函数才能变为 $ (1, 5) $,输出 `4`。