当前位置：首页 > news >正文

洛谷 P11830 省选联考2025 幸运数字题解

news 来源：原创 2025/9/9 11:47:20

题意

小 X 有 $n$ 个正整数二元组 $(a_i, b_i) (1 \leq i \leq n)$ 。他将会维护初始为空的可重集 $S$ ，并对其进行 $n$ 轮操作。第 $\leq i \leq n)$ 轮操作中，他会在 $S$ 中加入 $a_i$ 个 $b_i$ 。

设 $\sum \limits_{i=1}^{n} a_i$ ，在所有操作结束后，小 X 会得到一个包含 $m$ 个正整数的可重集 $S$ 。最后他会计算 $S$ 的中位数，即 $S$ 中第 $\left\lfloor \frac{m+1}{2} \right\rfloor$ 小的数，作为他的幸运数字。

想知道小 X 幸运数字的小 Y 不知道这 $n$ 个二元组的具体数值是多少，但她得知了每个数的范围。具体地，对于每个 $\leq i \leq n$ ，小 Y 知道 $a_i \in [l_{i,1}, r_{i,1}]$ 且 $b_i \in [l_{i,2}, r_{i,2}]$ 。

小 Y 想知道在满足以上条件的情况下，有多少个数可能成为小 X 的幸运数字。

设 $\sum n$ 为单个测试点内所有测试数据的 $n$ 的和。对于所有测试点：

$\leq T \leq 400$
$\leq n \leq 2 \times 10^5$ ， $\leq \sum n \leq 6 \times 10^5$
$\forall 1 \leq i \leq n$ ， $\leq l_{i,1} \leq r_{i,1} \leq 10^9$ ， $\leq l_{i,2} \leq r_{i,2} \leq 10^9$ 。

思路

假如有一个数列，一个值 $m$ 的个数为 $b$ ，比它小的数的个数为 $a$ ，比它大的数的个数为 $c$ ，对于中间位置 $mid=\left \lfloor \frac{a+b+c+1}{2} \right \rfloor$ ：

$mid\le a$ ，那么中间位置在小于 $m$ 的数中，中位数小于 $m$ ；
$a<mid\le a+b$ ，那么中间位置在一堆 $m$ 中，中位数就是 $m$ ；
$mi d > a + b$ ，那么中间位置在大于 $m$ 的数中，中位数大于 $m$ 。

那么，当我们知道 $m$ 的个数、小于和大于 $m$ 的数的个数，就可以知道 $m$ 是否为中位数。将这样的操作集成为函数 $\rm {Mid}(a,b,c)$ ，三种类型分别为 $- 1, 0, 1$ 。

但是题目中给的是个数的区间，那要怎么办呢？

考虑从题目给的“个数区间”下手，如果可以维护两对区间：小于 $m$ 的数的个数区间为 $l_{les},r_{les}]$ ，大于 $m$ 的数的个数区间为 $l_{big},r_{big}]$ 。如果存在 $\textup{Mid}(r_{les},cnt_m,l_{big})=0$ 或者 $\textup{Mid}(l_{les},cnt_m,r_{big})$ ，显然 $m$ 为中位数。

还有两种情况就是，小于 $m$ 的数的个数取得少、大于 $m$ 的数的个数取得多，或者小于 $m$ 的数的个数取得多、大于 $m$ 的数的个数取得少。这两种情况的可行性体现于：
$\textup{Mid}(r_{les},cnt_m,l_{big})\neq\textup{Mid}(l_{les},cnt_m,r_{big})$

（感性理解就是）因为两端个数 $a\in [l_{les},r_{les}]$ 、 $c\in[l_{big},r_{big}]$ ， $a$ 和 $c$ 可以取各自区间的任意一个数；而“不等于”相当于存在 $r_{les}>l_{big},l_{les}<r_{big}$ 或者 $r_{les}<l_{big},l_{les}>r_{big}$ ，可以构造出 $m$ 是中位数的情况。

ll Mid(ll a,ll b,ll c)
{ll mid=(a+b+c+1)>>1;if(a>=mid)return -1;if(a+b>=mid)return 0;return 1;
}
bool MID(ll m)
{ll c1=Mid(les.r,m,big.l),c2=Mid(les.l,m,big.r);return m&&(!c1||!c2||c1!=c2);
}

那只要能维护出上文的两对区间就可以了。

因为只求个数，不需要知道具体哪一个，而且注意到题目给的 $l_{i,1},r_{i,1},l_{i,2},r_{i,2}$ 较大，考虑离散化。然后套路地用两个动态数组分别季度左右端点的信息，以便进行枚举过程中的信息修改。

枚举一堆 $m$ 是否为中位数时，贪心地取 $m$ 的最多数量（比较明显的贪心）。

先初始化 $l es$ 和 $bi g$ 区间，然后直接在离散化的下标哪里扫过去：在 $m$ 和 $m + 1$ 的转移中，使用先前维护的动态数组，分别加入和删除当前中位数和不符合条件的中位数的信息：从 $bi g$ 区间删去当前中位数的信息，在 $l es$ 区间中加入被弹出的数的信息。

答案就是相邻区间个数和。使用离散后的数组就可以计算。

一些细节和写法见代码：

#include<bits/stdc++.h>
using namespace std;
#define ll long long
const ll N=1e6+9,inf=0x7f7f7f7f;
int id,T,n;
struct term
{ll l,r;
}a[N],b[N],les,big;
ll bb[N];
ll Mid(ll a,ll b,ll c)
{ll mid=(a+b+c+1)>>1;if(a>=mid)return -1;if(a+b>=mid)return 0;return 1;
}
bool MID(ll m)
{ll c1=Mid(les.r,m,big.l),c2=Mid(les.l,m,big.r);return m&&(!c1||!c2||c1!=c2);
}
vector<term>s[N],t[N];
void clean(ll nn)
{for(int i=1;i<=nn;i++)s[i].clear(),t[i].clear();
}
int main()
{scanf("%d%d",&id,&T);while(T--){scanf("%d",&n);for(int i=1;i<=n;i++){scanf("%lld%lld%lld%lld",&a[i].l,&a[i].r,&b[i].l,&b[i].r);bb[i*2-1]=b[i].l;bb[i*2]=b[i].r+1;}sort(bb+1,bb+2*n+1);ll nn=unique(bb+1,bb+2*n+1)-bb-1;les.l=les.r=big.l=big.r=0;//在中位数枚举的转移中，动态维护两对区间//比中位数大/小的个数区间 //[les.l,les.r] cntmid [big.l,big.r]for(int i=1;i<=n;i++){b[i].l=lower_bound(bb+1,bb+nn+1,b[i].l)-bb;//离散化b[i].r=lower_bound(bb+1,bb+nn+1,b[i].r+1)-bb;//	cout<<b[i].l<<" "<<b[i].r<<endl;s[b[i].l].push_back(a[i]);//套路地，只记录左右端点信息t[b[i].r].push_back(a[i]);big.l+=a[i].l,big.r+=a[i].r;//big区间初始化}ll cntmid=0,ret=0;for(int i=1;i<=nn;i++){for(auto x:s[i]){cntmid+=x.r;//加入中位数，贪心的取数量更多的中位数 big.l-=x.l,big.r-=x.r;//从big区间删去}for(auto x:t[i]){cntmid-=x.r;//弹出不符合条件的 les.l+=x.l,les.r+=x.r;//弹出的加入les区间 }//	cout<<les.l<<" "<<les.r<<" "<<big.l<<" "<<big.r<<endl;if(MID(cntmid))ret+=bb[i+1]-bb[i];//这段区间都能是中位数，统计个数}printf("%lld\n",ret);clean(nn);}return 0;
}

题意

思路

相关文章：