BFS + Even/Odd segment tree
Intuition / approach\n\nThere are several hard subproblems within this problem, but the main one is to figure out how the 1s can be efficiently updated after a 
# Intuition / approach\n\nThere are several hard subproblems within this problem, but the main one is to figure out how the 1s can be efficiently updated after a subarray is reversed.\n\nAfter discovering that a reverse affects a range of numbers only at either even or odd positions, I went for a segment tree approach where there is one tree for odd and one for even numbers.\n\nThe segment tree is responsible for keeping track of whether a range of odd or even numbers consists of only banned or reached numbers. The result is also split into odd/even.\n\nThen, using BFS, elements are visited in order, updating ranges of odd/even numbers based on the subarray length and the element index.\n\nThis implementation is full of foot-guns. If you can find a simpler approach, then I recommend using it. I\'m just sharing it for reference or if some lazy person wants to copy-paste the solution.\n\n# Complexity\n\n- Time complexity: `O(n*log(n))`\n- Space complexity: `O(n)`\n\n# Code\n```\nfunc minReverseOperations(n int, p int, banned []int, k int) []int {\n\t// This problem is quite hard.\n\t//\n\t// First, it is worth noting that we want to work with odd and even\n\t// positions in the array separately. This is because an odd k can only\n\t// reverse 1 into positions at an even distance from the current position.\n\t// Similarly, with an even k, the 1 can only be moved into an odd distance\n\t// from the current position.\n\t//\n\t// By splitting the array into odd and even positions, the reachable\n\t// positions can be described as a range rather than single positions,\n\t// making it possible to do a range update with a segment tree.\n\t//\n\tm := 1\n\tneven := n/2 + n&1\n\tfor m < neven {\n\t\tm *= 2\n\t}\n\tvar segtree [2][]bool\n\tsegtree[0] = make([]bool, m*2)\n\tsegtree[1] = make([]bool, m*2)\n\n\tvar res [2][]int\n\tres[0] = make([]int, neven)\n\tres[1] = make([]int, n/2)\n\tfor i := range res {\n\t\tfor j := range res[i] {\n\t\t\tres[i][j] = -2\n\t\t}\n\t}\n\n\t// mark marks the provided index with the provided value\n\tmark := func(segtree []bool, res []int, i, val int) {\n\t\tsegtree[m+i] = true\n\t\tfor k := (m + i) / 2; k >= 1; k /= 2 {\n\t\t\tsegtree[k] = segtree[k*2] && segtree[k*2+1]\n\t\t\tif !segtree[k] {\n\t\t\t\tbreak\n\t\t\t}\n\t\t}\n\t\tif i < len(res) {\n\t\t\tres[i] = val\n\t\t}\n\t}\n\n\tfor _, i := range banned {\n\t\tmark(segtree[i&1], res[i&1], i/2, -1)\n\t}\n\n\t// Mark out-of-bounds elements as seen\n\tfor i := neven; i < m; i++ {\n\t\tmark(segtree[0], res[0], i, -1)\n\t}\n\tfor i := n / 2; i < m; i++ {\n\t\tmark(segtree[1], res[1], i, -1)\n\t}\n\n\ttype pos struct {\n\t\ti   int\n\t\todd int\n\t}\n\n\t// Update marks the range\n\t// [lo,hi] is the current range in the segment tree\n\t// [qlo,qhi] is the range being updated by the caller\n\t// j is 0 if using even segtree, otherwise 1\n\tvar update func(segtree []bool, res []int, next *[]pos, i, lo, hi, qlo, qhi, val, odd int)\n\tupdate = func(segtree []bool, res []int, next *[]pos, i, lo, hi, qlo, qhi, val, odd int) {\n\t\tif qhi < lo || qlo > hi {\n\t\t\t// Skip\n\t\t\treturn\n\t\t}\n\n\t\tif lo >= qlo && hi <= qhi {\n\t\t\t// This range of the segment tree should be marked as "done"\n\t\t\tif segtree[i] {\n\t\t\t\t// If it is already done, return\n\t\t\t\treturn\n\t\t\t}\n\n\t\t\t// Mark all nodes as done, adding unseen nodes to next iteration\n\t\t\tfor j := lo; j <= hi; j++ {\n\t\t\t\tif res[j] != -2 {\n\t\t\t\t\tcontinue\n\t\t\t\t}\n\t\t\t\tres[j] = val\n\n\t\t\t\tmark(segtree, res, j, val)\n\t\t\t\t*next = append(*next, pos{j, odd})\n\t\t\t}\n\t\t\treturn\n\t\t}\n\n\t\t// Split query into left/right\n\t\tmid := lo + (hi-lo)/2\n\t\tupdate(segtree, res, next, i*2, lo, mid, qlo, qhi, val, odd)\n\t\tupdate(segtree, res, next, i*2+1, mid+1, hi, qlo, qhi, val, odd)\n\t}\n\n\tcurr := []pos{}\n\tnext := []pos{}\n\n\t// Start by marking p as done\n\t// This will populate next with the first node.\n\tupdate(segtree[p&1], res[p&1], &curr, 1, 0, m-1, p/2, p/2, 0, p&1)\n\n\tfor steps := 1; len(curr) > 0; steps++ {\n\t\tnext = next[:0]\n\t\tfor _, x := range curr {\n\t\t\tii := x.i*2 + x.odd\n\t\t\tl, r := reachableRange(n, ii, k)\n\t\t\tupdate(segtree[l&1], res[l&1], &next, 1, 0, m-1, l/2, r/2, steps, l&1)\n\t\t}\n\t\tcurr, next = next, curr\n\t}\n\n\tret := make([]int, n)\n\tfor i := 0; i < n; i++ {\n\t\tret[i] = res[i&1][i/2]\n\t}\n\tfor i := range ret {\n\t\tif ret[i] == -2 {\n\t\t\tret[i] = -1\n\t\t}\n\t}\n\treturn ret\n}\n\nfunc reachableRange(n, i, k int) (int, int) {\n\tleftMost := i - k + 1\n\trightMost := i + k - 1\n\tif leftMost < 0 {\n\t\td := -leftMost\n\t\tleftMost += d * 2\n\t}\n\tif rightMost >= n {\n\t\td := rightMost - n + 1\n\t\trightMost -= d * 2\n\t}\n\treturn leftMost, rightMost\n}\n\nfunc min(a, b int) int {\n\tif a < b {\n\t\treturn a\n\t}\n\treturn b\n}\n\nfunc max(a, b int) int {\n\tif a > b {\n\t\treturn a\n\t}\n\treturn b\n}\n\n```
['Go']