![【题解】P11830 [省选联考 2025] 幸运数字](http://pic.xiahunao.cn/yaotu/【题解】P11830 [省选联考 2025] 幸运数字)
P11830 [省选联考 2025] 幸运数字 - 洛谷 (luogu.com.cn)看到中位数就应该想到分为小于中位数、等于中位数和大于中位数。题目中中位数的位置显然和这三种数值的数量有关系设它们的数量分别为。设当前数值为我们强制让成为中位数应该满足1如果的话中位数将大于。2如果的话中位数将小于。我们该如何想到这些条件反推中位数不等于的情况即可前半部分过多中位数变小后半部分过多中位数变大那么对于我们就有同时可以选中位数的尽量多选。也就是让变大这样一定会让该中位数被选择的概率增大。我们发现每个值的可以差分处理也就是对于值区间为的值。我们统一让它们的贡献加上对应前文中的要尽量大。对于当前值区间作为我们则在上差分因为用到这个就代表着一定比大。对于当前值区间作为我们则在上差分因为用到这个就代表着一定比小。#includebits/stdc.h using namespace std; typedef long long LL; const int N 2e5 10; const int M 2 * N; int n, ln, cf, ans; // ln:离散化后点数, cf:当前覆盖 x 的区间数 int l1[N], r1[N], l2[N], r2[N]; // 输入的四元组 int dc[M]; // 离散化坐标所有 l2 和 r21 LL sumb, mna, mxa, mnc, mxc, sumf; // 当前扫描到的累计值 LL bs[M], al[M], ar[M], cl[M], cr[M], f[M]; // 差分数组 // bs: 等于 x // al: amin // ar: amax // cl: cmin // cr: cmax // f: 覆盖x的区间数量的差分 (用于判断是否有区间包含x) void solve() { cin n; for (int i 1; i ln; i ) { bs[i] al[i] ar[i] cl[i] cr[i] f[i] 0; } ln sumb mna mxa mnc mxc sumf ans 0; for (int i 1; i n; i ) { cin l1[i] r1[i] l2[i] r2[i]; 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; i n; i ) { // 这里的 x 和 y 对应着当前区间可选的最小值和最大值 int x lower_bound(dc 1, dc 1 ln, l2[i]) - dc; // 左端点位置 int y lower_bound(dc 1, dc 1 ln, r2[i] 1) - dc; // 右端点 1 位置 // 等于当前值的区间贡献在 [l2, r2] 内增加 r1 bs[x] r1[i]; bs[y] - r1[i]; // 当前值区间作为别人的 a al[y] l1[i]; // 当别人的 amin取最少的数量 ar[y] r1[i]; // 当别人的 amax取最多的数量 // 当前值区间作为别人的 c cl[1] l1[i]; // 当别人的 cmin取最少的数量 cl[x] - l1[i]; // 只有比 x 小的才能选为 c cr[1] r1[i]; // 当别人的 cmax取最多的数量 cr[x] - r1[i]; // 只有比 x 小的才能选为 c // 覆盖当前值的区间数量计数 f[x] ; f[y] --; } for (int i 1; i ln; i ) { // 累计当前点的值 sumb bs[i]; // 等于 x 的个数总和 mna al[i]; // 小于 x 的最小可能个数 mxa ar[i]; // 小于 x 的最大可能个数 mnc cl[i]; // 大于 x 的最小可能个数 mxc cr[i]; // 大于 x 的最大可能个数 sumf f[i]; // 覆盖 x 的区间数量 // 必须有区间覆盖 x否则 x 不会出现在集合中 if (sumf 0) continue; LL lef max(mna - sumb 1, mnc); LL rig min(mxa sumb, mxc); if (lef rig) { // 这段区间内所有整数点都满足条件加入长度 ans dc[i 1] - dc[i]; } } cout ans \n; } int main () { ios::sync_with_stdio(false); cin.tie(0); int c, T; cin c T; while(T --) { solve(); } return 0; }
P11830 [省选联考 2025] 幸运数字 - 洛谷 (luogu.com.cn)看到中位数就应该想到分为小于中位数、等于中位数和大于中位数。题目中中位数的位置显然和这三种数值的数量有关系设它们的数量分别为。设当前数值为我们强制让成为中位数应该满足1如果的话中位数将大于。2如果的话中位数将小于。我们该如何想到这些条件反推中位数不等于的情况即可前半部分过多中位数变小后半部分过多中位数变大那么对于我们就有同时可以选中位数的尽量多选。也就是让变大这样一定会让该中位数被选择的概率增大。我们发现每个值的可以差分处理也就是对于值区间为的值。我们统一让它们的贡献加上对应前文中的要尽量大。对于当前值区间作为我们则在上差分因为用到这个就代表着一定比大。对于当前值区间作为我们则在上差分因为用到这个就代表着一定比小。#includebits/stdc.h using namespace std; typedef long long LL; const int N 2e5 10; const int M 2 * N; int n, ln, cf, ans; // ln:离散化后点数, cf:当前覆盖 x 的区间数 int l1[N], r1[N], l2[N], r2[N]; // 输入的四元组 int dc[M]; // 离散化坐标所有 l2 和 r21 LL sumb, mna, mxa, mnc, mxc, sumf; // 当前扫描到的累计值 LL bs[M], al[M], ar[M], cl[M], cr[M], f[M]; // 差分数组 // bs: 等于 x // al: amin // ar: amax // cl: cmin // cr: cmax // f: 覆盖x的区间数量的差分 (用于判断是否有区间包含x) void solve() { cin n; for (int i 1; i ln; i ) { bs[i] al[i] ar[i] cl[i] cr[i] f[i] 0; } ln sumb mna mxa mnc mxc sumf ans 0; for (int i 1; i n; i ) { cin l1[i] r1[i] l2[i] r2[i]; 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; i n; i ) { // 这里的 x 和 y 对应着当前区间可选的最小值和最大值 int x lower_bound(dc 1, dc 1 ln, l2[i]) - dc; // 左端点位置 int y lower_bound(dc 1, dc 1 ln, r2[i] 1) - dc; // 右端点 1 位置 // 等于当前值的区间贡献在 [l2, r2] 内增加 r1 bs[x] r1[i]; bs[y] - r1[i]; // 当前值区间作为别人的 a al[y] l1[i]; // 当别人的 amin取最少的数量 ar[y] r1[i]; // 当别人的 amax取最多的数量 // 当前值区间作为别人的 c cl[1] l1[i]; // 当别人的 cmin取最少的数量 cl[x] - l1[i]; // 只有比 x 小的才能选为 c cr[1] r1[i]; // 当别人的 cmax取最多的数量 cr[x] - r1[i]; // 只有比 x 小的才能选为 c // 覆盖当前值的区间数量计数 f[x] ; f[y] --; } for (int i 1; i ln; i ) { // 累计当前点的值 sumb bs[i]; // 等于 x 的个数总和 mna al[i]; // 小于 x 的最小可能个数 mxa ar[i]; // 小于 x 的最大可能个数 mnc cl[i]; // 大于 x 的最小可能个数 mxc cr[i]; // 大于 x 的最大可能个数 sumf f[i]; // 覆盖 x 的区间数量 // 必须有区间覆盖 x否则 x 不会出现在集合中 if (sumf 0) continue; LL lef max(mna - sumb 1, mnc); LL rig min(mxa sumb, mxc); if (lef rig) { // 这段区间内所有整数点都满足条件加入长度 ans dc[i 1] - dc[i]; } } cout ans \n; } int main () { ios::sync_with_stdio(false); cin.tie(0); int c, T; cin c T; while(T --) { solve(); } return 0; }
