题解 P3031 【[USACO11NOV]高于中位数Above the Median】

huzhaoyang · 2017-08-08 06:46:52 · 题解

其实每一个数都只有2种情况：大于等于x、小于x，我们把第一种情况当成1，第二种情况当成-1，相当于就变成了有多少个和不为负数的子序列，用前缀和解决就是n^2，但还是不行。继续考虑：现在这个问题是要求sum[j]-sum[i-1]>=0，同时加上sum[i-1]后就变成了询问j以前有多少个i满足sum[i]<=sum[j]。由于sum[j]和sum[j-1]最多相差1，那么如果sum[j]比较大，那么这个的答案就相当于ans[j-1]+之前sum[j]有多少个，反之类似。（开longlong）

附上代码：

#include<cstdio>
long long n,t,x,ans,a[100001],b[200001];
int main()
{
    scanf("%lld%lld",&n,&x);
    a[0]=n;
    b[n]=1;
    for (int i=1;i<=n;i++)
    {
        scanf("%lld",&t);
        if (t>=x)a[i]=a[i-1]+1;
        else a[i]=a[i-1]-1;
    }
    t=0;
    for (int i=1;i<=n;i++)
    {
        if (a[i]>a[i-1])t-=b[a[i]];
        else t+=b[a[i-1]];
        b[a[i]]++;
        ans+=t;
    }
    printf("%lld",n*(n+1)/2-ans);
}