【题解】CF1793F Rebrending

TallBanana · 2025-02-27 20:07:39 · 题解

题面传送门

暴力美学。

先离线一下，防止空间爆炸。

对于查询 [l,r] 的长度进行根号分治：

• 类似地，右端点扫描线，维护 $g_i$ 表示最大的、满足 $[g_i,r]$ 的答案 $\le i$ 的左端点。每次更新对 $a_r\pm x$ 的更新答案即可。查询可以考虑双指针。

总复杂度 O(n\sqrt n+q\log q)， 关于 q 的瓶颈在于排序。

膜拜 larsr 给我这么多 nb 的题目，虽然我一个都做不出来。