102474: [AtCoder]ABC247 E - Max Min
Memory Limit：256 MB
Time Limit：2 S
Judge Style：Text Compare
Creator：
Submit：0
Solved：0
Description
Score : $500$ points
Problem Statement
We have a number sequence $A = (A_1, A_2, \dots, A_N)$ of length $N$ and integers $X$ and $Y$. Find the number of pairs of integers $(L, R)$ satisfying all the conditions below.
- $1 \leq L \leq R \leq N$
- The maximum value of $A_L, A_{L+1}, \dots, A_R$ is $X$, and the minimum is $Y$.
Constraints
- $1 \leq N \leq 2 \times 10^5$
- $1 \leq A_i \leq 2 \times 10^5$
- $1 \leq Y \leq X \leq 2 \times 10^5$
- All values in input are integers.
Input
Input is given from Standard Input in the following format:
$N$ $X$ $Y$ $A_1$ $A_2$ $\dots$ $A_N$
Output
Print the answer.
Sample Input 1
4 3 1 1 2 3 1
Sample Output 1
4
$4$ pairs satisfy the conditions: $(L,R)=(1,3),(1,4),(2,4),(3,4)$.
Sample Input 2
5 2 1 1 3 2 4 1
Sample Output 2
0
No pair $(L,R)$ satisfies the condition.
Sample Input 3
5 1 1 1 1 1 1 1
Sample Output 3
15
It may hold that $X=Y$.
Sample Input 4
10 8 1 2 7 1 8 2 8 1 8 2 8
Sample Output 4
36
Input
题意翻译
给定数列 $ A_n $，给定 $ X, Y $，我们定义数对 $ (L, R) $ 满足 $ 1 \le L \le R \le n $，且数列 $ A_L, A_{L + 1}, \cdots, A_R $ 满足最大值为 $ X $，最小值为 $ Y $，求有多少种满足条件的数对。Output
分数：500分
问题描述
我们有一个长度为 $N$ 的数字序列 $A = (A_1, A_2, \dots, A_N)$，以及整数 $X$ 和 $Y$。找出满足以下所有条件的整数对 $(L, R)$ 的数量。
- $1 \leq L \leq R \leq N$
- $A_L, A_{L+1}, \dots, A_R$ 的最大值为 $X$，最小值为 $Y$。
约束条件
- $1 \leq N \leq 2 \times 10^5$
- $1 \leq A_i \leq 2 \times 10^5$
- $1 \leq Y \leq X \leq 2 \times 10^5$
- 输入中的所有值都是整数。
输入
输入从标准输入以以下格式给出：
$N$ $X$ $Y$ $A_1$ $A_2$ $\dots$ $A_N$
输出
打印答案。
样例输入 1
4 3 1 1 2 3 1
样例输出 1
4
有 $4$ 对满足条件的 $(L,R)$：$(L,R)=(1,3),(1,4),(2,4),(3,4)$。
样例输入 2
5 2 1 1 3 2 4 1
样例输出 2
0
没有满足条件的 $(L,R)$ 对。
样例输入 3
5 1 1 1 1 1 1 1
样例输出 3
15
可能满足 $X=Y$。
样例输入 4
10 8 1 2 7 1 8 2 8 1 8 2 8
样例输出 4
36