Frosti

日寄 of January,2025

Wed Jan 01 2025
13 minutes
OI生涯记录 日寄 OI
3501 words

Hello,2025#

1.1#

耶噫耶噫耶噫耶哦哦

新年第一天早上当然要去天府红啦（bushi。Coser 老师好多啊，然后天府红也是终于上流萤的谷子了，乐。但是只有 15 块钱了，哭哭。

然后晚上返校，写容斥专题，jmr 的题是改不了一点的。

1.2#

早上#

因为被一道橙题卡常而去学习 NTT。然后就把板子再过了一遍，讲题，然后就再看了看子集反演，只能说容斥 DP 都好抽象啊。

下午#

写多项式全家桶，同时写求逆的板子。

晚上#

因为多项式没取模同时被卡常而放弃写多项式求逆。

1.3#

考试，60pts

T1#

贪心，策略就错了，还要写高精，我觉得强制写高精的出题人就是出生，还好昨天存了一份 NTT。

T2#

贪心，用线段树维护区间覆盖。

T3#

码力分类讨论题，出题人就是畜生。

T4#

分块，或者叫根号分治（？

下午#

先把前两题改了，然后就写专题去了。

晚上#

多项式求逆过了，死因是 struct 的常数大到飞起来， 96ms→1.727s\text{96ms} \to \text{1.727s}，没救了，不封装了。

顺便把多项式 ln⁡\ln 过了，话说最近是不是都在和多项式斗智斗勇啊。

1.4#

早上#

先做容斥，然后 zcy 讲了高维前缀和，祝老就开了个 SOS DP 的专题。

高维前缀和是听了的，用是不会用的，所以直接使用多项式科技过了 A 题，然后 B 题就不行了，得写 SOS DP 了。

下午#

写 SOS DP，然后光速干个总结。

晚上本来想打 Hello 2025 的，但是第二天要早起做卷子就没打 ybz挂分了，乐

1.5#

晚上返校好像没干啥，不想写了。

1.6#

早上把 SOS DP 题单 AK 了，然后补 Hello 2025 的 D，果然还是 DS 适合我。

下午调了半个下午的多项式 exp⁡\exp，死因是 ln⁡\ln 的数组没清空，还开小了点。然后容斥的题是写不了一点的，寄。

晚上又在写 DS。

1.7#

 mod −1sin⁡\bmod ^ {-1} \sin

T1#

应该是 DP，不会，状压骗 40pts。

T2#

还是 DP，不会，性质骗 10pts。

T3#

树形 DP，不会，链的性质骗 10pts。

T4#

可能是数论，先骗了个 30pts。

最后是 60+10+10+0=80pts60 + 10 + 10 + 0 = 80pts，T4 挂了，但是 T1 多了 2020 没想到啊。

然后 T1 其实是类似 2-SAT 的，可以用并查集。T2 是先有个性质，然后维护区间中位数、区间和还有区间元素数量，可以平衡树，直接打了个 FHQ-Treap，但是被卡常了，我不会其他的，所以打表过掉。

T3 T4 是改不了一点的。

然后斜率优化的专题开了，不像是我能做的呢。

1.8#

早上#

做斜率优化，感觉看懂了以后比其他的都好做一点，两个都单调其实就是单调队列维护凸包，不单调就可以上李超线段树了，或者 CDQ 分治、平衡树也行。

下午#

学李超线段树，但这玩意是真的抽象。而且分类讨论的情况还多。

晚上#

写线段树的总结，但是主席树那些还没学呢，只能先咕掉了。

1.9#

今天考试，挂的只有 10pts 了。

T1#

单调栈，但是脑子抽了去写势能线段树了，挂没了，寄。

T2#

DP，但是不会。

T3#

线段树维护矩阵乘法，感觉挺奇妙的 Trick。

T4#

不会 /

下午#

改题 + 写斜率优化 DP。明天还得讲李超线段树斜率优化。

1.10#

改题，并且因为初三的期末考试，提前放一天。

1.12#

考试，挂的只有 30pts 了。

T1#

神经贪心，推了个结论，但是错了，艹。

T2#

一眼 DP，还是之前考过的原题，但是写不出来，寄。打了个暴搜。

T3#

容斥 + DP，寄。

我补药推式子 /

T4#

启发式合并合并联通块，做个 【数据删除】。

但是有个树的部分分，骗了 20pts。

下午#

因为改不出题所以去看 P2305，果然是黑题。可以树链剖分 + 线段树套李超线段树。

并且可并堆的题单开了，终于可以回数据结构了 :)

1.13#

写题

早上先写了一堆可持久化数据结构，但是写可持久化文艺平衡树的时候遇到个灵异错误，gdb 报 Python 的错误。

然后写个垃圾回收，过了。

下午不想写邪虑忧化 DP 了，所以去写了左偏树的 E。本来尝试写个 FHQ Treap 的，但是写挂了。。。

晚上就在暴切主席树 + 写可持久化线段树笔记。

1.14#

考试，【数据删除】的 T2 黄题都写不出。

T1#

一眼二维数点，但是我写出的是指数复杂度，只骗 20pts。

T2#

唐人黄题，放 nmd T2，误导我，【数据删除】的。

就是一个非常简单的前缀和，注意到 AA 和 BB 可以互相转化，并且变换可逆： A→BB→AAAA→AA \to BB \to AAAA \to A。

所以可以直接统计 A,BA,B 的个数，只要两段在模 33 意义下同余，就可以互相转化。

T3#

一眼数位 DP，然后就不会 DP 了。只能传个 vector 下去来记录个数。

T4#

凸优化，不会。而且暴力方程都写不出来。

挂成 60pts 了，今天真是糖丸了。

赛后先光速改出来了 T2。

然后 T1 实际上是一个容斥，统计完了贡献之后就可以当作普通的二维数点来解决。但是主席树写挂了，改成树状数组过的。

晚上就在练习主席树。

T3 是一个数位 DP + 背包 DP。

1.15#

今天补题，开了吉司机线段树，就先去学了。然后我嫌标记维护太烦了，直接用线段树维护矩阵乘法把这道题过掉了/

然后直接把左偏树专题 AK 了啊。

线段树总结都已经写了 514 行了，还没有写完，这玩意真的太多了。

见过停水的，见过停电的，但你见过机房停网的吗/

只能本地改改博客了 qwq。

好了以后，有一道维护六个操作，打了 6kb 的代码爆炸了，导致心态崩了，去水题了。

因为初三放寒假，我们也提前放个周末。

1.17#

考试

T1#

贪心，我尝试证明均分的正确性，然后伪证了/，挂了 40，最后是贪心的策略都有点问题。

T2#

一眼 DS 题。

这个 Trick 我记得是在镜子里的昆虫见过，维护 preipre _ i 表示前一个与这个颜色同色的元素的位置。

然后顺着这个思路，就【数据删除】的想到 CDQ 去了。

看题解发现，我这个思路是没问题的，可以用 set + 线段树维护。

然后可以用类似珂朵莉树的方式维护区间，但是我没调出来。

T3#

容斥题，不会。

T4#

另类的树形 DP，最后可以转化到求集合的交集/并集上。

可以用珂朵莉树维护，好耶，但是是 DP，不好。

所以没改

然后改了 T1，T2 改不出来就去写吉司机线段树了。

周三改不出来的吉司机线段树调出来了，乐。

1.18#

今天做题。

我觉得以后做题那一天的日寄放题解吧？

UOJ 169 元旦老人与数列

修改：区间加、区间 ChkMax

查询：区间最小值，区间历史最小值。

一眼吉司机线段树，考虑用 SegBeats 的 Trick 将 ChkMax 转化为加减法。

考虑维护 lazMin,laznMin,hislazMin,hislaznMinlazMin,laznMin,hislazMin,hislaznMin 这四个 lazytag，分别表示最小值的 lazytag，非最小值的 lazytag，以及它们的历史标记。

每次下放标记的时候，就同时用 laz+Lazlaz + Laz 去更新对应的历史标记，同时更新历史最值就好了。

还是很板的。

洛谷 P6242 【模板】线段树 3

就是上面那道题，把最小值和最大值互换一下，加个区间求和就好了。

重构一遍就过了嘛

今天还 VP 了一场 CF Div.2，只切了两道

CF A

发现每次移动之后，落点都在上一个矩形内部，所以无效的周长就是 2(2m−xi−yi)2(2m - x _ i - y _ i)，把所有周长减去无效周长就好了。

CF B

发现若 pi,pj(pi<pj)p _ i,p _ j(p _ i \lt p _ j) 间有边，则 i<ji \lt j，所以我们可以求出，对于每一个和 ii 间有边的点，有多少个比它小的。然后填到答案数组里，如果不空就往前放。

一开始甚至想到的是差分约束。

1.19#

考试，只有 20pts。

T1#

给你一些字符串 {si}\{s _ i\}，求一个子序列，使得对于所有 i>ji \gt j，有 si>sjs _ i \gt s _ j，且 reverse(si)>teverse(sj)\text{reverse}(s _ i) \gt \text{teverse}(s _ j)，并且相邻两项有恰好一项有 mm。

我们先按 sis _ i 排序，然后离散化 reverse(si)\text{reverse}(s _ i)，这个时候，我们就能写出一个 DP 方程了：

dpi,0/idp _ {i,0/i} 表示考虑了前 ii 个，且第 ii 个有/没有 mm。

则有以下 DP 方程：

dpi,0=max⁡j<i{dpj,1}dpi,1=max⁡j<i{dpj,0}dp _ {i,0} = \max _ {j \lt i} \{dp _ {j,1} \} dp _ {i,1} = \max _ {j \lt i} \{ dp _ {j,0} \}

发现这是一个前缀最大值的形式，使用树状数组优化即可。

我发现我 DP 弱是因为写不出暴力方程，什么优化都会。

T2#

给你一个后缀数组 saisa _ i 表示ssai,∣s∣s _ {sa _ i,|s|} 的字典序是第 ii 小的，再给你一个 bib _ i 表示 si−1,∣s∣s _ {i - 1,|s|} 与 si,∣s∣s _ {i,|s|} 的公共前缀长度，可能为 −1-1，即未知。

可以通过 sasa 来推出大于和等于关系，再通过 bb 来推出小于关系，可以用并查集/拓扑排序/差分约束求解。

T3 & T4#

WTF 放黑题这还是 C 组吗

没改。

晚上把 CTSN 改出来了，吉司机线段树真的太恶心了。

1.20#

今天做题 + VP Div.3

前四题太简单了就不写了。

CFR 998 E

首先，有没有路径就是联通不联通，所以我们可以考虑维护联通块，可以用并查集方便的维护。

具体的，∀(u,v)∈F\forall (u,v) \in F，若 gu≠gvg _ u \neq g _ v，则这条边必须删除，并记录答案。

然后对于 u∈Gu \in G，若 fu≠guf _ u \neq g _ u，则需要加边，记录答案。

然后输出就好了。

然后下午就去复习复习了 01Trie，把一道毒瘤 Ynoi 过了。

1.21#

又打 VP，但是发挥的比之前的 Div.2 好？

A 题就很简单，如果有偶数答案加一，没有就减一，然后加上奇数个数输出就好。

B 题就是个二分查找的简单模拟。

C 题#

我们先套路的设 dpi,0/1dp _ {i,0/1} 表示考虑前 ii 个人，第 ii 个人诚实/说谎。

其实是可以写普通 DP 的，但是我太菜了，状态错了。

我们再维护一个 sumsum，表示已经确定的说谎的人的个数的前缀和，同时用记忆化搜索实现 DP。若 ai≠suma _ i \neq sum，则不可以接着转移。

然后因为相邻的人不能同时是说谎的人，所以这个人说谎，就不往下个人说谎的状态搜索。

最后记忆化直接开的话是开不下的，用 gp_hash_table 来记忆化。

中午就重构了一遍树套树，过了，原因是不用可持久化的题写了个可持久化。

1.22#

考试

T1#

简单题，我们看到 n≤2×104,m≤1000n \le 2 \times 10 ^ 4,m \le 1000，直接想到权值数据结构，发现维护后缀和。所以直接选择树状数组。

其实甚至不用数据结构

T2#

我们发现，每一次操作，只有每一段区间内的逆序对数量会变，区间与区间互不影响。

又因为序列长度为 2n2 ^ n，则形成一棵满二叉树，恰好，归并排序中每一次就是求一个子区间的逆序对，则可以一次归并排序构建这棵树。

然后赛场上不会归并排序，想的是线段树上跑 CDQ.

我 tm 真想的出来

T3#

赛时不会，其实是一个类似可撤销01背包。

先跑一次背包，求出每一个数能不能被拼出来，然后计算每一个值删除后的变化。

对于一个非法的 QQ，一定有：

∃S,T⊆Us.t.∑i∈SBi+Q=∑i∈TBi\exist S,T \subseteq U s.t. \sum _ {i \in S} B _ i + Q = \sum _ {i \in T} B _ i

则可以用 bitset 维护某个值是否合法，取最小值即可。

其实第一步可以用多项式科技从 O(n2B)\Omicron(n ^ 2 B) 优化到 O(nBlog⁡B)\Omicron(n B \log B) 的，但是我的板子太难用了。

T4#

没改。

放假了，不想写日记，就 2.9 回来再写了吧。