日记 - 伊埃斯的博客站

少年啊成为神话吧！

T1

愿天堂没有 27。

T2

愿天堂没有码力题。

T3

想到根号分治。~~我也不知道怎么想到的~~。

发现我们暴力也具有优越性。因为它的时间复杂度是 $O(n)$ 的，与 $m$ 无关。那么在 $m$ 较大的时候，暴力就是很优的。我们可以把 $m \ge \sqrt{n}$ 的时候跑暴力。因为至多只有 $\sqrt{n}$ 个询问拿来跑暴力，所以暴力这块的时间复杂度就是 $O(n \sqrt{n})$ 。

考虑 $m < \sqrt{n}$ 如何做。考虑维护一个 $f_{i,j}$ 表示左端点 $\in [1,x_i]$ ，右端点 $\in [x_j,n]$ 的区间数。考虑如何用 $f$ 计算 $ans$ 。我们可以用容斥原理。首先，考虑一个只覆盖 $[x_i,x_i]$ 的区间。那么只有 $f_{i,i}$ 能计算它。 $ans$ 加上 $f_{i,i}$ 。继续考虑只覆盖 $[x_i,x_{i + 1}]$ 的区间。那么它会被 $f_{i,i},f_{i + 1,i + 1}$ 计算它。但是它覆盖了两个点。所以它不能被计算， $ans$ 加上 $-2 f_{i,i + 1}$ 。经过一番推导，我们发现容斥系数长这个样子： $1,-2,2,-2,2,\dots$ 。我们就可以计算了。如何维护 $f$ ？把每个 $f_{i,j}$ 看成一次询问。将每次询问离线，有 $O(n)$ 个询问。用树状数组维护即可，预处理时间复杂度 $O(n\log n)$ ，每次询问 $O(m^2 \log n)$ 。我们发现，这是一个二次函数形式的复杂度，要卡满 $m$ 就得是最大值 $\sqrt{n}$ ，但是这样就最多只有 $\sqrt{n}$ 个询问这样，总的复杂度就是 $O(n\log n \sqrt{n})$

照理来说 $O(n\sqrt{n})$ 都跑不过 $5 \times 10^5$ ，但是这玩意带 $\log$ 都跑得过，数据是不是有点水啊？

后日谈

砸场没砸过，我的自尊心和明日香的自尊心一样，碎了。

昨天晚上的 CF，我居然还没有掉下青，说明青的实力十分的不行，得往蓝冲了。

Thanks for reading!

日记

周三 4月 23 2025

494 字 · 2 分钟

life 日记