[BZOJ1303]&&[CQOI2009] 中位数图

2014-11-07
竞赛题解 / 模拟
BZOJCQOI

描述 Description

给出 1~n 的一个排列，统计该排列有多少个长度为奇数的连续子序列的中位数是 b。中位数是指把所有元素从小到大排列后，位于中间的数。

输入格式 InputFormat

第一行为两个正整数 n 和 b ，第二行为 1~n 的排列。

输出格式 OutputFormat

输出一个整数，即中位数为 b 的连续子序列个数。

样例输入 SampleInput

7 4
5 7 2 4 3 1 6

样例输出 SampleOutput

4

BZOJ 1303

根据大小关系转成 1 和 - 1 串，然后就变成了求区间和为零且包含中位数的区间的个数。

#include <stdio.h>
#include <iostream>
#include <cstring>
#include <algorithm>
#include <cmath>
using namespace std;
#define ll long long
const int maxn=100005;
ll i,j,t,n,m,l,r,k,z,y,x;
ll s,b,ans;
ll a[maxn],sum[maxn],f[2*maxn+5];
int main()
{
    freopen("median.in","r",stdin);
    freopen("median.out","w",stdout);
    ans=0;
    scanf("%lld%lld",&n,&b);
    sum[0]=0;
    for (i=1;i<=n;i++)
    {
        scanf("%lld",&a[i]);
        if (a[i]>b) a[i]=1;
        else if (a[i]<b) a[i]=-1;
        else a[i]=0;
        if (a[i]==0) s=i;
        sum[i]=sum[i-1]+a[i];
    }
    for (i=1;i<=s;i++) f[sum[i-1]+maxn]++;
    for (i=s;i<=n;i++) ans+=(ll)f[sum[i]+maxn];
    printf("%lld\n",ans);
    return 0;
}