atcoder abc107 D.Median of Medians(二分+前缀和+树状数组顺序对)

题目

给你一个序列a[]

其子区间的中位数定义为长度/2+1

子区间可以为一个点

如5/2+1=3,4/2+1=3等

求所有子区间的中位数的中位数

思路来源

https://www.cnblogs.com/henry-1202/p/9537952.html

题解

二分最后的中位数mid，

把原序列大于等于mid的标为1，小于mid的标为-1

如果一段子区间的和大于0，说明1多-1少，中位数大于等于mid

如果-1多的话中位数怎么也轮不着mid啊

我们作一下前缀和，

那么在前缀和数组中的顺序对

顺序对：suml<sumr且l<r

顺序对的对数即为大于等于mid的答案

因为[l+1,r]这段区间显然>0哈,l+1<=r

那么对于个子区间，

只要顺序对对数即中位数大于等于mid的对数小于，

说明mid不可能出现在最后序列的右起n*(n+1)/4位置即左起位置，而是还靠右，

说明mid找大了，就该往小里找

如果小于等于，说明找小了，该往大里找

但有可能等于也往大里找l=mid+1

但等于之后，再二分的mid就都不符合条件了，l保持不变，l-1就是答案

这个时候只需等r的值均不符合

r=l-1退出循环后，输出r即可

细节

①顺序对的部分可以用树状数组

但考虑到前缀和最小为-n，统一+maxn防止下标越界

②加的时候先把pre[0]加进去

如果前缀和一上来就大于0符合条件，

就会找到先前加进去的pre[0]，

保证答案正确

所以说，树状数组和前缀和的双重保证，要求下标1-n输入啊QAQ

心得

好几个月没用BIT了

现在写来感觉真的是小巧灵活QAQ

代码

#include<iostream>
#include<cstring>
#include<cstdio>
#include<algorithm>
const int maxn=1e5+10;
using namespace std;
typedef long long ll;
ll n,a[maxn],tree[maxn*2+5],pre[maxn*2+5],l,r;
void add(int x,ll v)
{
	for(int i=x;i<=2*maxn;i+=i&-i)
    tree[i]+=v;
}
ll ask(int x)
{
    ll ans=0;
    for(int i=x;i>0;i-=i&-i)
    ans+=tree[i];
    return ans;
}
bool check(int mid)//最后的中位数应该是从右数第n*(n+1)/4个,即顺序对恰为n*(n+1)/4即答案 大于说明mid找小了 小于说明mid找大了 
{
	memset(tree,0,sizeof(tree));
	pre[0]=0;
	ll ans=0;
	for(int i=1;i<=n;++i)
	pre[i]=pre[i-1]+(a[i]>=mid?1:-1);
	//任意大于0的区间均可 即若pre[1]>0 应加上1即pre[0] 故从0开始 
	for(int i=0;i<=n;++i)
	{
		ans+=ask(pre[i]+maxn);//求[1,pre[i]+maxn]的值即比当前值小的已插入值 顺序对 
		//考虑到pre[i]最小可为-n,故移位maxn使之不为负 
		add(pre[i]+maxn,1ll);
	}
	return ans>=n*(n+1)/4;//前缀和顺序对的个数 即比mid要大的中位数个数 
	//如果大于 说明大于mid的中位数超过n*(n+1)/4个 mid一定不是中位数 
	//mid在前一半里 只有n*(n+1)/2为奇数且ans取等才可能是中位数
	//如果小于 则mid在后一半里,比n*(n+1)/2+1要大 
}
int main()
{
	scanf("%d",&n);
	for(int i=1;i<=n;++i)
	{
	 scanf("%d",&a[i]);
	 r=max(r,a[i]);
    }
    while(l<=r)//二分最后的中位数 
    {
    	int mid=(l+r)>>1; 
    	if(check(mid))l=mid+1;//mid可能符合条件 但mid一旦符合条件 l即保持mid+1不变 答案只可能是l-1即r
		else r=mid-1; 
    }
    printf("%d\n",r);
	return 0;
}