联合省选 2025 集中讨论贴

站务版

chen_zhe @ 2025-03-01 00:04:38

祝各位考生 ++RP！游记将在周日开放提交通道。

本帖的内容可能会对考生造成显著心态影响。建议考生至少在 Day2 结束后再观看本帖内容。

游记征集：https://www.luogu.com.cn/article/collection/209
Day1 T1：https://www.luogu.com.cn/problem/P11830
Day1 T2：https://www.luogu.com.cn/problem/P11831
Day1 T3：https://www.luogu.com.cn/problem/P11832
Day2 T1：https://www.luogu.com.cn/problem/P11833
Day2 T2：https://www.luogu.com.cn/problem/P11834
Day2 T3：https://www.luogu.com.cn/problem/P11835

发布 ++RP 请前往 https://www.luogu.com.cn/discuss/1062233

本贴中单纯的 ++RP 等祝福（而不带学术交流的内容）可能会被删除。

by Auto_Accepted @ 2025-03-01 15:31:04

@Ace_FutureDream 就你考虑咋求中位数，考虑维护s1,s2,s3,s4,s表示小于当前值的最小个数，最大个数，大于当前值的最小个数，最大个数，和可以取当前值的最大个数。

考虑到每一次从一个区间的端点到另一个区间的端点时，这五个东西的变化都是可以 O(1) 求的，于是简单处理下就昨晚了。

时间复杂度 O(n \log n)，瓶颈在排序，将排序换成基数排序可实现线性。

这个东西应该是对的，我场上这么些过了所有样例，没拍出错。

by Poncirus @ 2025-03-01 15:31:11

@天空即为极限静态的，直接在 a 上做线段树合并。

对于 AC 性质，可以在时间上线段树合并转化为静态问题。

其他就不会了 orz

by Auto_Accepted @ 2025-03-01 15:31:23

这么写

by luogu_hezhenmin1 @ 2025-03-01 15:33:35

祝贺今天的考生们活着完成了考试！

by Poncirus @ 2025-03-01 15:34:52

@Ace_FutureDream 不会吧，我们机房评出来 T1 最多只有上位绿的水平。

离散化之后对于每一个点和给定点之间的点（发现后者可以等价为一个点）看看能不能找到一种方案使得左边的数数量和右边的数数量相等即可（即要求两边的数量区间有交，容易发现“完全在左边”和“完全在右边”两个部分不会互相干扰，对于位于跨越了当前枚举的位置的区间，分配给劣势一方后判断），这个离散化之后前缀和统计一下就行。

by Poncirus @ 2025-03-01 15:37:20

@IkunTeddy /jk，当时出来问了一下听说没问题来着

by _Kenma_ @ 2025-03-01 15:38:49

@Poncirus 你线段树合并复杂度真对吗

by Poncirus @ 2025-03-01 15:39:43

@Kenma 太菜不知，但听到有佬说是对的 /yun

by a1co0av5ce5az1cz0ap_ @ 2025-03-01 15:40:31

@Poncirus 能细说一下怎么在 a 上做线段树合并嘛，我感觉无法离开 dag 的结构啊

by Xy_top @ 2025-03-01 15:41:14

@Auto_Accepted

T1 脑抽了用 5 颗树状数组维护 s1 s2 s3 s4 s 会超时吗