日志

一天更新一次。

2024.7.22

今天讲了树剖和树上启发式合并以及虚树。

非常抽象。

树剖还好，重链剖分和长链剖分都听懂了，并且顺利过掉了板子。树剖理解起来不难，题也是真的不会。

今天大概懂了 50%，非常好（

说句题外话，今天题单上连 A 14道蓝紫黑题的大哥被开盒了，可能大家是难以想象初三的入门组二等奖能进步如此神速，于是扒出了他为了冲榜交别人的AC代码的事，然后他就陨落了。

2024.7.23

今天是 24 暑假C班 day1 暨睿问宗内门弟子半步准提高初期宗门大比，也就是第一次模拟赛 。

第一道题就给我整不会了，看上去是个数学，推了半个小时的结论啥也没推出来，灵机一动想到用逆序对来优化，但是我的常数太大了，于是最后悲惨挂到了 30 分。

T2 好像是个构造，也很毒瘤，我想到了最长不下降子序列的做法，但是因为理解不够，所以否掉了。于是拿了 20 pts 跑路

T3 压根没有任何思路，打了 25pts 的暴力

T4想出来了一个 $O(n^2 m)$ 的做法，但时间不够了，没来得及检查，于是写挂了。

最终得分：30+20+25+0=75，中等水平

总结：一是对各种算法的理解不够深入，除了T2以外T1也想到了树状数组做法，但是理解不足就否掉了，看来要多花时间沉淀，二是考虑不够周到，T1 在本地是可以极限卡过 2e5 的，但是因为 CPU 性能问题，交上去其余全 T 。以后考虑要周到一些。

2024.7.24

今天讲了区间 DP 和换根 DP。其实没怎么讲算法，基本上都是上来就讲例题。

刚开始讲区间例题的时候还比较好懂，后来讲到四边形不等式优化以及 WQS 二分就彻底听不懂了，WQS 二分真是神，加上一个带常系数的一次项就可以 $\log$ 级求解，用的人需要的只是：深刻理解，完全相信 ( 。

换根 DP 还比较好理解，至少这几道题不难，所以 A 掉了。

现在做绿题都感觉好轻松，这就是正睿的强度吗(

2024.7.29

今天首先讲了二叉搜索树的概念以及实现，然后就开始讲平衡树了。理论听起来不难。

首先讲了 Treap ，理解到能用随机数和堆来实现平衡觉得非常神奇。但是平衡树和线段树一样，都是较难实现的数据结构，于是我先对着题解写完了模板题，然后自己完成了另一道比较板的 Treap 。这次居然没有调多久，说明码力还是有所进步的。

然后讲 Splay 就比较迷糊了，不过后来看题解还是理解了，但是代码还没写出来，又要后面补了。

2024.7.30

今天讲了非常抽象的数论。

刚开始讲筛法还好，因为之前学过，所以很容易就听懂了。然后突然开始讲狄利克雷卷积，花了一分钟讲完了定义就开始讲题推式子，像是从普及到了省选，根本听不懂，索性直接放弃，转而去写昨天的平衡树。这些知识只有后面基础好起来的时候再去补了，现在先把前几天的漏洞补上。

平衡树真的难调，比线段树难调 5 倍。不过现在可以不看板子写出一点平衡树题目了，还是有进步。

2024.7.31

今天也讲的是数论，不过情况比昨天好一些。

首先讲了容斥原理，摆出来的实质公式有些抽象看不懂，于是自己去找了找资料然后算是基本搞懂了并 A 掉了一道用到容斥原理的多重背包，不过我在写的时候用的是暴力判断，正解用的是位运算来容斥。于是也学习到了。然后听懂了 Prufer 序列，并顺利 A 掉了板子。后来讲的东西就没听懂了。剩下的时间写了几道相关的题，顺带补了一下昨天的内容。

这周天是 ACM ，但我和 xhr 还没有找到队友，明后天去群里找一个。

2024.8.1

今天讲的是数学期望，多项式以及生成函数，比起昨天也要好一些。前面老师讲的时候还好，后面有些听不懂，但大体来说还是可以理解的。生成函数比较抽象，后面要看一会。

期望 A 掉了几道板子，感觉理解比较容易，但是很多时候无法证明结论是否正确。以后要多练练。多项式和生成函数比较难，于是勉强过了两道题。

今天找到队友了，是一位比 xhr 还大一届的准高三选手，于是我们应该就成了年龄最大的 ACM 队伍。

2024.8.2

今天讲的是博弈论。

但是开始讲的时候没有拉概念，直接开始讲例题了，遗忘的比较多的我只好自己去复习 Nim 游戏和 SG 函数，后来还是基本上跟着走了。不过 Nim 游戏结论还是很神奇，只需要求出每堆石子的数量异或和就可以了，证明过程太难懂，暂时就先深刻理解，完全相信了。

今天做了许多博弈论的题，题单里有去年 THUPC 初赛的一道题，当时难住了我们三个人，直到今天才补上（

2024.8.3

今天讲了可持久化数据结构和恶心的构造题。

讲了持久化线段树的时候还好可以听懂，后面构造题讲的比较详细的听懂了。今天的状态还算比较好。不过在写可持久化线段树的时候总是 WA 和 RE ，也找不出原因。然后发现居然要开 30 倍的空间，以后注意。

明天是 ACM ，今天复习了一下这些天来学过的板子。

2024.8.4

今天是欢乐 ACM 。

赛前制定了策略：每个人开4道题，发现了签到题就说，几分钟的时候就看榜。

开赛以后，因为没有及时发纸质资料，所以只好一道一道看，结果连第一题都还没有读完，已经有人发现了签到题并A掉，不得不感慨手速。

队友花一分钟 A 掉了那道无脑求和的签到题以后就开始找剩下的比较简单的题。这时纸质资料也发下来了于是我们全部扯下来了看，然后 xhr 就切掉了一道很简单的贪心，但是他没有开 long long ，于是吃了两个罚时，但最终拿下了第二题。我看到 D 题以后第一眼感觉是找二进制下 GCD 的关系，一时找不出来且听到了有队已经拿下了 D 题的一血，于是决定打表尝试。结果我惊奇的发现只有 x=y 时会产生贡献，于是急速写了代码并通过，拿下了我们的第三题。xhr 然后再观察 C 题发现只需要简单贪心即可，不过这道题卡 $O(n^2)$ ，所以需要前缀和以及二分来优化。xhr去看别的题了，于是交给我来实现，但是我搞混了 lower_bound 和 upper_bound ，于是我也吃了两个罚时，最后第四道题也 A 掉了。这时我们的队友想出了 L 题的做法，并且没吃罚时做对了。这是我们的排名巅峰，短暂地来到了 RK8 (虽然马上就掉下去了)。

后来陷入了长达两个小时的真空期，他们发现 G,H 过得比较多，于是他们思考这两道题。我看到 J 题发现了一些结论，于是决定继续思考。最后想到了一个 $O(n^2)$ 的 DP 做法，但是数据范围有 $5\times10^5$ ，于是只好考虑优化，想到了线段树但是发现实现起来非常麻烦，感觉剩下的时间并不足以写完，于是放弃。他们那边也没有什么进展。

时间只剩下不到两个小时了，这时神奇的 xhr 想出了来了 H 题的做法，成功切掉，拿下了我们本场的最后一题。然后我们决定集体做 G 题。队友想出来了一个 $O(n \log n)$ 的做法，不过最后没有调出来，最终 Rank25 遗憾离场。

下午听讲评的时候发现我的 J 题思路非常趋近于正解，只需要 $O(n)$ 提前预处理递推就可以了。当时应该把我的思路全部给队友说一下，下次注意思考要周到一点，不要死磕，也不要提前放弃。

2024.8.5

今天早上到教室的时候发现很热，于是被告知是空调坏了，上午一时半会维修不好，让我们先去 112 教室上自习，于是上午就可以愉快地补一下题了。首先重新理解并写了一下以前比较懵的树状数组部分，然后看起了支持静态区间的可持久化线段树，理解起来不难，就是根据线段树修改的性质来优化 $O(n)$ 的 $n$ 个权值线段树至每次添加一个新的权值线段树就只需要在第一颗上添加一个链的 $O(\log n)$ ，成功解决了几道题。本来还想学习一下树套树的，但是看到那个码量觉得剩下的时间不足以写完，于是放弃了继续写了一道可持久化线段树。

下午讲各种字符串，首先讲了 hash 和 KMP ，然后讲马拉车的时候没听懂，讲字典树的时候还算听懂了一些。然后因为上午的课挪到了下午，所以下午的训练被迫推迟到晚上，然后晚上就在教室写题写到了 9：30。

尝试理解了一下明天要讲的 AC 自动机和拓展 KMP ，太过抽象一时半会理解不了，后面再说。

2024.8.6

今天上午继续讲了字符串算法，首先讲了 exKMP 以及 AC 自动机。虽然昨天预习过，但是还是比较难理解，于是最开始听得似懂非懂的。不过后来又找了几个博客，然后就基本上搞懂了并且过掉了模板题。讲 PAM 的时候没懂，后面再补。

下午是附加赛，开了以后发现只有三道题。上来看完三道，T1 应该是结论题，T2 像个 DP 。T3 应该是线段树之类的数据结构题。观察 T1 发现一定是从小到大选最优，于是简单 DP 出当前选加或者乘的最大值。很快就过掉了，但是因为某些玄学问题导致精度丢失，于是最后挂为了 70pts 。 T2 一时半会没有什么思路，于是去看 T3。看到是二维组开始考虑了二维树状数组，不过树状数组好像不能维护区间翻转，于是想到了 Splay，但是还要考虑区间求和，于是就想到了 Splay 树套线段树。但是由于之前只写过树套树的板子，于是写了 1.5h 无果，只好放弃。但是看到有 40 分是可以用线段树并且暴力 $O(nq)$ 修改 3,4 操作的，于是就写了这 40 分。这时转去看 T2 发现并没有什么思路，于是写了一个 $O(n^5)$ 的多重背包，但是发现好像写挂了，时间又不够了，没拿到。

预估得分 ： 100+0+40

实际得分 : 70+0+40

比上次有进步，不过对于这些学习过的知识掌握程度还不够，多多加强。

2024.8.7

今天上午讲的是后缀数组以及后缀自动机。因为太过于抽象，听了一会根本跟不上，索性直接放弃转而去补之前学的比较迷惑的。于是上午就完成了三道重链剖分和线段树以及有旋 Treap 的题。上午讲的后面再补。

下午准备补昨天的题。T3 重新考虑了一下，发现可以不需要拆分成一维线段树，因为 r 很小，所以只需要暴力地开 r 棵线段树就可以了。结构体里面多放一个左右孩子的指针就可以很好的维护操作 3,4 了。

今天顺便把需要补的知识点列了个清单，方便以后看。

2024.8.8

今天是杂题选讲，不过难度有点过于高了，一开始就跟不上，于是放弃转而去补之前的题。

今天终于把重链剖分和普通线段树的题单补完了，现在竟然能一遍过重链剖分并用线段树维护的模板题了，还是有进步。

明天有模拟赛，今天复习了一下板子，这一段时间跟得上就跟，跟不上就把 DP 的题补了。

2024.8.9

今天模拟赛，被创飞了（

8.45 开赛，上来浏览四道题，不对劲，怎么有三道数学，看到部分分更是倒吸了一口凉气， T1 给了纯暴力的 26 T4 给了 10 分的暴力。然后就没有其他的了。

T3 是一个博弈论加期望缝合怪，感觉是个不可做题，看到 T4 的 10 分比较好拿，于是就先拿下了这十分，然后尝试用前缀和以及一些奇怪的东西优化到 $O(n^2)…$ ，不过失败了，于是放弃转而去看前面的题。

T2 上来没什么思路于是决定打表找规律。最开始我把 Qpow 写错了，但是并没有察觉到，于是得出了一个错误的规律，写了以后发现连样例都没有过，才检查出来是自己的快速幂写错了，改对了以后发现之前的规律完全错了，于是考虑 $O(n^2\log n)$ 的暴力。但是好像什么地方写挂了，于是挂掉了。

最后留了两个小时写 T1 。发现正解也很难想，于是决定从暴力以及特殊性质入手。写了个纯暴力的 DFS 发现可以用记忆化优化，于是写好了记忆化搜索以后考虑将 $O(n^2 q)$ 消掉一阶，本来准备用可持久化线段树维护的，但是我看错了值域，还加了个离散化上去浪费了大量的时间，于是最后没有调出来，只交了 26pts 的记忆化搜索。

最后 ：26+0+0+10

RK60

总结：还是犯了很多低级错误，希望正赛的时候不要再犯。

2024.8.10

今天讲的居然是我最喜欢的线段树。

首先讲了动态开点线段树，比较好理解，因为之前学过，所以还是听懂了。然后讲的是可持久化线段树，之前也补过，所以也听懂了。最后讲了线段树合并，有些似懂非懂的，今天大概是听懂最多的一天。

今天写的题全部是线段树，其中一道我惊奇地发现没有改变任何指针的 cout 居然会影响值，并且应该不存在越界，于是就重构了代码，然后过掉了这道题，一共 180 行，这次居然没调多久。

晚上去听演唱会，有些比较抽象。轮到我的时候因为太过紧张，前半段有些抢拍以及不稳，后半段还挺好的.

2024.8.11

今天讲的是同余最短路，让我想起了 2023 的 T4 。

上午讲同余最短路的时候其实还比较好理解，听完老师讲并且结合了 OI Wiki 算是搞懂了。然后看到洛谷有初赛模拟，做了一下，获得了 80 分，还算不错。

下午在写同余最短路，看到了 Alex_Wei 的一种转圈法，还挺厉害的，于是也学习了。

2024.8.12

今天上午讲的是网络流。

开始还算跟得上，不过有一点跟不上了以后就完全跟不上了，我于是找了 OI wiki 和洛谷上的题解自己看。然后基本上懂了 EK 和 Dinic 并过掉了板子。

下午送了一场附加赛。开始先浏览 3 道题，T1 是一个暂时看不出来什么的题， T2 是概率期望，T3 是数学一类的东西。于是先思考 T1 的做法。发现求出原数组的差分以后就可以把区间加减改成单点加减，然后 sort 一下直接贪心就可以了。T2 盯了一会，因为是我一直不擅长的数学，一时半会也没有什么思路，于是决定去手模一下 T3 。模了很久以后发现前面的 20pts 可以枚举 24 种情况打表出来，于是拿下了最后的 20pts 。

赛后 xhr 说 T2 打表找规律就可以了，下次还是要深入思考一下。

最后 ： 100+0+20=120 ， Rank 45 ，还算比上次有进步。

2024.8.13

今天上午讲了线性规划等奇怪的东西，因为内容太过抽象，所以我选择去补昨天的网络流，于是上午就写了两道网络流的题，还找了几篇博客加深理解了一下。

下午因为感觉之前学的树链剖分之类的东西有些遗忘了于是准备写几道题，其中一道重链剖分+线段树的题写了我 200 多行，然后被边界判断以及 hack 数据卡了三个多小时，最后还是过了，以后要多多注意细节。

2024.9.2

时隔多日，终于是又回到了机房。

今天梳理了一下要补的算法，有如下这几类：DP , 数学 , 图论 ,字符串 , 可持久化数据结构以及平衡树，综合考虑后决定顺序如下： dp，图论，数学，字符串,可持久化数据结构以及平衡树因为不在 NOIP 考点以内的原因所以决定以后再考虑。

于是今天就写了 4 道 DP，都是一些背包。

明天决定继续写 DP 。

2024.9.3

今天按照计划执行，依旧还是在练习 DP.

上午写了一道期望 DP ,自己思考无果后转而去看题解,发现只需要简单的推式子然后倒着 DP 就可以了.然后写了一道树形 DP 以及一道背包之类的.

下午得知今天是 IOI 2024 Day 1 ,于是便决定线上观摩一会现场排行榜,中国队今年比起去年来说要逊色一些,但是 zky 还是太强了, 3h 就 AK 了.

下午找空隙做了一会 DP ,也就写了一道题,是一个比较普通的树形 DP .

明天的计划是继续做这个题单 link ,往后做 5 道题左右,这两周的目标大概都是这个.

2024.9.4

今天也按照计划执行，依旧还是在练习 DP 。

上午写的是一道 NOIP 的原题，是一个比较普通的 DP ，不过我没有想到状态可以从同层转移过来，多练练积累经验。

明日计划：

2024.9.4	CF1271E CF840B CF768D CF128C CF16E

2024.9.5

今天按计划执行，上午和下午写完了计划的 5 道 DP ，现在做起来还是比前两天好一些了，不过优化之类的东西还是比较难以想到。

下午观摩了 IOI2024 的 Day2 。今天的题貌似难度比较大，zak 时间过半的时候只 AC 了一道最简单的，一道题写挂了只拿了一半的分数，剩下的一道题据说是专门防 AK ，不过最后还是翻了，zak AK IOI! gyc 拿下了全场第二，并且与第三名的选手拉开了将近 100 的分差，剩下两位选手也稳稳地在金牌分数线上，衷心为他们祝贺。

明天：

2024.9.4	CF1271E CF840B CF768D CF128C CF16E
2024.9.5	CF786A CF621E CF235B CF351B CF1151E

2024.9.9

前两天一共做了 3 场模拟赛，洛谷的基础赛是 255, ZR 的 CSP Day1 是 200，NOIP Day2 是 131。

于是今天就在补题，NOIP Day2 的 T2 正解是虚树，不过我不会这个东西并且 NOIP 好像也不考，所以我就用点分治+树剖解决了这道题， T3,T4 都对着正解过了，这两场大概算是我现在的水平吧，目前做 NOIP 的目标是 T1 写出正解，剩下的几道题把暴力打满。

明天准备补 CSP Day1 的题。

2024.9.10

今天补 CSP Day1 的题。

T1 T2 因为场上过了，所以就从 T3 开始。 T3 正解是线段树优化 DP,理解了思路以后略加调试便通过了这道题，T4 也是一个简单 DP，加上 exGCD 推一下式子，理解起来有一些困难，不过实现还是较为简单的。

除此之外，还完成了 CF353D 以及 CF963B。

2024.9.11

今天按照昨天的计划执行，把这几道 DP 写了。现在做基础的 DP 还是有一定的感觉了，不过更高深一点的斜率优化，四边形不等式之类的因为 NOIP 不考，所以等到后面再补。

除此之外，我和 xhr 还给低年级的小朋友讲了课，讲解了几道初赛题。

明天准备做一下初赛题，做一下洛谷的 S 组模拟。

2024.9.12

今天做了一套初赛题，是 2021 年的 S 组题目，得了 65 分，还需加强。目前失分比较多的是补全程序，但是总体来说问题不大。

除此之外，今天还完成了 NOIP2021 的 T1T2 ，目前基本可以独立做出 T1,T2 比较看题型，如果是我比较擅长的那还是可以做出来的，不太擅长的例如字符串，数学等还需加强.

2024.9.13

今天也做了一套初赛题，是 CSP-S2022 ，当年在赛场上得到了 29 分，今天得了 69 分，还是不禁感慨自己的变化。

除此之外，今天还完成了 NOIP2022 T1T3 ,T2 因为是非常恶心的构造，不太擅长，就暂时先搁置，于是完成了 DP 的 T3;

2024.9.18

今天几乎全部在练初赛。

上午做了 CSP-S 2023 的初赛，获得了 69.5 分，还算是比较稳的，去年的线好像是 55. 做完以后看一下，问题主要是出在阅读程序以及完善程序中的 DP 部分。

下午做的是 2019 的，获得了 71.5 ，也算是比较稳，这几天还是要多加练习。

2024.9.19

今天复盘了这几天做过的初赛题目，把错的地方都重新做了一遍，其中因为不小心丢的分数大概占 30% 左右，剩下的则是能力不足，不过上线还是基本上可以的，明天最后一天再复习一下，后天要稳住。

明天可以专门找几道完善程序来做。

2024.9.21 CSP-S1 2024 游记

今天是 CSP-J/S1 ，下午提前到了考场附近，和大家集合。

进了考场，居然是坐在第一排最中间的位置。

开始先浏览了题目，阅读程序是什么玩意？怎么这么不对劲？完善程序的两道题看起来还好。

前面的单选题怎么这么简单？很快便做完了。

第一道阅读程序就感觉到比较不对劲了，怎么比前两年难这么多？代码也是极其抽象，用一堆位运算成功实现了按位或（

第二道阅读程序卡了我很久，瞪眼了很久以后才看出来是个什么东西，好像是枚举 $(1,2^{n})$ 内的所有数，找到其二进制下的每一个 $1$ ，然后和字符串 $s$ 对比之类的奇怪的东西，不过这时候时间只剩下了 1h ，还有最难的一道阅读程序和完善程序没做，题目也比较恶心，于是没有做多久就做后面的去了。

看到 T3 非常疑惑，这是什么奇怪的算法？感觉不可做以后只写了分析时间复杂度的那道题然后就去做完善程序了。

完善程序还是比较善良的，不过怎么这么多 A 选项。

最后 5 分钟发现自己准考证号填错了，光速修改，还好我有检查信息填涂的习惯。

最后小图灵估分 61.5 ，中规中矩吧，不算太稳。

2024.9.23

昨天是 NOIP 模拟赛 Day4 ，所以今天在补题。

T1 观察了以后发现因为精度的问题，取模又会破坏 GCD 与 LCM 。所以考虑将 $\operatorname{lcm} (a_1...a_i)$ 维护为 $b_i$ ，然后用辗转相除法来转移 $b$ ,最后使得 $ans=\prod b$ 就可以求出来了。

T3 首先第一问是简单的，因为直接所有边权乘二减去最深的点就可以了。
然后第二问考虑对每个深度最大的点算出到这个点且没有走过多余的路的概率。
实际上是什么呢，对于每个不在 $1$ ~ $i$ 路径上的点，如果儿子数量是 $d$，那么合法的概率是 $\frac{d!}{(d+1)^{(d+1)}}$ ，也就是说要把所有儿子都走完才能往回走。如果一个点在 $1$ ~ $i$ 的路径上，儿子个数为 $d$ 那么合法的概率是 $\frac{(d-1)!}{(d+1)^{d}}$ 。

朴素实现是 $O(n \log mod)$。

精细实现一下，比如把需要的除法放到一起除。然后从第一个到第二个转换相当于乘 $\frac{d-1}{d}$ ，这些都是可以做到线性的。所以最后复杂度 $O(n)$。

明天准备一起比一场 Ucup.

2024.9.24

今天我们三人一起做了 ICPC 2024 网络赛 。

开赛后 lry 马上就发现了 M 是签到，于是他很快便过掉了这道题，与此同时，我在看 A 题， xhr 在看 F 题。我发现了 A 题是个比较恶心的签到，但是是模拟，于是我就占了 1h 的机位狂搓 100 行的模拟，不过虽然过了样例，但我一开始就想假了，于是吃了一个罚时。然后 lry 和 xhr 一起想出 F 题的正解并且很快做了出来。这时候机位空了出来，于是我又继续调 A ，但还是没有调出来。然后我决定放弃 A ,把他交给比较擅长模拟的 xhr ，我去想看起来有一点数据结构样子的 C 题。但是经过我们的思考过后，认为这是一个我们尚未接触过的数学问题，但是我当时没有什么其他题能做出了来，于是我决定接着想，我考虑了可持久化权值线段树，并且还通过大眼观察法发现了一个很奇怪的规律，对于每一组 $l,r$ ，连接一条 $l-1,r$ 的边，看最后的这张图是不是一棵树来判断是否正确。赛时因为感觉太不靠谱，所以我们三个也没有尝试，但是赛后知道这就是正解，虽然我证明不了，要用到矩阵行列式线性代数一类的东西，不过也算是一个遗憾。

最后我们一共过了 4 道题，在当时排的到 rank500+ 。还是要多多努力。

2024.9.25

今天突然发现我之前做的 NOIP Day3 的题还没有补，于是今天决定补题。

这一场模拟赛难度还是比较大的，光是 T1 T2 就是紫题,T2比较水，不过我在场上把 T2 正解写出来了，所以我也算场切紫题了(?)

T1 题意： 给定两个长度为 $n$ 的序列 $a,b$，定义一个区间 $l,r$ 的权值为 $\frac{\sum_{i=l}^r a_i}{\sum_{i=l}^r a_i}$ 。给定 $q$ 组 $[l,r]$ ，求每一组区间 $[l,r]$ 的长度至少为 $k$ 的子区间的最大权值。

题解：有一个引理: 对于正数 $a,b,c,d$ 满足 $\frac{a}{b} \le \frac{c}{d}$ ，则有 $\frac{a}{b} \le \frac{a+c}{b+d} \le \frac{c}{d}$ ，所以，最优的合法区间的长度一定 $<2 k$，否则可以分裂成两个合法区间，其中必然有一个不劣。这时有用的区间只有 $O(nk)$ 个，这是可以接受的。
设 $t=2k-1$ ，对于一组询问 $l,r$ ，考虑所有的 $l' \le r-t+1$ ，以这些位置为左端点的有用区间一定被询问区间包含。可以对每个左端点预处理其的最优区间，然后使用线段树维护，这一部分复杂度为 $O(nk+n \log n)$ 。对于 $l'>r-t+1$ ，我们可以优化暴力的区间 dp。注意到所有在此时访问到的区间的长
度均 $<t$，我们可以 $O(nk)$ 地 dp。最后时间复杂度 $O(nk+n\log n+q)$。

剩下两道题因为难度有些过于大，并且考察的内容并不在 NOIP 大纲内，所以暂时先不考虑。

2024.9.26

前一阵子一直在写 DP ,这两周决定专攻数据结构。

今天写了三道线段树，两道题较为基础，稍加调试便通过，剩下一道题是我之前没怎么做过的类型，要用到均摊时间复杂度分析。

题意：给定一个序列，给定三种操作:1. 区间加 2. 使区间内的每一个数 $x=\operatorname{popcount} (x)，$ $\operatorname{popcount}(x)$ 指 $x$ 二进制下 $1$ 的个数。

因为 $\operatorname{popcount}$ 不满足区间可加性，所以不能呢直接用常规的线段树来维护，于是我写了一个打表程序，发现一个区间内的数变成 $1$ 最多只需要 $O(\log V)$ 次 $\operatorname{popcount}$ ，于是就维护一个并查集来判断区间内的数是否全部是 $1$ ，如果是直接跳过，如果不是直接暴力修改其子节点并线段树合并即可。

由于暴力修改的次数最多不会超过 $O(n\log V)$ 次，常规的线段树操作是 $O(n \log n)$ ,所以最终时间复杂度是 $O(n(\log V+\log n))$ 。

2024.9.29

今天在补昨天模拟赛的题。

T2 很简单， $p<q$ 时，答案一定是 $-1$ ， $p=q$ 时， $k=1$ 答案是 $0$ ，其余的是 $-1$ 。

$p>q$ 时，直接二分答案即可，考虑 $[0,mid]$ 中有多少数在序列里出现过，这个数量就等于 $\operatorname{ceil}(\frac{(mid+1)q}{p}-1)$ 。

T3 直接爆搜就可以了

T1 首先暴力枚举根。
显然，对于权值最小的点，选了它的父亲后一定马上就会选它。
这样我们可以把这两个点合并，那么每个点现在都是一个二元组 ， 表示权值之和， 表示点的个数。那么
两个二元组 之间也是可以比较的。$i$ 比 $j$ 优的条件就是 $t_is_j>t_js_i$

把关于 $i$ 的移到同一边，得：$\frac{s_i}{t_i}<\frac{s_j}{t_j}$

于是点合并之后也可以用 $\frac{s_i}{t_i}$ 作为关键字比较大小。并查集+堆即可。

时间复杂度 $O(R ·n\log n)$ ，其中 $R$ 是合法的根的数量

还顺便写了另一场模拟赛 T3 的题解。

XCH 十一集训

Day1,Day2

这两天是我出题。

不过好像因为题面问题导致他们被创了，以后要注意。

Day3

做了之前某一场因为时间问题而耽误的 CSP 模拟赛并且补了题。

Day4

休息。

Day5

今天是做 xhr 的模拟赛。

T1 题面太过于抽象，导致我们光是理解题意就花了 1h。

T2 题面也很抽象，不过理解了题意以后发现是一个高精度除法，我凭借着仅存的做过高精度的记忆把这道题憋了出来。

T3 有一些难，我思考了很久以后感觉是一个点分治，不过因为提高组包括 NOIP 不会考这个东西,所以我就只想了暴力。

最终得分： 100+100+0+0=200

SC分数线出了，也算有惊无险过了。

Day6

今天强度有点大。

8:30~1:00 NOIP 模拟赛。

2:05~4:05 CF。

6:00~10:00 CSP 模拟赛。

NOIP

首先开了四道题，发现都不像简单的样子。

经过思考过后，感觉 T1 是最可做的。

T1 先简单的想了一下，发现可以枚举每个位置 $i$ ，然后考虑贡献，首先归并排序求出每个位置的逆序对数量记为 $num_i$，则 $ans_i=num_i\times C \binom{n-i}{n-i}$ ，不过后面的 $n-i$ 需要去除掉重复的个数，很麻烦，于是整场比赛就全部在做 T1。

赛后知道这场的难度是 蓝+黑+黑+黑，感觉有一些变态了。

CF

下午 CF 不知道为什么状态很差，被两道简单题困住了很久，

CSP

晚上 CSP 模拟赛，首先开题, T1,T2 都是数学类型的， T3 是数据结构，T4 是构造，感觉不太可做。

看了 T1 很久没有思路以后决定思考 T2 。我看到 T2 的时候感觉可以打表，于是惊奇的发现每个数与其所有的因数都会构成好的数对。然后只需要 $O(\sqrt{n})$ 统计每个数的因数个数，最后加上 $O(n)$ 维护就可以了，不过好像因为一些奇怪的原因挂掉了 $20pts$ 。

T3 思考了很久发现只会 $O(n·q·k\log n )$ ,想到了可以用求出的一个答案来中转，但是没想到怎么实现。

于是最后的时间就在思考 T1 ，手模了很久以后发现只要序列中前 $p_1$ 个数没有小于 $p_1$ 的，那么先手必败，所以只需要简单维护就可以了。

最终：100+80+10+0 。

2024.10.9

今天做了两场模拟赛。

上午做了一下 2022 的 CSP-S 真题，T1 打了暴力 60pts ，T2 在草稿纸上画了很久最后实现了正解。T3 不可以总司令骗到了 45pts 。最终 60+100+45+0=205 。

下午做的是 lry 的模拟赛，开赛的时候先预览了四道题， T1 是个数据结构题， T2 是一个奇怪的图论题，T3 看起来就是一个不可做题, T4 题面非常恐怖，但是以我的了解题面长的大概率都不难，于是我断定 T4 是签到题。不过我看了 T4 好像暂时没有什么头绪，于是转而去想我比较擅长的数据结构题。我最开始想到了可持久化线段树+二分答案的做法，不过由于较难能实现，只好另寻他路。于是我注意到了询问是离线的，于是直接用莫队过了这道题。这时候转过头来去看 T4 ,只想到了前缀和，经过我的努力思考过后，想到了一个乱搞哈希的做法，没想到居然神奇地过了。

最后 100+0+0+100=200 。

2024.10.10

今天在补昨天模拟赛的题。

首先补的是 CSP-S2022 的。T1 发现可以先用 BFS 标记出每个点是否可达，然后再用一个环状结构来贪心就可以了， T3 发现原题目的问题可以转化为统计并修改每个点的出度，然后想办法用 Hash 来把出度转化为入度，这个还是太难想了，给每个点附上一个随机权值，这样虽然入度的总和和出度的总和相等并不是出度全部为 $1$ 的充分条件，但是不充分的概率仅为 $\frac{1}{10^{10^6 \times 9}}$ ，几乎是不可能的，于是很简单地实现了。 T4 还没想出了，目前想到了 DP 树剖和矩阵乘法，但是并不知道怎么用矩阵乘法优化，明天继续想。

2024.10.11

今天还是在补昨天模拟赛的题。

CSP-S2022 的 T4 经过思考和手模以后， 想出了用矩阵乘法和树链剖分来优化 DP ,写出来了以后发现不对，检查了很久发现是一个 $+$ 号写成了 $-$ 号。

另外，验了 xhr 新出的模拟题。

2024.10.14

ZR NOIP 20 Day1

开题后发现 T1 很可做，于是短暂思考了一下，一个简单的数学，很快过掉了。接下来看剩下的， T2T3 感觉都是奇怪的 DP ，T4 是个数据结构，是我比较擅长的类型，于是我深入思考了一下，想到了一个很难写的做法：树剖+CDQ 分治+可持久化线段树 ，但是我斟酌了一下，写正解可能非常困难，于是我就盯上了部分分，发现打暴力可以拿到 60pts ，于是转而去实现。但在我写了很久以后发现，加上剪枝后居然可以直接过大样例，但是我感觉会专门造几个数据来卡我 于是我的赛时估计是 30pts，于是交上去索性没管了。然后尝试拼了 T2T3 的暴力，最终拼出 15pts 。

赛时预估 : 100+15+0+30；

结果: 100+15+0+100；

没想到 T4 的数据居然这么水，最终让我荣获了 215 的高分，要是 NOIP 真是这个分数就好了。

2024.10.15

ZR NOIP 20 Day2

开题后发现 T1 一定满足不冲突的两人 $i+1$ 坐的位置一定在 $i$ 后，然后就考虑二分，但是因为还要判满，所以二分的思路假了，调很久以后才发现，又想了一阵也没有思路，于是决定放弃转而去看其他的题。T2 感觉是一个奇怪的 DP，T3 是一个不怎么可做的题，于是盯上了是数据结构的 T4。思考了以后发现我不会什么维护深度的数据结构，于是就决定拼暴力。最后写了 300+ 行的的树剖+线段树+奇怪的树。这时候时间不多了，T3 发现可以连成图来拓扑排序，但是没有写出来，然后修改了一下 T1 的做法，感觉是 $O(n+m)$ ,然后就结束了。

最后 30+0+72=102

比起昨天来说有所退步，不过要是把 T1 的正确做法写出来，T2 T3 部分分拿满还是差不多。

剩下的时间补了题以后做了 CSP-S2023 T1T2。

2024.10.16

ZR NOIP 20 Day3

开题后发现 T1 是一个朴素的 DP, 直接转移一下就可以。T2 思考了一阵以后想出来了一个 $O(n^2)$ 的朴素做法，但是一时没有什么思路优化到 $O(n \log n)$ ，于是就暂时放下去考虑 T3T4 ，结果完全没有任何思路，于是花时间来拼暴力，调了一阵。这时候发现最好拿的就是 T2 正解，于是推了一下式子以后发现可以二分答案，然后很快调试过了。

赛时预估：100+100+10+0=210 。

最终：60+100+10+0=170 。

T1 神秘原因挂了一个点，目前暂时还不知道原因。

2024.10.17

ZR NOIP 20 Day4

赛前出题人说 $B<A<C<D$ ,于是我就先开了 B 题，看了很久以后发现没有任何思路，这道题看起来很像一个 DP ，但是我推了一会以后发现是有后效性的于是放弃，贪心也可以证明是不正确的，于是放弃来看其他的题，T1 是一个感觉像是 DP 的题。T3 是一个数据结构，但是看起来不太可做，T4 也感觉是一个不可做题。于是我就决定全场拼暴力了。

首先把 T3 的暴力 10pts 拿到，然后简单实现了一下 T1 的 $O(n^3)$ 背包，但是我感觉是可以继续优化的，于是就想了很久的 T1 优化，手模了很久以后突然注意到了 DP 的无后效性，然后可以逆向思维一下，因为询问是离线的，所以可以把删除后的答案反着过来变成添加一个数后的答案，于是就愉快的消掉了一阶，变成了最朴素的 $O(n^2)$ 的背包，但是这个做法好像还是只能过 20pts ，于是在尝试用奇怪的二分或者数据结构之类的来优化到 $O(n \log n)$ ，但是努力了很久都没有结果，并且关于背包问题也没有什么好的优化，然后就放弃了，最后 T2 糊了一个乱搞贪心上去，也不知道可以得多少分。

最后： $20+35+10+0$

赛后知道 T1 我想到的是正解的一部分，不过好像还要阈值分治什么奇怪的东西，没学过， T2 居然是二分图匹配，没想到，T3T4 都是国家队难度的题，确实不太可做。这场难度还是过于大了，感觉是 CTS 模拟赛（

2024.10.21

ZR NOIP 20 Day5

上来先开了 T1，最开始想了一个奇怪的做法，但是假了，于是想了很久以后发现答案具有单调性，于是直接二分答案就过了这道题。然后看剩下的三道，T2 像是一个奇怪的 DP ，T3 是个数学， T4 应该是个我做不出来的题，想了 T2 很久没有任何思路，于是决定写 T3 ，打了很久的暴力以后发现想假了，于是放弃，然后重新看 T2 ，这时时间也没有多少了，最终无果，暴力也没有调出来。

最终： 100+0+0+0 ，今天的还是有一些难度的。

下午补了昨天 S 模拟赛 T2，不过昨天模拟赛 T1 树状数组$O(n \log^2 n)$ 跑的比正解线段树二分 $O(n \log \log n)$ 要快三倍，看来常数确实是一个比较要注意的问题。

2024.10.22

ZR NOIP 20 Day6

上来先看了四道题， T1 没什么想法， T2 是个博弈论， T3 是个构造，T4 是个数据结构。

开始决定先想 T1，感觉自己想出了 $O(nm)$，但是在删点的时候发现假了，于是只好打暴力跑路。然后就在想我比较擅长的数据结构，想了很久感觉可以用树上莫队，但是我好像不会，然后就感觉这个是虚树一类的奇怪的东西，于是只好拼暴力。首先写了最基础的暴力，然后考虑链，维护区间颜色个数，于是我就写了一个可持久化线段树得到了这个部分分。最终没多少时间， T2 瞎蒙了一个结论交上去，但是猜错了。

最后 30+0+0+20 。

继续努力。

2024.10.23

因为还有几天就要比赛了，所以今天没有做模拟赛，于是在打板子。

上午复习了一下平衡树和树状数组，以及图论。

下午做了一场信心赛，3h 成功 AK ，rk1 离场，确实很信心，不过也让我重新知道了不要死磕一道题，还有 long long 。

CSP-S2024 rp++。

CQ NOIP 10 Day

2024.11.13 Day1

来 CQ 集训的第一天。

上午就做了他们的模拟赛，开了四道题感觉都不是很善良，很快的做出来了 T1 以后开始苦苦思索剩下的几道题， T3 感觉是一个DS ，于是着重想了一会。猜了一个结论感觉很有正确性，于是着手实现，转化了以后发现可以把单点修改变成一个区间加减的问题，然后用线段树维护。不过写出来了发现最开始那个结论的正确性不可以保证，于是只好放弃打起了暴力。最后的时间写了一下 T4 的 $O(n^3)$ 以及 $O(n^2)$ 的做法，不过后者用 vector 维护一直 RE。无愧我 RE 仙人的名号。

最后 100+0+10+8=118 Rank 28。

不是倒数第一

总结了一下，感觉我们和强校的选手训练方式以及实力还是有很大的差距，多向他们学习。

2024.11.14

第二天。

上午模拟赛。

开始了之后看了四道题感觉到都不是很可做的样子，首先看了 T2 ，感觉是一个 DP。于是推出了 $O(n^4)$ 的式子，
不过好像没有什么用，于是就想到了一个优化方法：线段树套权值线段树来维护区间颜色个数。
实际上是想多了，因为静态区间用前缀和就可以了，但是脑抽了没想到，于是就放弃了。看了 T4 发现按照题意模拟可以得到 10pts 于是拿下了。最后还有一个多小时，看看能不能想出来一道题的正解，于是就盯上了 T1，打了很久的表以后发现就是求
$\sum_{i=l}^r \min \left \{ i \And j \right \} (j\in (l,r))$ 。

然后用类似二分的东西就求出来了，不过调了挺久的。

最后： 100+0+0+10=110 。 Rank132 ，居然是多校联考（甚至有七中）。

剩下的时间尝试理解了一下正解，然后写了一道线段树。

2024.11.17

今天做的是梦熊的模拟赛。

开题先看了 T1，短暂思考过后发现就是一个普通区间修改维护区间最小值以及最小值位置的线段树，40min 不到就写完了。不过测了一下大样例发现发现错了，但是我也没检查出来什么错，就这样盯了几十分钟没有任何进展，于是决定写一个暴力来检查一下，结果暴力写出来也错了，这让我不得不重新读题，结果才发现是 $n,q$ 写反了，改了之后一遍过了。
然后看看 T2，感觉是一个贪心或者背包一类的东西，写了很久以后写出来了一个背包的做法，因为无法验证正确性，所以我还写了暴力。不过我暴力过后搞忘打 return 0 了，写了暴力之后又没有测大样例了，于是直接 $0$ 分。

最后：$100+0+0+0=100$。

这一场低级错误犯的很多，正赛一定要注意。

2024.11.18

今天做了多校联考的模拟赛，是 CDQZ 出题。

开题后先看了 T1，想了很久以后没有什么思路，于是决定从部分分入手。首先考虑了链的部分，发现很简单，直接计算就可以了，然后考虑菊花图，发现要考虑 $u$ 位置。
然后考虑了 $n=4000$ 的做法，想了一个 $O(n^2 \log n)$ 的做法，使用线段树优化一个区间 DP。这时候想了一下正解，一时没什么思路，但是突然想到可以把点和边的贡献拆开来计算，于是就写出了 $O(n)$ 的做法，很简单，于是就看了看 T2。

T2 想了一会就想到了一个 DP 的做法，貌似是 $O(n^3)$ 的，于是决定先写出来，不过发现空间会爆掉，但是发现每一个状态只会与上一个状态以及现在的状态有关。于是就考虑用两个矩阵来滚动数组优化。调了一阵之后过掉了大样例。但是发现复杂度后想假了，但是时间不多了，于是只好放弃。最后打了 T3 暴力，但是没有跳出来。

最后：$100+22+0+0$.

2024.11.19

今天上午做的模拟赛。

T1 看到了感觉是什么奇怪的计数题，于是就决定推式子。然后在 Markdown 里推了很久想出来可以枚举每个夹角， 于是就开始实现，不过极其难调，于是整个比赛都在调 T1。

最后：$100+0+0+0$。

下午因为感觉需要练习一下码力，于是就开了一道大模拟，写+调一共花了将近四个小时。然后写了两个 DP。

另外，今年的 CSP-S 评奖线出了。不出我所料拿到了二等，NOIP 一定要尽量避免非实力因素的失分，加油。

2024.11.20

今天是模拟赛。

上来先看了 T1,感觉可以 DP ，于是考虑线性的做法，想出来了以后调了一阵过后就写出来了。这时候看到剩下的三道题，感觉 T2T3 不是很可做的样子，于是在想 T4，发现可以用 set 维护并查集。于是就开始写，不过细节很多，边界条件也比较难判断，写出来之后调不出来。

最终：100+0+0+0=100。

2024.11.21

今天是在 CQYC 的最后一场模拟赛。

上来先看了 T1，发现就是今年 S 组 T1 改了一下。于是考虑贪心，简单的实现了一下就通过了。然后看剩下的，发现都不是很可做，于是就决定打部分分。最后只拼出来了 20pts。

100+10+10+0=120。

今天制定了下一周的 NOIP 计划，抽几天出来再练练 DP 和图论，赛前两天打打板子就可以了。

SC 省选好像 NOIP 一等就可以去了，看来还是有希望去参加省队选拔的，加油。

2024.12.1

NOIP 炸炸炸！我菜菜菜！

Week 1

这个星期的主要任务：板刷 ARC，打 (VP) CF。

2024.12.2

今天做的：板刷 ARC。

arc_022_3 绿

很板的题，求一下树的直径就可以了。

arc_027_3 绿

背包。不过有一个结论，能用普通就尽量用普通，不过搞忘了滚动数组要从上往下 DP。

arc_035_c 绿

要加边的全源最短路。发现每次加的边只会影响这一块，其实也就是 DP 的无后效性。

arc_119_c 绿

一直没想出来怎么判区间合法，看了题解才反应过来可以用区间交错和相等的性质，思维能力还是要多练练。

arc_172_a 绿

感觉可以贪心放正方形，但是不知道怎么判定，然后就发现可以用现在放的是否超过全局能放的，超过了就不可以了。

arc_157_b 绿

发现如果把一个连续段填完那么贡献是最大的，但是在算负贡献时要先算头尾，算正贡献时要最后算头尾，

arc_017_4 蓝

线段树维护区间加以及区间 gcd。区间 gcd 可以通过更相减损法来转化为原数组差分求出，这样区间加就变成了单点加，线段树维护即可，不过搞忘特判 r=n 了。

NOIP2024 T2 绿

赛时被 T1 硬控了，赛后想很快就会了，简单乘法原理计数就可以了。

CF

你说得对，但是晚上打 CF 被 T2 硬控，最后几十秒想出来 T3 做法但是写不完。

绿：7
蓝：1
紫：0

2024.12.3

继续板刷 ARC。

arc134_c 绿

一个普通的计数问题，不过要用到第二类斯特林数，并且在求组合的时候不能用常规的预处理阶乘来求，但是考虑 $m$ 很小，所以可以每次都暴力乘上 $(n-m+1,n)$ ，然后乘上 $inv_m$ 即可。

arc172_c 绿

最开始想用线段树维护和哈希来做，不过感觉太麻烦，然后发现只有当 $sum_i \le 1$ 时才会产生贡献，直接 $O(n)$ 扫一遍就可以了。

arc146_b 绿

可以对于每一位按照最小的代价来贪心地选，简单处理一下就可以了。

CF2047

全是结论题。

T1

每一天的前缀和如果是某个奇数的平方，则满足条件，暴力判断即可。

T2

直接把某一个出现次数最小的替换为出现次数最多的就可以了。

T3

贪心的选即可。

T4

每个点会被挪到后面当且仅当他的后面有比它小的，但是要注意前面的点也有可能被挪到后面。

Rank696。

upd: 差一点上 1400，遗憾。

arc173_c 蓝

容易发现，对于答案长度为 $k$ 的区间，至多只有 $\frac{n}{k}$ 个点满足条件。于是考虑枚举每一个未得到答案的点，看是否满足 $ans_i>k$ 。以上过程可以调和级数 $O(n \ln n )$ 实现。

然后问题就转化为了：$O(1)$ 判断一个点 $ans_i$ 是否大于 $k$ 。

于是发现，如果 $ans_i>k$ ，那么每个包含 $a_i$ 长度为 $k$ 的区间，$a_i$ 都必须是该区间的中位数。那么就只能是形如 0 1 0 1 x 0 1 0 1 的形式。（ $0,1$ 分别表示小于/大于 $a_i$）。

于是就做完了，不过要记得判断一下边界。

code:

#include<bits/stdc++.h>
#define Love_Elaina return 0
#define int long long
using namespace std;
int qpow(int a,int b,int p){int ans=1;while(b>0){if(b&1)ans=ans*a%p;a=a*a%p;b/=2;}return ans;}
const int maxn=3e5+9;
int n;
int a[maxn];
int s[maxn];
vector<int> b,c;
signed main()
{
    //freopen("test.in","r",stdin);
    //freopen("test.out","w",stdout);
    ios::sync_with_stdio(false);
    cin.tie(0), cout.tie(0); 
    cin>>n;
    for(int i=1;i<=n;i++) cin>>a[i];
    for(int i=1;i<=n;i++)
    {
        if(i>2&&((a[i-2]<a[i])==(a[i-1]<a[i]))) s[i]=3;
        else if(i>1&&i<n&&((a[i-1]<a[i])==(a[i+1]<a[i]))) s[i]=3;
        else if(i<n-1&&((a[i+1]<a[i])==(a[i+2]<a[i]))) s[i]=3;
        else c.push_back(i);
    }
    for(int k=5;k<=n;k+=2)
    {
        b=c,c.clear();
        for(auto i:b)
        {
            if(i-k+2>0&&i<n&&(a[i-k+2]<a[i])!=(a[i-1]<a[i])) s[i]=k;
            else if(i-k+1>0&&(a[i-k+1]<a[i])==(a[i-k+2]<a[i])) s[i]=k;
            else if(i+k-2<=n&&i>1&&(a[i+k-2]<a[i])!=(a[i+1]<a[i])) s[i]=k;
            else if(i+k-1<=n&&(a[i+k-1]<a[i])==(a[i+k-2]<a[i])) s[i]=k;
            else c.push_back(i);
        }
    } 
    for(auto v:c) s[v]=-1;
    for(int i=1;i<=n;i++) cout<<s[i]<<' ';
    cout<<'\n';
    Love_Elaina;
}

绿：5
蓝：1
紫：0

2024.12.4

arc171_b 蓝

容易发现，将每个 $i$ 满足 $i<p_i$ ，从 $i$ 连一条指向 $p_i$ 的边，最终的答案序列 $b_i$ 就是每个 $i$ 所属的链的末尾。

为什么如果存在 $i,j$ 满足 $a_i > i$ 但 $a_j=i$ 就无解？

这时 $j$ 连向 $i$，但是 $a_i > i$ ，所以 $j$ 一定会重新连向 $a_i$ 。

否则，每个 $a_j \ne j$ 的位置填的都是确定的。那么有可能产生变化的只有 $a_j=j$ 的位置。这些位置可以填任意小于 $a_j$ 的数，那么最终乘法原理统计一下就可以了。

arc154_c 绿

把满足条件的 $a,b$ 相邻的去重后，$b$ 一定是 $a$ 的连续子序列。

arc160_c 蓝

定义状态 $dp_{i,j}$ 为数 $i$ 可以向下一位贡献 $j$ 个 $i+1$ 能产生的集合的数量。

记 $num_i$ 为原序列中 $i$ 的数量。

$$dp_{i,\frac{num_i+j}{2}}=\sum_{k=j}dp_{i-1,k}$$

后面这个东西可以用后缀和维护，不过被边界判断卡了一阵。

arc163_c 绿

$\frac{1}{n}=\frac{1}{n+1}+\frac{1}{n(n+1)}$ 结束。不过遇到重复的要往后继续计算。

arc173_a 绿

对于每一个数计算出小于等于它的 neq 数，这个东西分成三个部分计算：位数比它小的，位数和它相同最高位不相等的，位数和它相同最高位相等。然后二分一下就可以了。

P2657 蓝

数位 DP 典中典，提前预处理出 $dp_{i,j}$ 表示第 $i$ 为 $j$ 时的答案，然后分段统计就可以了。

arc094_c 绿

首先可以知道，如果某个位置 $a_i<b_i$ ，那么一定可以操作到零。

然后对于剩下的，一定有且仅有一个会被留下来，于是直接 $O(n)$ 统计就可以。

P5435 紫（非正解）

正解是 $O(值域)$ ，但是被我用 Binary GCD 卡过去了。（

发现 $\gcd(a,b)$ 可以按照这个东西来求：

$a=b:\gcd(a,b)=a$

$a=0|b=0:\gcd(a,b)=a(b)$

$a,b$ 其中一者为偶数：$\gcd(a,b)=\gcd(\frac{a}{2},b)$

$a,b$ 皆为偶数：$\gcd(a,b)=2\gcd(\frac{a}{2},\frac{b}{2})$

$a,b$ 都是奇数：$\gcd(a,b)=\gcd(a,a-b)$

然后再用 __builtin_ctz() 优化一下（这个东西跑得飞快），就过了。

绿：4
蓝：3
紫：1

2024.12.5

arc150_b 蓝

考虑根号分治，对于 $a\le\sqrt b$ ，直接统计每个因子。对于 $a\ge \sqrt b$ ，记 $d=\frac{b}{a}$，统计 $d$ 就可以了。

P3396 蓝

典型的根号分治。提前预处理出 $\sqrt n$ 内的模数的所有贡献，如果给定的 $y\ge \sqrt{n}$，那么直接枚举，时间复杂度 $\sqrt{n}$ 。

根号分治妙妙妙！

P9809 蓝

对于 $x\le \sqrt{n}$ ，直接枚举算贡献就可以了。对于 $x> \sqrt{n}$ ，考虑值域分块，用 set 维护每个 $\sqrt n$ 块的最近的数，算就可以了。

arc150_c 绿

有一个转化：把能和 $b$ 匹配的转化为边权，然后直接跑 Dijkstra 就可以了。

arc124_c 绿

一：发现可以模拟退火，每次扫一遍看可不可以交换，然后就乱搞过了。

二： 记 $dp_{i,j}$ 为是否能达到 $\gcd(A)=i,\gcd(B)=j$ ，用 set 转移就可以了。

CF2050 Div3

被 B 硬控 40min，写出 G 题正解因为函数和某个库里面的命名重合没查出来痛失 AK，气死。

绿：5
蓝：3
紫：0

2024.12.6

今天 NOIP 查分，感觉要 3= 了。

CF 打上 1400 了。

upd:0+10+0+0，三等都没有/kx。

arc168_b 蓝

Nim 游戏变形，可以选择每次取的石子数量上限 $k$。发现最后游戏胜利局面是每个 $a_i \mod (k+1)$ 的异或的结果。那么如果最开始异或起来就不为 $0$，那么无论取多大，异或和都不可能为 $0$，输出 $-1$。否则先考虑现在出现次数为偶数的数，可以直接不管。然后再考虑奇数的情况，设所有奇数的最大值为 $p$ ，其余的值异或起来为 $q$，那么只需要让 $k=p-1$，所有数对 $p$ 取模，只有 $p$ 会变成 $0$，因为 $p \oplus q=0$，所以 $0\oplus q \not ={0}$，这时先手必胜。

arc133_b 蓝

先考虑最朴素的 DP: 设 $dp_{i,j}$ 为 $a$ 的前 $i$ 个与 $b$ 的前 $j$ 配对的最大贡献，记 $pos_i$ 为 $i$ 在 $b$ 中的位置那么则有：

$$dp_{i,j}=\max \{dp_{i-1,pos_{k}-1}+1 \}(a_i|k)$$

但是这样会炸，于是考虑优化，首先可以用滚动数组优化空间，然后发现以上的 $\max$ 可以用单点修改，区间查询最小值的线段树来维护，于是就过了。

一道不错的 DS 优化 DP。

arc113_d 绿

枚举 $A$ 的最大值 $i$ ，那么就有：

$$ans=\sum_{i=1}^k [i^n-(i-1)^n]\times(k-i+1)$$

取模的时候注意负数。并且要特判一下 $n=1$ 或 $m=1$ 的情况。

今天好颓，感觉写不动题。

P10680 蓝

首先，朴素做法可以通过倍增来预处理出 $f_{i,j}$ 表示从 $j$ 开始后 $2^i$ 内的答案。但是这样每次修改就是 $O(n)$ 的，于是考虑根号分治，预处理出 $2^i<\sqrt{n}$ 内的答案，这样每次修改就是 $O(\sqrt{n})$，询问如果大于 $\sqrt{n}$，就暴力倍增，次数不会超过 $\sqrt{n}$。

绿：1
蓝：3
紫：0

2024.12.7

今天买了洛谷的省选计划，以后会跟着走。

今天写了一些省选计划的准备题单。

P1064 绿

树形 DP。记 $dp_{i,j}$ 为子树 $i$ 容量为 $j$ 时的最大价值，朴素转移一下就可以了。

P5050 绿

有两个证明：不能被 $A$ 集合内其它数组成的数一定在 $B$ 集合内，能被 $A$ 集合内其它数组成的数一定不在$B$ 集合内。完全背包一下即可。

是的，这个人又摆了一天（其实是再不摆烂眼睛就瞎了）

绿：2
蓝：0
紫：0

2024.12.8

今天计划完成洛谷省选计划的题单。

P6225 绿

发现当 $l,r$ 奇偶性相同时，答案一定为 $0$ 。否则只有奇偶性和 $l,r$ 相同的出现次数为奇数，才会产生贡献，所以开两个线段树分别维护区间奇数异或和，区间偶数异或和即可。

P5787 蓝

线段树分治板子题。

首先考虑如何判断一个图是不是二分图，只需要用扩展域并查集简单维护即可。

然后可以用线段树维护每个时刻有哪些边，用栈记载一下哪些是要删除的就可以了。

arc160_b 绿

简单分类讨论计数一下就可以了。

CF

C 调不出来，掉大分！

绿：2
蓝：1
紫：0

Week 总结：

绿：26
蓝：11
紫：2

练习指数：50。

除了最后两天眼睛的原因，剩下的状态都还可以，希望继续保持。

Week 2

2024.12.9

P7453 紫

发现元素之间会互相影响，那么考虑线段树维护矩阵。

操作 $1,2,3$ 其实就是把 $A,B,C$ 乘上一个单位矩阵，

调了超级久，卡常从 1min3s 卡到 25s （喜）。

学到了一个 trick: 线段树维护几个会互相影响的元素时，可以考虑使用矩阵乘法。

arc151_b 绿

发现符合条件的序列具有对称性，那么就可以求出 $A=A_p$ 的数量 $x$，答案则为 $\frac{m^n-x}{2}$。

然后就可以把每个 $i$ 到 $P_i$ 连一条边，图中的连通块个数就是答案。

arc139_b 绿

首先使 $y=min(y,a*x),z=min(z,b*x)$ 。

然后使得 $a$ 更优。

那么考虑根号分治。

如果 $a \ge \sqrt{n}$，那么每次把 $n$ 减去 $a$，判断一下即可。

否则，枚举一下选几个 $a$ 就可以了。

P6619 紫

首先考虑朴素做法。

发现温度一定时，答案就是两边总和的较小值，于是可以用树状数组来维护这个东西，然后二分就可以，复杂度 $O(n \log^2 n)$。

然后考虑去掉一只 $\log$ ，树状数组倍增就可以了。

绿：2
蓝：0
紫：2

练习指数：8。

今天整个下午都有事，所以只做了这点题。

2024.12.10

P4198 紫

发现可以把每个点连向 $(0,0)$ 的线的斜率求出来，那么答案就是斜率序列的最长上升子序列。

于是问题就转化为了：单点修改，询问全局最长上升子序列。

然后维护区间最大值，最长上升子序列的长度，唯一的难点在于 pushup 。

合并两个区间时，左区间的一定有贡献，而对于右区间，可以每次判断，如果右区间的左区间的最大值小于左区间的最大值，那么直接在右区间的右区间找即可，否则继续在右区间的左区间找。

是不是说的有点抽象

时间复杂度：$O(n \log^2 n)$ 。

VP CF

在一小时内过掉了四道题，剩下一个小时没有过掉任何题目（

不过学到了一些打 CF 时的策略。

P6492 绿

简单的线段树维护区间交错序列长度。

P1637 绿

把三元上升拆成一个单元和二元，然后用权值树状数组倒着加入就可以了。

P1558 绿

发现颜色的数量很少，那么可以把颜色 $i$ 变为 $2^i$ 的权值，用线段树维护区间或即可。

有一种状压的思想。

P2572 蓝

线段树维护区间左起的 $0$ 个数，右起的 $0$ 个数，左起的 $1$ 个数，右起的 $1$ 个数，区间 $0$ 个数，区间 $1$ 个数，区间和以及三种 tag 就可以了。

调了我将近三个小时 /lh。

P1668 绿

每次贪心地选能走最远的就可以了。

P2184 绿

发现就是求询问区间内包含的修改区间个数，直接开两个树状数组维护就可以了。

绿：6
蓝：1
紫：1

练习指数：12 。

2024.12.11

P4556 紫

线段树合并：

1. 同时遍历两颗线段树的每个节点。
2. 如果两个线段树上这个节点都有左右儿子，则遍历左右儿子。
3. 否则，如果是线段树二缺失节点，那么可以不管，如果是线段树一缺失节点，那么就可以直接让线段树一的这个子节点等于线段树二的这个子节点。
4. 如果遍历到了叶子节点，那么就直接两两相加。

这种方法把 $n$ 颗只有一个节点的线段树合并为一颗有 $n$ 个节点的线段树的时间复杂度为 $O(n \log n)$。

那么本题考虑对每个点建一颗权值线段树，然后按照树上差分的思想来转化为单点修改，最后用线段树合并维护整棵树的最大值即可。

P? & P? 绿*2

非常板的线段树，就不记题号了。

P3740 绿

看到 $n\le10^8,m\le1000$ ，于是可以想到用 $m$ 来乱搞，发现离散化后的区间影响和之前是一样的，然后暴力染色就可以了。

我好像是第一个这样做这道题的人 ( ? )

绿题 100 道了。

今天有点小摆。

绿：3
蓝：0
紫：1

练习指数：7 。

2024.12.12

P2824 紫

首先，考虑一个东西：对 $01$ 序列的一个区间排序的单次时间复杂度可以用线段树 $O(\log n)$ 实现。

具体的操作就是：查询一个区间 $1$ 的数量记为 $s$ ，然后把区间 $r-s+1 \sim r$ 的改为 $1$ ，剩下的改为 $0$ 就可以了。

那么我们考虑二分出一个 $mid$ 使得原位置 $q$ 上的数恰好为 $1$ ，那么这个二分出的 $mid$ 实际上就是答案。

时间复杂度： $O(n\log n+m\log ^2 n)$ 。

炸鱼杯

很多 CF 的 Div2 AB 难度的题，就当是练习 CF 了。 其实是因为有奖励

今天写了 $24$ 道这个题。

练习指数：10

2024.12.13

P3919 蓝

可持久化线段树维护历史信息板子题。

P3834 蓝

可持久化线段树维护静态区间第 $k$ 小。

P4137 紫

考虑用可持久化权值线段树维护 $1 \sim i$ 数 $a_i$ 最后出现的位置，那么询问 $[l,r]$ 的答案就是第 $r$ 颗权值线段树第一个出现位置小于 $l$ 的数。

炸鱼杯

写了十道题。

P3224 紫

考虑开一个并查集，然后对于每一个连通块开一颗权值线段树， 1 操作用并查集线段树合并一下就可以了。

总感觉 DS 的紫题比其他的简单好多

绿：1
蓝：2
紫：2

练习指数：13 。

2024.12.14

摆大烂。

但是下午听了洛谷网校的 DP。

2024.12.15

THUPC2025 刚开始我和 lry 就有事走了，剩下的是我家猫猫和他家狗打的。

Week 总结

绿：12

蓝：3

紫：6

练习指数：42。

这周主要在练习数据结构，学会了可持久化线段树和线段树分治等高科技。

不过有点小摆。

Week 3

我写不来 DP!

2024.12.16

P4124 蓝

数位 DP。

但是为什么不使用记忆化搜索呢？

考场上这方法性价比比数位 DP 高多了。

U498751 紫

自己出的一道毒瘤数据结构题，时隔多日终于想出了正解 (?)

首先，可以先分块，然后进行块内排序。

于是每次对于整块的修改就可以二分出最小的值，剩下的全部设为 $0$。

那么维护块内顺序就可以使用 Splay 维护，把那些要变成 $0$ 的给移动到块首。

对于散块的修改，直接暴力然后用 Splay 维护块内顺序就可以了。

总时间复杂度：$O(\sqrt{n}\log n \times q)$

思维难度不清楚，但实现难度绝对有紫黑（

P1651 绿

设 $dp_{i,j,k}$ 为考虑了前 $i$ 个数，$j\in (0,1)$ 表示选或不选。$k$ 表示右边的减去左边的高度 的最大高度。

那么就有：

$$dp_{i,j,k}=\max\left\{dp_{i-1,j,k \pm a_i}\pm a_i\right\}$$

然后用滚动数组优化一下，并且把 $k$ 全部加上 $500000$ 就可以了。

P2339 蓝

考虑 DP。设 $dp_{i,j,k}$ 为当前还有区间 $[i,j]$ 的作业没有交，人在左/右 ($k\in\{0,1\}$) 端点的最小花费时间，那么则有：

$$dp_{i,j,0}=\max(\min(dp_{i-1,j,0}+a_i-a_{i-1},dp_{i,j+1,1}+a_{j+1}-a_i),a_i.t)$$

$$dp_{i,j,1}=\max(\min(dp_{i-1,j,0}+a_j-a_{i-1},dp_{i,j+1,1}+a_{j+1}-a_j),a_j.t)$$

把 $$从后往前枚举 $j$ 就可以了。

P2727 蓝

首先预处理出组合数，然后计算每一位的贡献看是否大于 $i$ ，然后选择填 $1/0$ 就可以了。

P2744 蓝

可以爆搜，然后每次 $O(n^2)$ 用完全背包 check 一下。再加个剪枝就过了。

绿：1
蓝：4
紫：1

练习指数：13

2024.12.17

P2486 蓝

首先考虑朴素转移：设 $dp_{i,j}$ 为第 $i$ 次检票在第 $j$ 个站最多的检票数，那么则有：

$$dp_{i,j}=\max_{k=0}^{j-1} dp_{i-1,k}+\sum _{k < p \le j < q} a_{p,q}$$

但这样朴素转移是 $O(k n^4)$ 的，于是考虑用预处理贡献来优化。

首先，定义

$$w_{j,i}=\sum_{i < p \le j < q} a_{p,q}$$

则有：

$$w_{j,i}=w_{j+1,i}+sum_{j+1,i}$$

于是就可以 $O(kn^2)$ 转移了。

P2851 蓝

考虑对自己和老板分别做多重背包与完全背包，那么题目所求就是：

$$\min _{i=T}^{mx} dp1_i+dp2_{i-T}$$

注意多重背包二进制拆分优化一下。

P3554 紫

发现 $k$ 具有单调性，于是就可以二分答案，那么问题就转化为了如何判断一个解是否合法。

首先，先记 $dp_i$ 表示 $i$ 节点至少需要多少次染黑，显然有：

$$dp_i=cnt_i-k+ \sum \max(dp_s,0)$$

其中 $cnt_i$ 表示儿子数量，$s$ 表示每一个儿子。

于是考虑 B 的最优策略，B 首先肯定不会走回头路，那么几个儿子之中，B 一定会走 $dp_i$ 值最大的子节点，那么这道题就可以做到 $O(n \log n)$ 了。

VP CF Div2

过了四道题。居然场切蓝了，不过 $O(n)$ 过 $2\times 10^3$ 有点难绷。

绿：1
蓝：3
紫：1

今天造数据还花了很久。

练习指数：12

2024.12.18

P3537 蓝

首先，可以考虑按照 $m$ 把询问排序，按照 $a_i$ 把物品排序，这样满足 $a_i \le m$ 的物品集就是单调递增的。

那么记 $dp_k$ 为在当前的物品集中选出一定数量的物品满足 $\sum c_i=k$ 的 $\min b_i$ 的最大值。那么如果 $f_k > m+s$ ，说明就是合法的。

考虑转移，发现加入一个物品的转移状态是：

$$f_k=\max(f_k,\min(f_{k-c_i,b_i}))$$

那么就做出来了。

P1273 蓝

记 $dp_{i,j,k}$ 为以 $i$ 为根的子树内，在前 $j$ 个子节点中选取 $k$ 个人的最大收益，那么则有：

$$dp_{i,j,k}= \max_{p=0}^{j} (dp_{i,j-1,k-p}+dp_{s,cnt_s,p}-w_j)$$

然后用滚动数组转移一下就可以了。

P2633 紫

树剖+可持久化线段树即可。

补题

补了昨天 CF 的 D ，要用马拉车。

绿：0
蓝：3
紫：1

练习指数：10 。

2024.12.19

P3052 绿

状压 DP 板子题。

首先观察到 $n$ 很小，于是考虑状压 DP 。

记状态 $i$ 为二进制下的 $i$ 对应一些物品有没有被分组，再记一个 $siz_i$ 表示 $i$ 状态下的容量，那么有 $dp_{i | (2^j)}=\min(dp_i,dp_{i | (2^j)})$ ，于是就做出来了。

P1879 蓝

记 $dp_{i,j}$ 为前 $(i,j)$ 个格子的方案数，那么：

$$dp_{i,j}=dp_{i,j}+dp_{i-1,k}$$

其中 $j,k$ 分别表示第 $i-1,i$ 行的状态。

记录一下那些格子可以转移过来就可以了。

P1896 蓝

先把棋盘每八个分为一组然后考虑设计状态：$i$ 为每一行的形如 $010101$ （放不放皇后）。

然后记 $dp_{i,j,k}$ 表示：当前考虑到第 $i$ 行，已经用了 $j$ 个皇后，并且第 $i$ 行的状态为 $k$ 。那么则有：

$$dp_{i,j,k2}=\sum dp_{i-1,j-cnt_{k2},k1 \& k2}$$

CF

C 交了 9 发才过，输麻了。

以后多做一点 ABC 的训练。

绿：0
蓝：4
紫：0

练习指数：10

2024.12.20

最近写 DP 写的我有点精神恍惚，所以我决定写一些小清新 ARC （虽然也很费脑子）。

arc069_c 蓝

由于要最小化字典序，那么现在的最优策略一定是全局的最优策略，那么考虑贪心。

1. 如果现在最大的是 1 ，那么直接从后往前减完即可。
2. 记现在最大的位置为 $pos$，那么根据 $\max (1\sim pos-1)$ 和 $\max(pos+1\sim n)$ 的关系就可以了。

预处理出前缀最大值以及对于每一个后缀 $i$，求出 $\sum \max(0,a_j-maxx_i)$ 即可，以上过程可以用二分实现。

CF

T3 交了 6 发，写了个对拍才查出来错 /cf。

T4 乱搞了一个模拟退火。