题解：P11830 [省选联考 2025] 幸运数字（民间数据）

· · 题解

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

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

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

然后设如果有 a 个数 <x，b 个数 =x，c 个数 >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");
}