P8337 [Ynoi2004] rsxc

· · 题解

一点也不卡常的小清新题。

考虑如何判定一个区间是好的。显然充要条件是，把所有数插入线性基后，设线性基元素个数为 k，那么区间内有 2^k 种不同的数。

考虑预处理。扫描线枚举右端点 i，维护一个前缀线性基（CF1100F 第一篇题解），那么将 pos 数组排序后，对于每个 k，左端点在 [pos_{k + 1} + 1, pos_k] 中的区间的线性基恰好有 k 个元素（pos 下标从 1 开始，且认为 pos_0 = i）。如果我们能求出 h_{i, k} 表示，[1, i] 中每种数从右往左第一次出现的位置中的第 2^k 大的值，那么对于一个 (i, k)，合法左端点区间就是 [pos_{k + 1} + 1, h_{i, k}]。

首先前缀线性基插入的时候 pos 数组至多删除一个数、加入一个数，所以可以使用类似插入排序的方法。这部分复杂度为 O(n \log V)。

接下来的问题是求出 h_{i, k}。我们维护一个集合 S，里面的数是 [1, i] 中每种数从右往左第一次出现的位置。每次右端点变化（i - 1 \to i）时，设 a_i 上一次出现位置为 x，那么对 S 的修改就是删除 x 再加入 i。设集合中 > x 的元素个数为 c，那么 h_{i, \ast} 相较于 h_{i - 1, \ast} 的变化是，\forall j \in [0, \left\lfloor{\log c}\right\rfloor]，h_{i, j} 变为 h_{i - 1, j} 在 S 中的后继，其他的数不变。特别地，若 [1, i] 不同的数的数量为 2^k 且 a_i 在 [1, i] 中第一次出现，那么 h_{i, k} 变为 S 的最小值。可以用树状数组维护 S。这部分复杂度为 O(n \log n)。

这样我们能求出对于每个 (i, k) 的合法左端点区间 [L_{i, k}, R_{i, k}]。

考虑查询。先写个暴力，枚举右端点 i，答案即为 \sum\limits_{i = l}^r \sum\limits_{k = 0}^{\left\lfloor{\log n}\right\rfloor} \max(0, R_{i, k} - \max(L_{i, k}, l) + 1)。

考虑优化。先枚举第二维 k。首先一个比较显然的性质是，L_{i, k} 和 R_{i, k} 是递增的。那么我们可以把 [l, r] 所有区间分成右端点 < l、右端点 \ge l 且左端点 < l 和左端点 \ge l 三部分。对于第一部分的区间无贡献；对于第二部分的区间，贡献为 \sum R - l + 1；对于第三部分的区间，贡献为 \sum R - L + 1。我们可以预处理出，对于每个 (x, k) 第一个 L_{i, k} \ge x 的 i 和第一个 R_{i, k} \ge x 的 i，还有 L_{i, k}, R_{i, k} 的前缀和，那么就可以 O(1) 对每个 k 回答询问。这部分复杂度为 O(q \log n)。

总时间复杂度为 O(n \log V + (n + q) \log n)。至于空间，我们只需要开 2 个值域为 O(n)、大小为 n \times \log n 的数组和 2 个值域为 O(n^2)、大小为 n \times \log n 的数组，以及 O(1) 个大小为 n 的数组，瓶颈在于前者。可以把它们压成 2 个 unsigned long long 数组，这样空间大约为 200MB。

代码可以在 QOJ 上看。