XYD 2025.7.15 记录

· · 个人记录

早上来打模拟赛，先三题看了一下。

T2 感觉在 CF 上面看到过，但是不太会写。

T1 看到第一反应拓扑然后标拓扑序。对于操作 2，3 非常容易，预处理以每个点为结尾的最长路记为 ori_i 以及以每个点为开头的最长路 rev_i，具体做法就是建立超级源点连接所有入度为 0 的点然后图上 dp。建反图同样操作即可求出 rev_i。

操作 2 答案即为 ori_i+rev_i，操作 3 答案即为 rev_u+ori_v+1。

加上暴力 20 pts 总共只有 30 pts，开始思考操作 1

考虑删去点 u 对于整个答案的影响，感觉应该类似于拓扑序小于他的和大于他的两个加一加，然后如果 u 是割点就两个取 max，但是我又想到如果拓扑序和 u 是同一层的点怎么处理（事实证明如果在同一层被剥出来那么他们两个根本不会连边，这个我下午 17:00 才突然意识到 qwq）。

然后我就不会了，这导致我那个链的部分分也不会写，这时候过了 1H 多，写完 30 pts 暴力去看 T2。

T2 并不能用线段树合并，感觉答案肯定要 \mathcal{O}(n\log n) 但是我就是没想到分块 \mathcal{O}(n\sqrt n) 的复杂度，后来我甚至开始想二分，因为统计 mex 要把数字扔到权值线段树或者树状数组上面，然后发现就是找到第一个权值为 0 的。二分 mex 之后判断 mid 前面是不是全都是 1，但是不可行。

还剩一个多小时，先打前 15 pts 暴力，后面离线不带修的直接套个莫队上去，在后面在线不带修的脑子已经不清楚了，想到主席树但是不知道怎么写。

T3 当时想的就是先放了，继续去想 T1，T2 的解法，很显然我没想出来。

中午听 GYC 说了 T2 的做法，用 \frac{n}{64} 个 unsigned long long 模拟 bitset 来做，复杂度 \mathcal{O}(qn^{\frac{2}{3}}+\frac{nq}{64}) 算一下差不多 2 \times10^8 有点卡，像是乱搞。

下午听讲题，T1 因为上午的问题再将分层的时候没听明白，T2 差不多听懂了，但是线段树的做法感觉比较难实现，讲完差不多 2:30，发点心的时候写完 T2，然后开始磕 T1，一边写一边理解，出去锻炼的时候突然想明白了。。。看来还是不能一直坐在电脑前面，会降智的有时候晚上改不出来的题目第二天早上过来一眼丁真。

然后吃完饭开始写总结，差不多写到 18:50。

改不出来 19:10 准备对拍，但是老师讲了一些话，然后去问了朱老师怎么随机 DAG，19:30 开始写对拍，19:50 找到错，感觉对拍真的好快，错误就是拓扑序 topo[i] 写成 i，太愚蠢了。

总结就是效率还要提高。