P5313 [Ynoi2011] WBLT 题解

· · 题解

好像是我第一次给 Ynoi 写题解？

对于这种询问特别非常规的题，大概很难用一般的数据结构来维护它。所以可以考虑用 bitset 存下数字的出现情况，然后用一些 bitset 的神秘操作把复杂度除个 64，然后你就发现可以过了。

这道题也是同理。想到用 bitset 之后就比较好办了。首先用莫队提取出一段区间中代表数字出现情况的 bitset，然后把这个大 bitset 从 0 开始分裂成一些长度为 b 的小 bitset。显然，如果将分裂出来的这些 bitset 全部 and 起来，第一次全为 0 时的小 bitset 的下标（下标从 0 开始）即为本次询问的答案。

这样做当分出的 bitset 数 \leq \frac{V}{w} 时，复杂度能够保证单次操作 O(\frac{V}{w})。但是当分出的 bitset 数过多，即 b < w 时，复杂度就退化到 O(\frac{V}{b})。由于本题出题人，这种做法肯定被卡掉了。考虑类似根号分治，对 b < w 的情况特殊处理。

由于此时 b < w，考虑一种比较暴力的方法。对不同的 b 各做一次莫队。开一个长为 b 的 bitset 数组。把所有 \bmod b 同余的值除以 b 后放进同一个 bitset 里面。询问时对每个 bitset 求 mex 的最大值即可。莫队部分的时间复杂度 O(n\sum{\sqrt{m_i}})，bitset 部分的复杂度与上一段过程的总和为 O(\frac{Vm}{w})。

因此总时间复杂度为 O(\frac{Vm}{w}+n\sum{\sqrt{m_i}})。

但是 std::bitset 不支持分裂操作，所以这道题的代码难度在于手写 bitset。

因此接下来这篇题解将着重介绍如何手写 bitset。因为这是本人第一次手写 bitset。所以参考了一下别的题解。

设 w=64，则 x 在 bitset 中的下标为 \frac{x}{w}=x>>6，压位后在数中的二进制位数为 x \bmod w = x \& 63。下文中设 div=6,mod=63，size 为该 bitset 中压位后数的个数，v 为用于存储这些数的 vector。

  1. 一些基础操作

    inline void reset() {
  for (int i = 0; i <= size; i++)
    v[i] = 0;
}
inline void set() {
  for (int i = 0; i <= size; i++)
    v[i] = ~0ull;
}
inline void set1(int x) {
  v[x >> DIV] |= 1ull << (x & MOD);
}
inline void set0(int x) {
  v[x >> DIV] &= ~(1ull << (x & MOD));
}
inline bool any() {
  for (int i = 0; i <= size; i++)
    if (v[i])
      return 1;
  return 0;
}
inline void operator&=(const Bitset &q) {
  for (int i = 0; i <= size; i++)
    v[i] &= q.v[i];
}

    这些操作比较简单，不解释。

  2. 初始化函数 init()

    inline void init(int x, bool val) {
  v.resize((x >> DIV) + 2), size = x >> DIV, val ? set() : reset();
}

    这个函数中需要注意的是 vector 的空间必须要往后多开 1 个，方便后续的 split()。

  3. 求第一次 0 的出现位置 mex() 操作

    inline int mex() {
  for (int i = 0;; i++)
    if (~v[i])
      return i << DIV | __builtin_ctzll(~v[i]);
}

    从 v_0 开始一直往后找，只要遇到第一次 v_i 中包含 0。则返回答案。其中 i << DIV 表示前面的位数，__builtin_ctzll() 是一个 gcc 的内建函数，用于 O(1) 计算一个 unsigned long long 类型的数的的二进制表示中末尾 0 的个数。用 ~ 进行取反使其变为计算 v_i 末尾 1 的个数。

  4. 分裂操作 split()

    正是因为这个操作才逼我们手写 bitset。

    inline void split(int len, Bitset res[]) {
  for (int i = 0; i <= V / len + 1; i++)
    res[i].init(len, 0);
  int begin = 0, need = res[0].size, place = 0, cur = 0;
  for (int i = 0; i <= size; i++) {
    if (place == need)
      res[cur].v[place] = (begin + (len & MOD) <= MOD)
                        ? (v[i--] & filter[begin + (len & MOD)]) >> begin
                        : v[i] >> begin | (v[i + 1] & filter[begin + (len & MOD) & MOD]) << (W - begin),
      begin = begin + (len & MOD) & MOD, place = 0, cur++;
    else
      res[cur].v[place] = begin ? (v[i] >> begin | (v[i + 1] & filter[begin]) << (W - begin)) : v[i], place++;
  }
}

    首先把 res_i 初始化。

    设 $begin$ 表示当前做到大 bitset 中数的哪个二进制位（范围为 $[0,w-1]$），$need$ 表示一个小 bitset 中数的个数，$place$ 表示当前做到的数在小 bitset 中的下标，$cur$ 表示当前做到的小 bitset 的编号。 - 当做到该小 bitset 的最后一个数时，加入小 bitset 的数的位数应该为 $len \bmod w = len \& 63$。 - 当大 bitset 的第 $i$ 个数足够时：将大 bitset 中第 $i$ 个数的 $[begin,begin+len \bmod w-1]$ 位加入小 bitset。 - 当大 bitset 的第 $i$ 个数不够时，需要从第 $i+1$ 个数借位。将第 $i$ 个数的 $[begin, w-1]$ 位和 第 $i+1$ 个数的 $[0,(begin+(len \bmod w)) \bmod w - 1]$ 位加入小 bitset。 - 做到该小 bitset 的最后一个数之前，加入小 bitset 的数的位数应该为 $w$。 - 当大 bitset 的第 $i$ 个数足够，即 $begin=0$ 时，将整个数加入小 bitset。 - 当 $begin \neq 0$ 时，需要从第 $i+1$ 个数借位。将第 $i$ 个数的 $[begin, w-1]$ 位和 第 $i+1$ 个数的 $[0,begin-1]$ 位加入小 bitset。 这里就能看出之前在 `init()` 中把 vector 往后多开 1 个的作用了。可以让我们不用特判 $i=size$。否则要加几行特判 $i=size$ 防止 $i+1$ 越界。

之后的代码就不难写了。根据 Ynoi 传统，不给出完整代码。

bitset 部分代码。