[ABC107D/ARC101B] Median of Medians 解题记录

本文主要是介绍[ABC107D/ARC101B] Median of Medians 解题记录，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

[ABC107D/ARC101B] Median of Medians 解题记录

题意简述

定义一个长度为 $M$ 的序列的中位数为这个序列中第 $\lfloor \frac{M}{2} \rfloor +1$ 小的数。
现在有一个长度为 $N$ 的序列 $A$ ，将 $A$ 的所有子段的中位数取出来作为一个序列 $S$ ，问序列 $S$ 的中位数是多少。

题目分析

~~早期ABC真的好变态~~
中位数有个性质：

如果 $x$ 是序列的中位数，那么这个序列中至少有一半的数 $\geq x$ 。
本题是求“中位数的中位数”。因为中位数具有单调性，所以考虑二分答案。
先将 $A$ 复制到另一个数组 $B$ 中，将 $B$ 排序。枚举答案在 $B$ 中的下标 $i d x$ 。
check 怎么写？
对于一个序列 $[l, r]$ 和枚举的答案 $x$ ，我们把其中 $> x$ 的数标记为 $1$ ， $\leq x$ 的数标记为 $- 1$ ，如果所有标记的和 $\geq0$ ，那么就说明这个序列的中位数肯定 $\geq x$ 。
序列 $A$ 中共有 $\frac{n\times(n+1)}{2}$ 个区间，如果其中有一半的区间的中位数 $\geq B_{idx}$ （即有一半的区间的区间和 $\geq0$ ），那么就说明真正的中位数比 $B_{idx}$ 大，向有缩减区间，反之亦然。
设 $s_i$ 表示前 $i$ 个标记的和，求“有多少个区间的和 $\geq0$ ”就变成了有多少个 $s_i\geq s_j$ 。
可以使用类似逆序对的思想，用树状数组统计 $s$ 不同值域的数量。
注意：由于 $s_i$ 可能小于 $0$ ，所以需要整体加上 $n$

AC Code

#include<bits/stdc++.h>
#define arrout(a,n) rep(i,1,n)std::cout<<a[i]<<" "
#define arrin(a,n) rep(i,1,n)std::cin>>a[i]
#define rep(i,x,n) for(int i=x;i<=n;i++)
#define dep(i,x,n) for(int i=x;i>=n;i--)
#define erg(i,x) for(int i=head[x];i;i=e[i].nex)
#define dbg(x) std::cout<<#x<<":"<<x<<" "
#define mem(a,x) memset(a,x,sizeof a)
#define all(x) x.begin(),x.end()
#define arrall(a,n) a+1,a+1+n
#define PII std::pair<int,int>
#define m_p std::make_pair
#define u_b upper_bound
#define l_b lower_bound
#define p_b push_back
#define CD const double
#define CI const int
#define int long long
#define il inline
#define ss second
#define ff first
#define itn int
CI N=2e5+5;
int n,a[N],s[N],c[N<<1],d[N],b[N];
int lowbit(int x) {return x&(-x);
}
void update(int x,int v) {for(int i=x;i<=n*2;i+=lowbit(i)) {c[i]+=v;}
}
int query(int x) {int b=0;for(int i=x;i;i-=lowbit(i)) {b+=c[i];}return b;
}
bool check(int x) {int cnt=0;rep(i,1,n) {s[i]=s[i-1];if(std::l_b(arrall(b,n),a[i])-b<=x) {//a[i]在b中的下标小于等于枚举的下标，因为b是有序的，所以等同于a[i]<=xs[i]--;} else {s[i]++;}}mem(c,0);rep(i,1,n) {update(s[i-1]+n,1ll);cnt+=i-query(s[i]+n);//统计到s[i]位置有多少个“逆序对”}return cnt>=n*(n+1)/2/2+1;//真实答案大于等于b[x]
}
signed main() {std::cin>>n;arrin(a,n);rep(i,1,n){b[i]=a[i];}std::sort(arrall(b,n));int l=0,r=n,idx;while(l<=r) {int mid=l+r>>1;if(check(mid)) {//mid小了，向大的缩减r=mid-1;idx=mid;} else {l=mid+1;}}std::cout<<b[idx];return 0;
}