题解

问题分析

K的算法实际上是对一棵以餐厅1为根的树进行BFS遍历的过程：

• 第$i$天访问的餐厅对应BFS遍历的第$i$个节点
• $A_i$表示该节点的子节点数量
• 条件保证每个餐厅（除1外）恰好被推荐一次，对应树边

关键转化

1. BFS序列的必要条件

对于合法的BFS出度序列$A_0, A_1, \ldots, A_{N-1}$：

1. $\sum_{i=0}^{N-1} A_i = N-1$（总边数条件）
2. 定义前缀和调整：$s_i = \sum_{j=0}^i A_j - (i+1)$
   • 必须满足$s_i \geq 0$ 对所有 $0 \leq i < N-1$
   • 且$s_{N-1} = -1$

2. 循环移位问题

我们需要找到所有$k$，使得$B$的循环移位$B^{(k)} = [B_k, B_{k+1}, \ldots, B_{k+N-1} \bmod N]$满足上述条件。

算法思路

1. 构造扩展数组

将$B$复制一份：$B' = B + B$ 这样$B^{(k)}$对应$B'[k:k+N]$

2. 前缀和预处理

计算$B'$的前缀和：

$$P[i] = \sum_{j=0}^{i} B'[j]$$

那么$B^{(k)}$的前$i$项和为：$P[k+i] - P[k-1]$（调整边界）

3. 条件检测

对于移位$k$，需要检查：

1. 总边数：$P[k+N-1] - P[k-1] = N-1$
2. 对于所有$0 \leq i < N-1$：$$P[k+i] - P[k-1] - (i+1) \geq 0$$
3. 当$i = N-1$时：$$P[k+N-1] - P[k-1] - N = -1$$

4. 最小值检测

定义：

$$f(k) = \min_{0 \leq i < N} \left(P[k+i] - P[k-1] - (i+1)\right) $$

合法条件为：$f(k) \geq 0$ 且 总边数条件成立。

高效实现

滑动窗口最小值

使用双端队列维护大小为$N$的窗口最小值：

• 在$B'$上计算$Q[i] = P[i] - i$
• 对每个$k$，检查$\min_{k \leq j < k+N} Q[j] - Q[k-1] \geq 0$

动态维护

对于交换操作$B_x \leftrightarrow B_y$：

• 更新$B'$中两个位置的值
• 重新计算受影响的前缀和区间
• 使用线段树维护$Q$数组的区间最小值

复杂度分析

• 初始检测：$O(N)$使用滑动窗口
• 每次交换：$O(\log N)$更新线段树
• 总复杂度：$O(N + Q\log N)$

样例验证

对于初始$B = [1,2,0,0,1]$：

• 扩展$B' = [1,2,0,0,1,1,2,0,0,1]$
• 计算$Q = [1,2,1,0,0,1,2,1,0,0] - [0,1,2,3,4,5,6,7,8,9]$ $= [1,1,-1,-3,-4,-4,-4,-6,-8,-9]$
• 检测每个$k$的窗口最小值

最终发现只有$k=4$满足条件。

总结

本题核心在于：

1. 将餐厅推荐过程识别为树BFS遍历
2. 推导BFS出度序列的数学特征
3. 使用滑动窗口和数据结构高效检测所有循环移位
4. 支持动态更新操作

通过巧妙的数学转化和数据结构应用，可以在大规模数据下高效解决问题。