专栏文章

Ynoi part 1.

EEric998
个人记录参与者 1已保存评论 0

文章操作

快速查看文章及其快照的属性，并进行相关操作。

当前评论
0 条
当前快照
1 份
快照标识符
@miofk55d
此快照首次捕获于
2025/12/02 18:23
3 个月前
此快照最后确认于
2025/12/02 18:23
3 个月前
查看原文

板刷 Ynoi (2025.8.9~?)

1.P5355 由乃的玉米田

首先过掉 P3674。脑子里带 ω\omega 就不难。
然后考察除法部分。若 x>nx>\sqrt n 显然；若 x<nx<\sqrt n，则预处理答案。具体地，对于每个 ii 满足 x∣aix|a_i，求出 aix\frac {a_i}{x} 上一次出现的位置 pi,xp_{i,x}。则询问 (l,r,x)(l,r,x) 为真，当且仅当 max⁡i=lrpi,x≥l\displaystyle\max_{i=l}^{r} p_{i,x}\geq l。
发现 （显然）pi,x<ip_{i,x}<i，因此询问 (l,r,x)(l,r,x) 为真等价于 max⁡i=1rpi,x≥l\displaystyle\max_{i=1}^{r} p_{i,x}\geq l。
这是好处理的。

2.P4692 谁的梦

把修改丢掉，考察静态问题。
没出现 ii 的拼接方案数等于 每个序列不含 ii 的非空子序列数 之积。对于每个 ii 算出初值，开个 umap 套 set 维护即可。
细节有一车。

3.P8512 [Ynoi Easy Round 2021] TEST_152

太高妙了。想了 30min 才会。
一个朴素的想法是用 ODT 做。然后这个题看起来很不能在线的样子，离线下来。
对于每个颜色段存一个时间戳，扫描线同时维护每个时间戳的数值之和。
30min 中有 20min 虚空思考可持久化/分块。这辈子有了。

4.P5314 [Ynoi2011] ODT

多校放过（近似）原，使用 2h 得以战胜。
2log⁡2\log 就树剖一下，对于每个点维护一颗平衡树存它的轻儿子。重链加只更新链顶。查询 uu 把 uu，uu 的父亲，uu 的重儿子扔进去再做即可。跑的飞慢。
1log⁡1\log 不会。

5. P9991 [Ynoi Easy Round 2023] TEST_107

最简单的一集。15min 得以战胜。
在线相当不可做。离线，枚举 rr。
我们考察对于 [l,r][l,r]，一个合法的区间会长啥样。发现是 [l,r][l,r] 去掉所有某个出现过的数之后剩下的区间。
扫描 rr 同时维护 lasvlas_v 为 vv 上一次出现位置。
分讨。若答案区间右端点为 rr，则左端点应为最小的 lasv≥llas_v\geq l 再 +1+1。
否则一定是某两个相同数之间的区间与原区间的交，两个相同数必定有至少一个在 l,rl,r 中。预处理每个数之后最近的相同数，查询时区间 max⁡\max 即可。
一只 log⁡\log。

P9989 [Ynoi Easy Round 2023] TEST_69

又原又板又典又水。
维护线段树每个节点的 lcmlcm。如果其 >V>V 视为 inf⁡\inf 即可。严肃分析复杂度，发现每个节点若被修改过，则其 lcm≤Vlcm\leq V。因此每个节点最多被大力修改 log⁡V\log V 次。
使用神秘快速 gcd⁡\gcd 即可。

6.P5046 [Ynoi2019 模拟赛] Yuno loves sqrt technology I

强制在线。
维护左右端点为 SS 的整数倍的区间，维护每个块前 xx 个和后 xx 个数的逆序对，维护前 ii 个块中 ii 的出现次数即可。

7.P5071 [Ynoi Easy Round 2015] 此时此刻的光辉

先考虑大力莫队。 10910^9 以下的数最多 1010 个质因数。发现跑不过去。
维护 <1000<1000 的因数个数的前缀和，这样莫队移动一次只需要处理 22 个因数。

8. [Ynoi2019 模拟赛] Yuno loves sqrt technology III

典。预处理 [ln,rn][l\sqrt n,r\sqrt n] 的众数，则 [L,R][L,R] 的答案只可能是 [ln,rn][l\sqrt n,r\sqrt n] 的答案或散块内的 O(n)O(\sqrt n) 个数。

9. P6109 [Ynoi2009] rprmq1

不会。
发现这题的修改在询问前面。
直接对 xx 猫树分治，设分治中心为 mm，对于 xx 坐标跨过 l,rl,r 的询问，拆成 [l,m],[m,r][l,m],[m,r] 两部分处理。这样就变成了一个历史和。

10. P6783 [Ynoi2008] rrusq

不会。
二维没有修改，使用 kdt。考察 TEST_152 的 trick，对右端点扫描线，在 kdt 上打最后一次被矩形覆盖的时间戳。维护一个 O(1)−O(n)O(1)-O(\sqrt n) 的分块即可。

评论

共 0 条评论，欢迎与作者交流。

正在加载评论...