【扫描线】即便看不到未来

WeLikeStudying · 2022-02-17 12:55:32 · 题解

• 谨以此题解，纪念gzp_26867，一位“珂学家”。
• 当时他被迫退役，踌躇后托我实现这个心愿。
• 这几年来，一路浮沉，长路漫漫，我也多次在退役的边缘徘徊。
• 忽然发现有道题目好像已经在我的能力范围之内，于是写了这道题目。
• “即便看不到未来”个人认为是个极好的名字，看似灰暗，细细品味之下，才能看到讲述者的坚忍。
• 谨以此题解，与君共勉。

题意

• 题目链接。
• 对于 k\in[1,10] 静态查询一个区间内部的数组成的长度为 k 的极大值域连续段的个数。
• 区间的极大值域连续段即区间内的数排序后去重形成的不能向左或向右拓展的值域连续段。
• 数列长度，询问次数 n,m\le 10^6。

分析

• 首先不强制在线，那么我们可以想到什么离线做法？
• 结合数据范围，扫描线是合理的，于是我们把区间查询按区间右端点排序，然后我们尝试维护某些后缀的信息。
• 而这个维护的信息，显然是维护后缀值域连续段的个数，由于这题 k 很小，我们可以开 k 个数据结构维护。
• 由于想到我们要维护的是连续段信息，我们很容易想到维护一个类似链表的结构，每个点的前驱和后继代表它在值域上的大 1 数和小 1 数的前于扫描右端点 r 的最后位置（不存在即为空），有序表的更新存在链接，也存在覆盖。
• 我们发现这个有序表可以有效地简化问题，现在我们的查询转化为把有序表中位置不小于 l 的元素保留下来形成的连通块的信息。
• 那么如何更新信息？
• 我们不妨看看它影响了哪些连续段，这里有个形象的图：
• 没错，如果我们暴力向左扫描，我们将会看到，至多会影响 O(k) 个点的贡献（它必须是边缘是扫描到的右端点的数的连续段，且长度不超过 10），即使我们一一更新，复杂度也是完全可接受的。
• 我们使用 k 棵树状数组维护信息，就可以得到 O(nk\log n+m(\log n+\log m)) 的复杂度，瓶颈主要是前一项。
• 代码实现，完全不卡常。