牛客 172A 中位数 题解【二分答案】【前缀和】

点击量：226

    排序后的区间第K大问题？？

目录

题目描述

小N得到了一个非常神奇的序列\(A\)。这个序列长度为\(N\)，下标从\(1\)开始。\(A\)的一个子区间对应一个序列，可以由数对\([l,r]\)表示，代表\(A[l],A[l+1],\dots ,A[r]\)这段数。对于一个序列\(B[1],B[2],\dots ,B[k]\)，定义\(B\)的中位数如下：

1. 先对\(B\)排序。得到新的序列\(C\)。

2. 假如\(k\)是奇数，那么中位数为\(C[\frac{k+1}2]\)。假如\(k\)为偶数，中位数为\(C[\frac k2]\)。

对于\(A\)的所有的子区间，小N可以知道它们对应的中位数。现在小N想知道，所有长度\(\ge Len\)的子区间中，中位数最大可以是多少。

 

输入描述:

第一行输入两个数\(N,Len\)。

第二行输入序列\(A\)，第\(i\)个数代表\(A[i]\)。

输出描述:

一行一个整数，代表所有长度\(\ge Len\)的子区间中，最大的中位数。

 

输入输出样例：

输入样例：

11 3
4864 8684 9511 8557 1122 1234 953 9819 101 1137 1759 

输出样例：

8684

说明

数据范围：
\(30\%: n\le 200\)，
\(60\%: n\le 2000\)，
另外有\(20\%\)：不超过\(50\)个不同的数，
\(100\%:1\le Len\le n\le 10^5, 1\le a[i]\le 10^9\)

题解：

    和[Tjoi2016&Heoi2016]排序的思路很像。都是二分答案；将大的设成1，小的设成0。而这个题特殊就在于它设置的比这个数小是-1。

    先看暴力，首先这个题是要求所有区间的中位数，区间有\(n^2\)个，每次求中位数是\(n\log n\)，总复杂度是\(O(n^3\log n)\)。枚举左端点后可以用平衡树来维护区间的中位数。时间复杂度\(O(n^2\log n)\)。

    而我们要求最大的中位数，这个答案是具有单调性的，因为如果\(x\)不能作为中位数，那么对于\(\forall y\ge x\)都不能作为中位数，因此考虑二分答案。但是二分答案了就要有一个检验的标准，如何检验\(x\)是否能作为中位数呢？中位数就是在区间\([l,r]\)中排第\(\lfloor\frac{r-l+2}2\rfloor\)小的那个数，因此我们只需要判断\(x\)能不能作为一个区间的第(区间长度+1)/2小即可，那么区间中就有不大于(区间长度-1)/2个比它小的数，那么在检验它时就把大于等于它的数置1，小于等于它的数置-1。如果发现有一段长度不小于len的区间，权值和为正，说明这个数小于等于中位数。如果没有找到，就说明这个数一定大于中位数。

    这个图就是简单的流程，答案为6。不过我们看到图中出现了“前缀和”数组，这个是用来找有没有大于0的区间用的，每次更新答案，比较距离在当前点左边\(len\)长度位置的前缀和。维护这些合法区间（即当前位置\(-len\)处以左）中的最小前缀和，判断当前前缀和减去它是否为正即可。也就是在维护区间和\(sum[r]-sum[l-1]\)最大，我们无法决定\(sum[r]\)，因为\(r\)是确定的，但是\(l\)的取值有很多，维护那个最小的\(sum[l-1]\)，就可以让\(sum[r]-sum[l-1]\)最大。如果无论如何也没有为正的区间，二分答案返回false。这个处理类似POJ 2018 Best Cow Fences，比较经典。

Code：

#include<cstdio>
#include<cstring>
int a[100100];
int sum[100100];
int n,m;
bool check(int x)
{
    sum[0]=0;
    for(int i=1;i<=n;++i)
        if(a[i]>=x)
            sum[i]=sum[i-1]+1;
        else
            sum[i]=sum[i-1]-1;
    int mn=sum[1];
    if(sum[m]>0)
        return true;
    for(int i=m+1;i<=n;++i)
    {
        if(sum[i]-mn>0)
            return true;
        mn=mn<sum[i-m+1]?mn:sum[i-m+1];
    }
    return false;
}
int main()
{
    scanf("%d%d",&n,&m);
    for(int i=1;i<=n;++i)
        scanf("%d",&a[i]);
    int l=1,r=1000000001,mid;
    while(l<r)
    {
        mid=l+r>>1;
        if(check(mid))
            l=mid+1;
        else
            r=mid;
    }
    printf("%d\n",l-1);
    return 0;
}