专栏文章

题解：AT_arc101_b [ABC107D] Median of Medians

CClare613
AT_arc101_b题解参与者 9已保存评论 9

文章操作

快速查看文章及其快照的属性，并进行相关操作。

当前评论
9 条
当前快照
1 份
快照标识符
@minrtval
此快照首次捕获于
2025/12/02 07:19
3 个月前
此快照最后确认于
2025/12/02 07:19
3 个月前
查看原文
我敢打赌，这肯定是洛谷这道题里最详细的题解了。

思路：

写这道题的时候可以先去 P3031 看一下，这篇题解就以此为突破口。
对于 P3031 这道题，我们可以先打暴力。

P3031 の 4040 分解法：

我们学过，如果想要找子串，我们可以枚举左端点和右端点，如下：
CPP
	for(int l=1;l<=n;l++){
		for(int r=l;r<=n;r++){
			/*这里写中位数判断*/
		}
	}
于是我们这个暴力只需要注意判断子串中位数是否大于等于 xx。
我们将中位数判断部分记为函数 check(l,r)。那么我们改怎么写 check(l,r) 呢？
很明显，作为暴力，我们可以再用一个数组来存储 al∼ara_l\sim a_r，记为 bb，长度为 mm。我们需要判断的便是 b⌊m2⌋+1≥xb_{\lfloor \frac{m}{2}\rfloor+1}\ge x。中位数的定义如下：
将 bb 按升序排序得到数列 b′b'。此时，b′b' 的第 M / 2 + 1M\ /\ 2\ +\ 1 个元素的值即为 bb 的中位数。这里，// 表示向下取整的除法。
定义来源于题目。
判断完 b⌊m2⌋+1≥xb_{\lfloor \frac{m}{2}\rfloor+1}\ge x 后，如果满足就加 11，对于每个子串都来一遍，输出即可。
CPP
#include<bits/stdc++.h>
#define int long long
using namespace std;
int n,x;
int a[1000005];
int b[1000005];
int check(int l,int r){
	int m=0;
	for(int i=l;i<=r;i++){
		b[++m]=a[i];
	}
	sort(b+1,b+m+1);
	return (b[m/2+1]>=x?1:0);
}
signed main(){
	cin.tie(0)->sync_with_stdio(0);
	cout.tie(0)->sync_with_stdio(0);
	cin>>n>>x;
	for(int i=1;i<=n;i++){
		cin>>a[i];
	}
	int ans=0;
	for(int l=1;l<=n;l++){
		for(int r=l;r<=n;r++){
			ans+=check(l,r);
		}
	}
	cout<<ans;
	return 0;
}

P3031 の 8080 分解法：

通过暴力得到 4040 分后，我们便要向 8080 分进发。
我们可以发现，对于每一个字串，如果希望 b⌊m2⌋+1≥xb_{\lfloor \frac{m}{2}\rfloor+1}\ge x，那么就肯定满足这个性质：
  • 设 xx 为数组 bb 中大于等于 xx 的数字个数，yy 为数组 bb 中小于 xx 的数字个数，那么 x,yx,y 一定满足 x−y≥0x-y\ge0。
这个性质是怎么来的？我们可以想，排完序后，如果 b⌊m2⌋+1≥xb_{\lfloor \frac{m}{2}\rfloor+1}\ge x 满足，那么大于等于 xx 的数字的数量一定大于等于 m−(⌊m2⌋+1)+1m-(\lfloor \frac{m}{2}\rfloor+1)+1，即 m−⌊m2⌋m-\lfloor \frac{m}{2} \rfloor。而这个数，一定满足 m−⌊m2⌋≥⌊m2⌋m-\lfloor\frac{m}{2}\rfloor \ge \lfloor\frac{m}{2}\rfloor。
这里也就间接的证明了 x−y≥0x-y\ge0。因为由上定义可以得到 x=m−⌊m2⌋，y=⌊m2⌋x=m-\lfloor \frac{m}{2}\rfloor，y=\lfloor \frac{m}{2}\rfloor。这里的 ⌊m2⌋\lfloor \frac{m}{2} \rfloor 在代码中就是 m/2，编译器会自动向下取整。
最后便是如何计算 x−yx-y。这个问题很简单，我们记大于等于 xx 的数字为 11，小于 xx 的数字为 −1-1。进行前缀和后，记前缀和数组为 sumsum，对于区间 [l,r][l,r]，答案便为 sumr−suml−1sum_r-sum_{l-1}。
CPP
#include<bits/stdc++.h>
#define int long long
using namespace std;
int a[1000005],sum[1000005];
int n,m,k,x;
signed main(){
	cin>>n>>x;
	for(int i=1;i<=n;i++){
		cin>>a[i];
		if(a[i]>=x){
			sum[i]=1;
		}
		else{
			sum[i]=-1;
		}
		sum[i]+=sum[i-1];
	}
	int ans=0;
	for(int l=1;l<=n;l++){
		for(int r=l;r<=n;r++){
			if(sum[r]-sum[l-1]>=0){
				ans++;
			}
		} 
	}
	cout<<ans;
	return 0;
}

P3031 の 100100 分解法：

拿下 8080 分后，100100 分便迎刃而解。
我们观察一下 8080 分代码的 sumr−suml−1≥0sum_r-sum_{l-1}\ge0，调整一下得：
suml−1≤sumrsum_{l-1}\le sum_r
我们将其与 l−1<rl-1< r 联立得：
{l−1<rsuml−1≤sumr\begin{cases} l-1< r\\ sum_{l-1}\le sum_r \end{cases}
似乎在哪里见过这个式子，我们将 l−1l-1 替换为 ii，rr 替换为 jj，便可得到：
{i<jsumi≤sumj\begin{cases} i< j\\ sum_i\le sum_j \end{cases}
这下完全想起来了，这不就是 P1908 逆序对的颠倒版吗！
我们知道逆序对是可以用树状数组来记录之前比 aia_i 大得数字，当然也可以记录之后比 aia_i 小的数字。而这里需要记录的是之前小于等于 aia_i 的数字。为什么？原因就是上面的式子，我不信有理解不了的。
接下来就是处理正负数的问题。很明显，数字区间是 −100000∼100000-100000\sim100000，而树状数组处理不了小于等于 00 的数字，所以这里统一加上 100001100001，这样子数字区间 1∼2000011\sim200001 了。
最后还要注意存入时，第一步时 sum0sum_0，这一个不能漏了，记得还要开 long long。
CPP
#include<bits/stdc++.h>
#define int long long
using namespace std;
const int b=100001;
int a[1000005],sum[1000005];
int tr[1000005];
int n,m,k,x;
int ans[1000005];
int lowbit(int x){
	return x&-x;
}
void modify(int x,int v){
	while(x<=210001){
		tr[x]+=v;
		x+=lowbit(x);
	}
}
int query(int x){
	int ans=0;
	while(x){
		ans+=tr[x];
		x-=lowbit(x);
	}
	return ans;
}
signed main(){
	cin>>n>>x;
	for(int i=1;i<=n;i++){
		cin>>a[i];
		if(a[i]>=x){
			sum[i]=1;
		}
		else{
			sum[i]=-1;
		}
	}
	modify(0+b,1);
	int ans=0;
	for(int i=1;i<=n;i++){
		sum[i]+=sum[i-1];
		ans+=query(sum[i]+b);
		modify(sum[i]+b,1);
	}
	cout<<ans;
	return 0;
}

AT_arc101_b の 100100 分解法：

讲了这么久的 P3031，是时候该讲 AT_arc101_b 了。
我们可以发现，其实我们可以对这道题经行二分答案。为什么？我们的目标是找到一个 xx，使其执行 P3031 的 100100 分代码后可以满足 ans≥⌊n2⌋+1ans\ge\lfloor \frac{n}{2} \rfloor+1，于是我们可以找到单调性：
  • 对于不同的 xx，较大的 xx 满足的概率绝对比较小的 xx 的低。
于是我们可以以 1∼n1\sim n 为区间，每次判断的是 amida_{mid}，如果 amida_{mid} 符合，那么 l=midl=mid，反之 r=mid−1r=mid-1。
最重要的还属 check 函数。check 函数我们的代码可以沿用 P3031 的 100100 分代码。我们唯独要修改的便是最后判断是否满足 ans≥⌊n2⌋+1ans\ge\lfloor \frac{n}{2} \rfloor+1 即可，感觉没有什么要讲的了。
CPP
#include<bits/stdc++.h>
#define int long long
using namespace std;
const int b=100001;
int a[1000005],c[1000005],sum[1000005];
int tr[1000005];
int n,m,k;
int ans[1000005];
int lowbit(int x){
	return x&-x;
}
void modify(int x,int v){
	while(x<=210001){
		tr[x]+=v;
		x+=lowbit(x);
	}
}
int query(int x){
	int ans=0;
	while(x){
		ans+=tr[x];
		x-=lowbit(x);
	}
	return ans;
}
bool check(int x){
	memset(tr,0,sizeof tr);
	memset(sum,0,sizeof sum);
	for(int i=1;i<=n;i++){
		if(a[i]>=x){
			sum[i]=1;
		}
		else{
			sum[i]=-1;
		}
	}
	modify(0+b,1);
	int ans=0;
	for(int i=1;i<=n;i++){
		sum[i]+=sum[i-1];
		ans+=query(sum[i]+b);
		modify(sum[i]+b,1);
	}
	if(ans>=(n*(n+1)/2+1)/2) return 1;
	return 0;
}
signed main(){
	cin>>n;
	for(int i=1;i<=n;i++){
		cin>>a[i];
		c[i]=a[i];
	}
	sort(c+1,c+n+1);
	int l=1,r=n;
	while(l<r){
		int mid=(l+r+1)/2;
		if(check(c[mid])) l=mid;
		else r=mid-1;
	}
	cout<<c[l];
	return 0;
}

后话：

本篇题解编辑历时 11 小时，给个赞再走呗。

评论

共 9 条评论，欢迎与作者交流。

正在加载评论...