题解：CF1508F Optimal Encoding

SegTree · 2024-11-22 09:12:42 · 题解

好题，但是我 O(q\sqrt n \log n) 没跑过 O(n^2)。

首先思考一个 O(n^2q) 的暴力，每次将区间内的数按照从小到大连成一条链，然后对于 u\to v\to w 的链如果有 u\to w 就删掉。

考虑优化，删掉等价于对于 u,v 满足 a_u<a_w<a_v 且 u,v,w 被同时包含。

于是思考 O(n^2) 做法，考虑每条边对询问的贡献。

如果对 q 个询问跑回滚莫队，那么有用的边只有 q\sqrt{n} 条，由于对 tim 的查询共有 q\sqrt{n} 个，所以离线下来做单点改后缀 \max 需要做到修改 O(\sqrt n) 查询 O(1) 来把复杂度做到 O(q\sqrt n)。

给每条边求出最左满足合法的点、最右满足合法的点可以使用主席树，当然也可以在做二维数点（使用同样的方式平衡复杂度），如果写后者配合秃子酋长的不插入莫队即可做到严格 q\sqrt n，笔者偷懒写了 q\sqrt n\log n 结果飞慢。