题意:给出一个序列,询问长度$>=len$的子区间的中位数的最大值,偶数长度取中间靠前一个作为中位数
------------
比赛的时候想到正解把自己hack了,交了个30分暴力
正解其实肥肠简单
二分一个数,检验ta是不是一个长度$>=len$的区间的中位数即可
对于$check$,把$>=mid$的数记为$1$,$<mid$的数记为$-1$
然后从$1$到$n$扫一遍
记录一个前缀最小值,当$i>=len$的时候看一下这一段的和是否$>0$就好了
所以考场上的每一个想法都要认真思考啊qwq,与正解擦肩而过太难受了
```
#include<cstdio>
#include<cstring>
#include<cctype>
#include<algorithm>
#define reg register
using namespace std;
const int N=1e5+5,inf=1e9;
int n,m,a[N],b[N],c[N];
inline int read()
{
int x=0,w=1;
char c=getchar();
while (!isdigit(c)&&c!='-') c=getchar();
if (c=='-') c=getchar(),w=-1;
while (isdigit(c))
{
x=(x<<1)+(x<<3)+c-'0';
c=getchar();
}
return x*w;
}
inline bool check(int k)
{
for (reg int i=1;i<=n;i++) c[i]=(a[i]>=k?1:-1);
for (reg int i=1,mi=inf;i<=n;i++)
{
if (i>=m) mi=min(mi,c[i-m]); c[i]+=c[i-1];
if (i>=m&&c[i]-mi>0) return 1;
}
return 0;
}
int main()
{
n=read(),m=read();
for (reg int i=1;i<=n;i++) a[i]=b[i]=read();
sort(b+1,b+n+1);
int l=2,r=n-1,ans=0;
while (l<=r)
{
int mid=(l+r)>>1;
if (check(b[mid])) ans=mid,l=mid+1;
else r=mid-1;
}
printf("%d\n",b[ans]);
return 0;
}
```