Median of Medians - AtCoder arc101_b - Virtual Judge
寻找中位数们的中位数，使用二分搜索，在数列a的最小值和最大值之间搜索，
在一列数m1,m2,m3......m_n中，如果x是他们的中位数，应该满足大于等于x的数的数目大于等于
n-[n/2]，并且x是满足该条件的最大数
比如1,2,3,4中，x=3是满足两个数（4-[4/2]）大于等于x的最大x值
比如 1,2,3,4,5中，x=3是满足三个数(5-[5/2]）大于等于x的最大x值
所以可以统计，在所有的中位数中，满足大于等于x的数的个数
如果统计给定一个区间[l,r]，快速判断这个区间的中位数是否大于等于x呢：
通过观察，将这个区间的数不降序排列后，如果区间内大于等于x的数的数目（区间中数的个数为n）大于等于(n-[n/2])，则该区间的中位数大于等于x
比如1 2 3 4，x=3，大于等于3的个数是2=4-[4/2]
比如1 2 3 4 5,x=3，大于等于3的个数是3=5-[5/2]
将一个区间中的数分成两类，大于等于x的数令其为1，否则令其为-1，则当这个区间的数的和大于等于0的时候，这个区间的中位数大于等于x
例如1 2 3 4，变为 -1 -1 1 1，和为0
这样处理后，求一个区间的和可以通过前缀和快速计算，给定区间端点l和r，如果pref[r]-pref[l-1]>=0，则这个区间的中位数大于等于x
通过移项得到 pref[r]>=pref[l-1]，（r>=l>l-1），也就是在pref数组中出现几个逆序对就有几个区间的中位数不大于等于x
因为l=1时，l-1=0，所以pref数组对于逆序对的计数要从下标0开始，统计逆序对的方法有归并排序和树状数组
复杂度 log(10^9)（二分查找）*Nlog(N)（使用树状数组）
#include<iostream>
#include<cstdio>
#include<climits>
#include<cstring>
using namespace std;#define int long long
#define lowbit(x) (x&(-x))const int maxn=2*1e5+5;int tree[maxn],a[maxn],pref[maxn];
int n;void update(int x,int d){while(x<=maxn){tree[x]+=d;x+=lowbit(x);}
}int query(int x){int res=0;while(x){res+=tree[x];x-=lowbit(x);}return res;
}int satisfy(int x){memset(tree,0,sizeof(tree));int t=n*(n+1)/2; //总数目int tar=t-t/2; //顺序对数目应该大于等于这个数int cnt=0;int minpref=0;pref[0]=0;for(int i=1;i<=n;i++){pref[i]=pref[i-1];if(a[i]>=x){pref[i]++;}else {pref[i]--;}minpref=min(minpref,pref[i]);}int base=-minpref+1;for(int i=0;i<=n;i++){pref[i]+=base+1;}for(int i=n;i>=0;i--){cnt+=query(pref[i]-1);update(pref[i],1);}if(t-cnt>=tar){return 1;}else {return 0;}
}int bin_search(int l,int r){int ans=-1;while(l<r){int mid=(l+r)>>1;//printf("l=%lld r=%lld mid=%lld\n",l,r,mid);if(satisfy(mid)){//printf("%lld满足！\n",mid);ans=mid;l=mid+1;}else {r=mid;}}return ans;
}signed main()
{ios::sync_with_stdio(0);cin.tie(0);cin>>n;int maxa=-1,mina=INT_MAX;for(int i=1;i<=n;i++){cin>>a[i];maxa=max(maxa,a[i]);mina=min(mina,a[i]);}cout<<bin_search(mina,maxa+1)<<"\n";return 0;
}
