P11367 [Ynoi2024] 魔法少女网站第二部 题解

Nopain · 2025-04-09 23:11:37 · 题解

一些字打了又删，犹豫再三也没把老年选手的碎碎念放出来，无病呻吟应该是没人愿意看的。

以下视 n,m 同阶，于是不再区分二者。

考虑分治，处理跨过分治中心 \text{mid} 的询问。

思考一下这个来回跳的过程，大概就是先在一边跳一会，然后跨过 \text{mid}，再跳一会再跳回来，可以将跳跨过 \text{mid} 视为先跳到 \text{mid} 再接着跳，于是两边分为独立的过程，于是思考两边各自贡献了多少距离，不妨只考虑右边。

显然只有右边排序后 a_i,a_j 相邻的点对才有贡献。贡献形式有如下两种：

• 若左侧不存在 k 满足 a_i<a_k<a_j，则我们会直接从 a_i 跳到 a_j，答案贡献距离为 c_0=|i-j|。

• 否则会从 a_i 跨过 \text{mid} 跳到左边，不知道跳多少次再跳回到 a_j，只算右边的贡献是 c_1=i-mid+j-mid。

所以我们需要计算所有点对 (a_i,a_j) 在左侧是否存在中间的数，可以想到我们只需要保留所有在其之间的数中最靠右的，设其位置为 p_i。则在询问时对右侧包含的每个点对考虑，若 ql\le p_i，则 (a_i,a_j) 贡献为 c_1，否则为 c_0。

以上都是暴力，考虑如何用数据结构维护这个过程。考虑到点对 (a_i,a_j) 维护着一个分界点 p_i，而点对的合并是容易的，将两个 p 取 \text{max} 即可。而分裂是困难的，需要额外的数据结构维护。于是我们从 \text{R} 向 \text{mid} 倒着扫描线，维护删除点对的过程。删除一个点 a_i 时删除其前驱点对 (a_p,a_i) 和后继点对 (a_i,a_s) 的贡献，再加入点对 (a_p,a_s)，前驱和后继可以用链表维护，这里共进行了 O(n\log n) 次修改。而查询时则变为了动态一维数点，使用树状数组即可做到 O(n\log^2 n)。

我们发现修改和查询存在不平衡，考虑使用 O(n^{\epsilon}) 分块来平衡这一点。如果以前见过这个套路即可平衡得时间复杂度为 O(\frac{n\log^2 n}{\log\log n})。不会也没关系，我下面讲。

考虑线段树即可视为 2 叉树，分块可视为 \sqrt n 叉树。那么一般的，用一个 h 叉树维护长为 n 的序列，树高为 \log_h n。此时单点修改复杂度为 O(\log_h n)，查询复杂度为 O(h\log_h n)，当然两边复杂度也可以反过来。

回到上面的问题，我们有 O(n\log n) 次修改与 O(n) 次查询。若使用 h 叉树使得复杂度最优则需要两侧复杂度相同，即 n\log n \log_hn=nh\log_hn，解得 h=\log n，运用换底公式带入得复杂度为 O(\frac{n\log^2 n}{\log\log n})。

看起来大部分人都能轻松通过，但我被卡了好久的常，所以在这里说一下我的卡常方法：

0. 加快读，少开 \text{long long}，没询问就不要跑这一大坨。

1. 扫描线建议按询问排序扫，扫完所有询问了即使后面还有点对需要删就可以不用额外加点对了，访问链表顺次删除贡献即可。

3. 递归到底层可以跑暴力，我设的阈值为 \text{len}\le 65，瞎试出来的，其实可以跑一下看看分治长度都有哪些。

4. 随着分治区间长度不同，一维数点的值域大小不总是 n。随着分治区间减小可以缩小维护范围，能小一些常数。

5. 当分治子树内总询问数不超过某阈值，可以直接将内部排序跑暴力。我试过没有显著效果，但如果卡不进去可以试试。

6. 能加 \text{inline} 就加，有效果。

7. 洗把脸多交几次就过了，亲测有用。

需要代码的可以私信我，但我写的一坨屎，还是别来找我污染你数据库了吧。