title
给你一个整数 n 和一个在范围 [0, n - 1] 以内的整数 p ，它们表示一个长度为 n 且下标从 0 开始的数组 arr ，数组中除了下标为 p 处是 1 以外，其他所有数都是 0 。
同时给你一个整数数组 banned ，它包含数组中的一些位置。banned 中第 i 个位置表示 arr[banned[i]] = 0 ，题目保证 banned[i] != p 。
你可以对 arr 进行 若干次 操作。一次操作中，你选择大小为 k 的一个 子数组 ，并将它 翻转 。在任何一次翻转操作后，你都需要确保 arr 中唯一的 1 不会到达任何 banned 中的位置。换句话说，arr[banned[i]] 始终 保持 0 。
请你返回一个数组 ans ，对于 [0, n - 1] 之间的任意下标 i ，ans[i] 是将 1 放到位置 i 处的 最少 翻转操作次数，如果无法放到位置 i 处，此数为 -1 。
- 子数组 指的是一个数组里一段连续 非空 的元素序列。
- 对于所有的
i，ans[i]相互之间独立计算。 - 将一个数组中的元素 翻转 指的是将数组中的值变成 相反顺序 。
示例 1：
输入：n = 4, p = 0, banned = [1,2], k = 4
输出：[0,-1,-1,1]
解释：k = 4，所以只有一种可行的翻转操作，就是将整个数组翻转。一开始 1 在位置 0 处，所以将它翻转到位置 0 处需要的操作数为 0 。
我们不能将 1 翻转到 banned 中的位置，所以位置 1 和 2 处的答案都是 -1 。
通过一次翻转操作，可以将 1 放到位置 3 处，所以位置 3 的答案是 1 。
示例 2：
输入：n = 5, p = 0, banned = [2,4], k = 3
输出：[0,-1,-1,-1,-1]
解释：这个例子中 1 一开始在位置 0 处，所以此下标的答案为 0 。
翻转的子数组长度为 k = 3 ，1 此时在位置 0 处，所以我们可以翻转子数组 [0, 2]，但翻转后的下标 2 在 banned 中，所以不能执行此操作。
由于 1 没法离开位置 0 ，所以其他位置的答案都是 -1 。
示例 3：
输入：n = 4, p = 2, banned = [0,1,3], k = 1
输出：[-1,-1,0,-1]
解释：这个例子中，我们只能对长度为 1 的子数组执行翻转操作，所以 1 无法离开初始位置。
提示：
1 <= n <= 1050 <= p <= n - 10 <= banned.length <= n - 10 <= banned[i] <= n - 11 <= k <= nbanned[i] != pbanned中的值 互不相同 。
solution
在线BFS
class SortedListUtil:
import sortedcontainers
'''
删除有序列表的区间, 并返回这个区间的列表
'''
def erase_internal(self, sl: sortedcontainers.SortedList, left: int, right: int):
l = sl.bisect_left(left)
r = sl.bisect_right(right) - 1
res = []
if right >= 0:
for i in range(l, r + 1):
res.append(sl[i])
del sl[i]
return res
'''
查询某个区间的坐标 [left,right]的值得区间
'''
def query_internal(self, sl: sortedcontainers.SortedList, left: int, right: int):
l = sl.bisect_left(left)
r = sl.bisect_right(right) - 1
if r >= l:
return [l, r]
return [-1,-1]
class Solution:
def minReverseOperations(self, n: int, p: int, banned: List[int], k: int) -> List[int]:
import sortedcontainers
INF = float('inf')
bset = set(banned)
ls = [sortedcontainers.SortedList() for _ in range(2)]
for i in range(n):
if i != p and i not in bset:
ls[i % 2].add(i)
ans = [INF for _ in range(n)]
def getRange(i: int) -> Tuple[int, int]:
"""反转长度为k的子数组,从i可以到达的左右边界闭区间."""
return max(i - k + 1, k - i - 1), min(i + k - 1, 2 * n - k - i - 1)
q = collections.deque()
q.append(p)
ans[p] = 0
sutil = SortedListUtil()
while q:
pop = q.popleft()
# 左右区间index
l, r = getRange(pop)
# 找到sort list的index
li, ri = sutil.query_internal(ls[l % 2], l, r)
if li == -1: continue
for i in range(li, ri + 1):
v = ls[l % 2][i]
ans[v] = ans[pop] + 1
q.append(v)
for i in range(ri, li - 1, -1):
del ls[l % 2][i]
ans = [-1 if v == INF else v for v in ans]
return ans