Div3 codeforces1005E1 Median on Segments (Permutations Edition)

93 阅读 0 评论 62 点赞

我是靠谱客的博主斯文冥王星，最近开发中收集的这篇文章主要介绍Div3 codeforces1005E1 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)$

题意：给你n个数和一个m，为你有多少个l，r，即l到r区间，有多少个这样的区间，使m成为这个区间序列的中位数。

思路：把m的左边序列做一下预处理，利用前缀和处理出大于m的个数与小于m的个数之差，即小于m的个数减去大于m的个数，（可以把大于m的变成1，小于m的变成-1，然后计和）然后因为当区间数是偶数的时候，他要取得是中间两个数右边的一个，这个时候当大于m的个数 = 小于m的个数 + 1的也应该成立，所以数列左侧的答案，有mm[0]和mm[-1]，然后遍历右边，当序列的大于m的个数减去小于m的个数的时候，看看map里面的mm是否存在这个差值，如果存在的话，左右的差值是不是就可以抵消了，还有就是偶数的情况，所以我们要在考虑两个相差1的时候（还有就是结果要long long）

代码如下：

#include <bits/stdc++.h>

using namespace std;

const int maxn = 1e6 + 100;
int n,m;
int a[maxn];
int d[maxn];
map<int,int>mm;
int s[maxn];
int main() {
    while(~scanf("%d%d",&n,&m)) {
        mm.clear();
        int m1 = 0,m2 = 0;
        memset(d,0,sizeof(d));
        int id;
        mm[0] = 1;
        for(int i = 0; i < n; i++) {
            scanf("%d",&a[i]);
            if(a[i] == m) id = i;
            if(a[i] < m) d[i] = -1;
            else if(a[i] > m) d[i] = 1;
        }
        s[0] = d[0];
        for(int i = 1; i < n; i++)
            s[i] = s[i - 1] + d[i];
        for(int i = 0; i < n; i++)
            if(i < id)
                mm[-(s[id] - s[i - 1])]++;
        m1 = 0,m2 = 0;
        long long  ans = mm[-1] + mm[0]; 
        for(int i = id + 1; i < n; i++) 
            if(a[i] < m) m1++;
            else if(a[i] > m) m2++;
            ans += mm[m2 - m1] + mm[m2 - m1 - 1]; 
        
        cout << ans << endl;
    }
    return 0;
}