English · Original
Chinese · Translation
Formal · Original
You are given a permutation $p_1, p_2, \dots, p_n$. A permutation of length $n$ is a sequence such that each integer between $1$ and $n$ occurs exactly once in the sequence.
Find the number of pairs of indices $(l, r)$ ($1 \le l \le r \le n$) such that the value of the median of $p_l, p_{l+1}, \dots, p_r$ is exactly the given number $m$.
The median of a sequence is the value of the element which is in the middle of the sequence after sorting it in non-decreasing order. If the length of the sequence is even, the left of two middle elements is used.
For example, if $a=[4, 2, 7, 5]$ then its median is $4$ since after sorting the sequence, it will look like $[2, 4, 5, 7]$ and the left of two middle elements is equal to $4$. The median of $[7, 1, 2, 9, 6]$ equals $6$ since after sorting, the value $6$ will be in the middle of the sequence.
Write a program to find the number of pairs of indices $(l, r)$ ($1 \le l \le r \le n$) such that the value of the median of $p_l, p_{l+1}, \dots, p_r$ is exactly the given number $m$.
## Input
The first line contains integers $n$ and $m$ ($1 \le n \le 2\cdot10^5$, $1 \le m \le n$) — the length of the given sequence and the required value of the median.
The second line contains a permutation $p_1, p_2, \dots, p_n$ ($1 \le p_i \le n$). Each integer between $1$ and $n$ occurs in $p$ exactly once.
## Output
Print the required number.
[samples]
## Note
In the first example, the suitable pairs of indices are: $(1, 3)$, $(2, 2)$, $(2, 3)$ and $(2, 4)$.
你被给定一个排列 $p_1, p_2, dots.h, p_n$。长度为 $n$ 的排列是一个序列，其中每个介于 $1$ 到 $n$ 之间的整数恰好出现一次。
求满足条件的下标对 $(l, r)$（$1 lt.eq l lt.eq r lt.eq n$）的数量，使得子序列 $p_l, p_(l + 1), dots.h, p_r$ 的中位数恰好等于给定的数 $m$。
一个序列的中位数是将序列按非递减顺序排序后位于中间位置的元素的值。如果序列长度为偶数，则使用两个中间元素中靠左的那个。
例如，若 $a = [ 4, 2, 7, 5 ]$，则其中位数为 $4$，因为排序后序列为 $[ 2, 4, 5, 7 ]$，两个中间元素中靠左的是 $4$。序列 $[ 7, 1, 2, 9, 6 ]$ 的中位数为 $6$，因为排序后 $6$ 位于序列中间。
编写一个程序，求满足条件的下标对 $(l, r)$（$1 lt.eq l lt.eq r lt.eq n$）的数量，使得子序列 $p_l, p_(l + 1), dots.h, p_r$ 的中位数恰好等于给定的数 $m$。
第一行包含两个整数 $n$ 和 $m$（$1 lt.eq n lt.eq 2 dot.op 10^5$，$1 lt.eq m lt.eq n$）——给定序列的长度和所需的中位数值。
第二行包含一个排列 $p_1, p_2, dots.h, p_n$（$1 lt.eq p_i lt.eq n$）。每个介于 $1$ 到 $n$ 之间的整数在 $p$ 中恰好出现一次。
请输出所需的数量。
在第一个例子中，符合条件的下标对为：$(1, 3)$、$(2, 2)$、$(2, 3)$ 和 $(2, 4)$。
## Input
第一行包含两个整数 $n$ 和 $m$（$1 lt.eq n lt.eq 2 dot.op 10^5$，$1 lt.eq m lt.eq n$）——给定序列的长度和所需的中位数值。第二行包含一个排列 $p_1, p_2, dots.h, p_n$（$1 lt.eq p_i lt.eq n$）。每个介于 $1$ 到 $n$ 之间的整数在 $p$ 中恰好出现一次。
## Output
请输出所需的数量。
[samples]
## Note
在第一个例子中，符合条件的下标对为：$(1, 3)$、$(2, 2)$、$(2, 3)$ 和 $(2, 4)$。
**Definitions**
Let $ n \in \mathbb{Z}^+ $ be the length of the permutation.
Let $ m \in \{1, 2, \dots, n\} $ be the target median value.
Let $ P = (p_1, p_2, \dots, p_n) $ be a permutation of $ \{1, 2, \dots, n\} $.
For any contiguous subsequence $ P[l:r] = (p_l, p_{l+1}, \dots, p_r) $ with $ 1 \leq l \leq r \leq n $, define its **median** as the $ \left\lceil \frac{r - l + 1}{2} \right\rceil $-th smallest element in the sorted version of $ P[l:r] $.
**Constraints**
1. $ 1 \leq n \leq 2 \cdot 10^5 $
2. $ 1 \leq m \leq n $
3. $ P $ is a permutation of $ \{1, 2, \dots, n\} $
**Objective**
Count the number of pairs $ (l, r) $ with $ 1 \leq l \leq r \leq n $ such that the median of $ P[l:r] $ is exactly $ m $.
API Response (JSON)
{
"problem": {
"name": "E1. Median on Segments (Permutations Edition)",
"description": {
"content": "You are given a permutation $p_1, p_2, \\dots, p_n$. A permutation of length $n$ is a sequence such that each integer between $1$ and $n$ occurs exactly once in the sequence. Find the number of pairs ",
"description_type": "Markdown"
},
"platform": "Codeforces",
"limit": {
"time_limit": 3000,
"memory_limit": 262144
},
"difficulty": "None",
"is_remote": true,
"is_sync": true,
"sync_url": null,
"sign": "CF1005E1"
},
"statements": [
{
"statement_type": "Markdown",
"content": "You are given a permutation $p_1, p_2, \\dots, p_n$. A permutation of length $n$ is a sequence such that each integer between $1$ and $n$ occurs exactly once in the sequence.\n\nFind the number of pairs ...",
"is_translate": false,
"language": "English"
},
{
"statement_type": "Markdown",
"content": "你被给定一个排列 $p_1, p_2, dots.h, p_n$。长度为 $n$ 的排列是一个序列，其中每个介于 $1$ 到 $n$ 之间的整数恰好出现一次。\n\n求满足条件的下标对 $(l, r)$（$1 lt.eq l lt.eq r lt.eq n$）的数量，使得子序列 $p_l, p_(l + 1), dots.h, p_r$ 的中位数恰好等于给定的数 $m$。\n\n一个序列的中位数是将序列按...",
"is_translate": true,
"language": "Chinese"
},
{
"statement_type": "Markdown",
"content": "**Definitions** \nLet $ n \\in \\mathbb{Z}^+ $ be the length of the permutation. \nLet $ m \\in \\{1, 2, \\dots, n\\} $ be the target median value. \nLet $ P = (p_1, p_2, \\dots, p_n) $ be a permutation of $...",
"is_translate": false,
"language": "Formal"
}
]
}