问题分析

我们需要找到一个二进制字符串中未出现的最短子串的长度。关键观察是：

• 长度为 $k$ 的所有可能子串有 $2^k$ 个
• 如果某个长度 $k$ 的所有 $2^k$ 个子串都出现了，那么长度 $k$ 就不是答案
• 答案是最小的 $k$，使得至少有一个长度为 $k$ 的子串没有出现

核心算法

算法框架：暴力枚举 + 滑动窗口更新

由于 $n \leq 100000$，我们不能检查所有可能的子串。但关键观察是：

• 答案不会太大（最多约 $\log n$）
• 实际上，当 $n$ 较大时，答案最多为 $O(\log n)$

算法步骤

1. 初始化：检查所有长度 $\leq L$ 的子串（$L = \min(n, 23)$）
2. 维护计数：cnt[i] 表示出现的不同长度为 $i$ 的子串数量
3. 查询答案：找到最小的 $i$ 使得 cnt[i] < 2^i
4. 更新操作：当修改一个字符时，重新计算受影响的子串

关键数据结构

• vis[1<<24]：标记数组，记录每个子串（编码为整数）的出现次数
• cnt[L+1]：记录每个长度出现的不同子串数量
• L = min(n, 23)：最大检查长度（由数据范围决定）

算法步骤详解

1. 初始扫描

for (int i = 0; i < n; i++) {
    int w = 1;
    for (int j = i; j < min(i + L, n); j++) {
        w = (w << 1) | (s[j] - '0');
        if (!vis[w]) cnt[j - i + 1]++;
        vis[w]++;
    }
}

对每个起始位置，生成所有长度 $\leq L$ 的子串并计数。

2. 答案计算

auto calc = [&]() {
    for (int i = 1; i <= L; i++)
        if (cnt[i] != (1 << i))
            return i;
    return -1;
};

找到第一个长度 $i$，使得长度为 $i$ 的子串没有全部出现。

3. 更新处理

当修改位置 $x$ 时：

// 第一步：移除旧子串的影响
for (int j = max(x - L + 1, 0); j <= x; j++) {
    int w = 1;
    for (int k = j; k < x; k++)
        w = (w << 1) | (s[k] - '0');
    for (int k = x; k <= min(j + L - 1, n - 1); k++) {
        w = (w << 1) | (s[k] - '0');
        if (vis[w] == 1) cnt[k - j + 1]--;
        vis[w]--;
    }
}

// 第二步：修改字符
s[x] = ((s[x] - '0') ^ 1) + '0';

// 第三步：添加新子串的影响
for (int j = max(x - L + 1, 0); j <= x; j++) {
    int w = 1;
    for (int k = j; k < x; k++)
        w = (w << 1) | (s[k] - '0');
    for (int k = x; k <= min(j + L - 1, n - 1); k++) {
        w = (w << 1) | (s[k] - '0');
        if (!vis[w]) cnt[k - j + 1]++;
        vis[w]++;
    }
}

算法标签

• 字符串处理 (String Processing)
• 滑动窗口 (Sliding Window)
• 暴力枚举 (Brute Force)
• 位运算优化 (Bit Manipulation)
• 子串编码 (Substring Encoding)

复杂度分析

• 预处理：$O(nL)$，其中 $L = 23$
• 每次查询：$O(L^2)$（受影响的窗口数量 × 窗口长度）
• 总复杂度：$O(nL + mL^2)$

关键技巧

1. 子串编码

w = (w << 1) | (s[k] - '0');

将二进制子串编码为整数，便于快速查找和计数。

2. 局部更新

只更新受修改影响的子串：

• 所有包含位置 $x$ 且长度 $\leq L$ 的子串
• 这些子串的起始位置在 $[x-L+1, x]$ 范围内

3. 答案上界

由于最多有 $n$ 个不同的长度为 $k$ 的子串，且总可能数为 $2^k$，因此：

• 当 $2^k > n$ 时，必然有某些子串缺失
• 所以答案最多为 $\lceil \log_2(n+1) \rceil$

4. 空间优化

使用 $2^{24}$ 大小的数组，可以处理长度 $\leq 23$ 的所有子串。

样例验证

对于样例1：

• 初始字符串 001010：
  • 长度1：出现 0,1，全部出现
  • 长度2：出现 00,01,10，缺少 11，答案为2
• 修改后 001011：
  • 长度1,2：全部出现
  • 长度3：缺少 110，答案为3
• 再次修改 011011：
  • 长度2：缺少 00，答案为2

正确性证明

1. 完备性：检查所有长度 $\leq L$ 的子串，由于答案上界为 $O(\log n)$，$L=23$ 足够覆盖所有可能答案。

2. 正确性：通过精确计数确保找到第一个缺失的长度。

3. 高效性：利用局部性原理，每次更新只处理受影响的部分。

该解法通过巧妙的问题转化和位运算优化，在合理的时间内解决了这个看似复杂的问题。