自动搬运

查看原文

来自洛谷，原作者为

	ran_qwq debug 深入思考 只靠样例与自己！

搬运于2025-08-24 23:10:34，当前版本为作者最后更新于2025-03-01 17:39:32，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

考场思路，大样例过了，不知道对不对。

考虑对于一个数 $x$，它能成为中位数需要满足什么条件。

首先肯定要有区间包含它，否则 $x$ 连出现一次都不可能。

然后设如果有 $a$ 个数 $<x$，$b$ 个数 $=x$，$c$ 个数 $>x$，那么必须满足以下两个不等式：

• $a+b\ge c$。如果 $a+b<c$，第 $\lfloor\dfrac{m+1}2\rfloor$ 个数 $>x$。
• $a<b+c$。如果 $a\ge b+c$，第 $\lfloor\dfrac{m+1}2\rfloor$ 个数 $<x$。

有一个贪心策略是如果 $l_{i,2}\le x\le r_{i,2}$，即可以放 $x$，就尽量放 $r_{i,1}$ 个 $x$。因为把非 $x$ 改成 $x$，$a$ 和 $c$ 减小而 $b$ 增大，显然 $x$ 成为中位数可能性变大。而且 $x$ 的个数越多，$a$ 和 $c$ 不变而 $b$ 越大，两个不等式中要求大的那部分，即包含 $b$ 的那部分变大，也是更优的。

现在问题变成 $a$ 和 $c$ 取多少。受到个数的限制，$a$ 和 $c$ 都有个最小值和最大值，$a$ 的取值范围为 $[l,r]$，$c$ 的取值范围为 $[L,R]$。

考虑固定 $a$，求 $c$ 的取值范围。第一个不等式化为 $c\le a+b$，第二个不等式化为 $c>a-b$。联立可得 $c\in[a-b+1,a+b]$。

现在不固定 $a$。$a=l$ 时，$c$ 最小为 $l-b+1$。$a=r$ 时，$c$ 最大为 $r+b$。所以 $c\in[l-b+1,r+b]$。

又因为 $c$ 的取值范围为 $[L,R]$，所以 $c\in[\max(l-b+1,L),\min(r+b,R)]$。

对于 $x$，求出 $b,l,r,L,R$ 之后，若 $c$ 的取值范围非空，即 $\max(l-b+1,L)\le\min(r+b,R)$，则 $x$ 可以作为中位数。$b,l,r,L,R$ 可以枚举每个区间，判断其与 $x$ 的关系来求。

到目前为止期望得分 $50$。

我们的瓶颈在于算出 $b,l,r,L,R$，考虑用差分前缀和优化这一过程。具体来讲，一个区间 $[l_{i,2},r_{i,2}]$，会对 $[l_{i,2},r_{i,2}]$ 的 $b$ 产生 $r_{i,1}$ 的贡献，对 $(r_{i,2},\infty)$ 的 $l$ 产生 $l_{i,1}$ 的贡献，对 $(r_{i,2},\infty)$ 的 $r$ 产生 $r_{i,1}$ 的贡献，对 $[1,l_{i,2})$ 的 $L$ 产生 $l_{i,1}$ 的贡献，对 $[1,l_{i,2})$ 的 $R$ 产生 $r_{i,1}$ 的贡献。而 $x$ 能否成为中位数只与 $b,l,r,L,R$ 有关，即如果没有跨过任何区间，不改变 $x$ 能否成为中位数。

所以我们可以对由区间左右端点划分而成的一段进行计算，用前缀和算出 $b,l,r,L,R$ 即可。

需要排序+离散化，时间复杂度 $O(n\log n)$。

可以通过民间数据的代码：

int n,ln,cf,as,l1[N],r1[N],l2[N],r2[N],dc[N*2],f[N*2];
ll ca,cb,cc,cd,ce,a[N*2],b[N*2],c[N*2],d[N*2],e[N*2];
void QwQ() {
	n=rd();
	for(int i=1;i<=ln;i++) a[i]=b[i]=c[i]=d[i]=e[i]=f[i]=0;
	ln=ca=cb=cc=cd=ce=cf=as=0;
	for(int i=1;i<=n;i++)
		l1[i]=rd(),r1[i]=rd(),l2[i]=rd(),r2[i]=rd(),
		dc[++ln]=l2[i],dc[++ln]=r2[i]+1;
	sort(dc+1,dc+1+ln),ln=unique(dc+1,dc+1+ln)-dc-1;
	for(int i=1,x,y;i<=n;i++)
		x=lb(dc+1,dc+1+ln,l2[i])-dc,y=lb(dc+1,dc+1+ln,r2[i]+1)-dc,
		a[x]+=r1[i],a[y]-=r1[i],
		b[y]+=l1[i],c[y]+=r1[i],
		d[1]+=l1[i],d[x]-=l1[i],
		e[1]+=r1[i],e[x]-=r1[i],
		f[x]++,f[y]--;
	for(int i=1;i<ln;i++) {
		ca+=a[i],cb+=b[i],cc+=c[i],cd+=d[i],ce+=e[i],cf+=f[i];
		if(cf&&max(cb-ca+1,cd)<=min(cc+ca,ce)) as+=dc[i+1]-dc[i];
	}
	wr(as,"\n");
}