Codeforces Round #496 (Div. 3 ) E1. Median on Segments (Permutations Edition)（中位数计数）

E1. Median on Segments (Permutations Edition)

time limit per test

3 seconds

memory limit per test

256 megabytes

input

standard input

output

standard output

You are given a permutation ${\mathrm{p1,p2,\dots ,pnp1,p2,\dots ,pn.\; A\; permutation\; of\; length nn is\; a\; sequence\; such\; that\; each\; integer\; between 11 and nn occurs\; exactly\; once\; in\; the\; sequence.}}^{}$

Find the number of pairs of indices $(l,r)(l,r) (1\le l\le r\le n1\le l\le r\le n)\; such\; that\; the\; value\; of\; the\; median\; of pl,pl+1,\dots ,prpl,pl+1,\dots ,pr is\; exactly\; the\; given\; number mm.$

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 $\mathrm{a=[4,2,7,5]a=[4,2,7,5] then\; its\; median\; is 44 since\; after\; sorting\; the\; sequence,\; it\; will\; look\; like [2,4,5,7][2,4,5,7] and\; the\; left\; of\; two\; middle\; elements\; is\; equal\; to 44.\; The\; median\; of [7,1,2,9,6][7,1,2,9,6] equals 66 since\; after\; sorting,\; the\; value 66 will\; be\; in\; the\; middle\; of\; the\; sequence.}$

Write a program to find the number of pairs of indices $(l,r)(l,r) (1\le l\le r\le n1\le l\le r\le n)\; such\; that\; the\; value\; of\; the\; median\; of pl,pl+1,\dots ,prpl,pl+1,\dots ,pr is\; exactly\; the\; given\; number mm.$

Input

The first line contains integers $\mathrm{nn and mm (1\le n\le 2\cdot 1051\le n\le 2\cdot 105, 1\le m\le n1\le m\le n)\; —\; the\; length\; of\; the\; given\; sequence\; and\; the\; required\; value\; of\; the\; median.}$

The second line contains a permutation ${\mathrm{p1,p2,\dots ,pnp1,p2,\dots ,pn (1\le pi\le n1\le pi\le n).\; Each\; integer\; between 11 and nn occurs\; in pp exactly\; once.}}^{}$

Output

Print the required number.

Examples

input

Copy

复制代码5 42 4 5 3 1

1
5 4
2 4 5 3 1

output

Copy

复制代码4

1
4

input

Copy

复制代码5 51 2 3 4 5

1
5 5
1 2 3 4 5

output

Copy

复制代码1

1
1

input

Copy

复制代码15 81 15 2 14 3 13 4 8 12 5 11 6 10 7 9

1
15 8
1 15 2 14 3 13 4 8 12 5 11 6 10 7 9

output

Copy

复制代码48

1
48

Note 

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

 

 

题意：给出n个数，中位数m，求在这n个数中的任意区间内中位数是n的个数，区间个数是偶数的时候去左边的为 中位数

解题思路：刚开始我以为这是主席树的模板题，第k大,后来听别人说不用这么复杂，因为是n个数互不重复1-n，因为要求的区间里面肯定包含了m，所以我们先求出m的位置，然后我们仔细想 

可以得知在这个区间里面要使中位数是m的话，奇数区间大于m的个数与小于m的个数是一样的，偶数区间是大于m的个数比小于m的个数多1，所以我们用map记录比m大和小的个数，我们先从

m的位置从右边遍历求出区间大于小于m的情况，用map 存大于m和小于m的差值，这样比较方便，比如mp[0]=1,说明右边大于m和小于m的区间个数相等的区间有1个，比如mp[-1]=2,说明右边

大于m比小于m少一个的区间个数有2个，以此类推，然后我们再此遍历左边，如果左边大于m的个数是1的话，奇数区间那么我就要右边小于m的个数为1，也就是mp[-1],偶数区间就要右边大于m

小于m个数相等，也就是mp[0],从而推出式子  cnt记录大于小于m的个数 sum=sum+mp[-cnt]+mp[1-cnt];

复制代码#include<cstdio> #include<iostream> #include<map> using namespace std; typedef long long ll; int main() { map<ll,ll> mp; ll m,n,a[200005]; cin>>n>>m; int pos; for(int i=0;i<n;i++) { cin>>a[i]; if(a[i]==m) pos=i; } int cnt=0; for(int i=pos;i<n;i++) { if(a[i]>m) cnt++; if(a[i]<m) cnt--; mp[cnt]++; } ll sum=0; cnt=0; for(int i=pos;i>=0;i--) { if(a[i]>m) cnt++; if(a[i]<m) cnt--; sum=sum+mp[-cnt]+mp[1-cnt]; } cout<<sum; }

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
#include<cstdio>
#include<iostream>
#include<map>
using namespace std;
typedef long long ll;
int main()
{
    map<ll,ll> mp;
    ll m,n,a[200005];
    cin>>n>>m;
    int pos;
    for(int i=0;i<n;i++)
    {
        cin>>a[i];
        if(a[i]==m)
        pos=i;
    }
    int cnt=0;
    for(int i=pos;i<n;i++)
    {
        if(a[i]>m) cnt++;
        if(a[i]<m) cnt--;
        mp[cnt]++;
    }
    ll sum=0;
    cnt=0;
    for(int i=pos;i>=0;i--)
    {
        if(a[i]>m) cnt++;
        if(a[i]<m) cnt--;
        sum=sum+mp[-cnt]+mp[1-cnt];
    }
    cout<<sum;
}