Codeforces Round #496 (Div. 3 ) E1. Median on Segments (Permutations Edition)（思维题）

本文主要是介绍Codeforces Round #496 (Div. 3 ) E1. Median on Segments (Permutations Edition)（思维题），希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

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 \leq l \leq r \leq 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 \leq l \leq r \leq 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 \leq n \leq 2 \cdot 10^{5}$ , $1 \leq m \leq 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 \leq p_{i} \leq n$ ). Each integer between $1$ and $n$ occurs in $p$ exactly once.

Output

Print the required number.

Examples 
input Copy 
5 4
2 4 5 3 1
output Copy 
4
input Copy 
5 5
1 2 3 4 5
output Copy 
1
input Copy 
15 8
1 15 2 14 3 13 4 8 12 5 11 6 10 7 9
output Copy 
48

Note

In the first example, the suitable pairs of indices are: $(1, 3)$ , $(2, 2)$ , $(2, 3)$ and $(2, 4)$ .

题意：给出一串各不相等的的数字，然后给出一个m，问你存在多少个区间使得数字m是这个区间的中位数（如果是奇数就是中间的数，如果是偶数就是中间靠左的那个数）。

思路：要想使得m是某个区间的中位数，那么如果区间是奇数的话，那么必然在这个区间上，比m小的数和比m大的数的个数是相等的。如果区间是偶数的话，那么比m大的数会比m小的数多一个。开一个map分别来存m左边的数比m大和小的个数，和m右边的数比m大和小的个数。

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
int n, m;
const int maxn = 2e5 + 5;
map<int, int>mp;
int pos, a[maxn];
int main() 
{scanf("%d%d", &n, &m);for(int i = 1; i <= n; i++) {scanf("%d", &a[i]);if(a[i] == m) pos = i;}int cnt = 0;for(int i = pos; i <= n; i++) {if(a[i] > m) cnt++;else if(a[i] < m) cnt--;mp[cnt]++;//记录右边比m大和小的情况}ll ans = 0;cnt = 0;for(int i = pos; i >= 1; i--) {if(a[i] > m) cnt++;//记录左边比m大和小的情况else if(a[i] < m) cnt--;//注意会爆int所以用1*LL强制转换ans += 1LL*mp[-cnt];//区间是奇数取最中间ans += 1LL*mp[1 - cnt];//区间是偶数去中间靠左的//如果区间是偶数的话，那么比m大的个数会比m小的个数多一个，所以要加1}printf("%lld\n", ans);return 0;
}

这篇关于Codeforces Round #496 (Div. 3 ) E1. Median on Segments (Permutations Edition)（思维题）的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！