BFS + DSU for compress jump. Beats 100% runtime.
Intuition\nPrerequisite: https://cp-algorithms.com/data_structures/disjoint_set_union.html#compress-jumps-along-a-segment-painting-subarrays-offline\n\n# Approa
# Intuition\nPrerequisite: https://cp-algorithms.com/data_structures/disjoint_set_union.html#compress-jumps-along-a-segment-painting-subarrays-offline\n\n# Approach\nThis problem could be solved by simple BFS. Let the current index of the $1\'s$ be $u$, then we will find the two indices $l$ and $r$ such that the $1\'s$ at the index $u$ could go to after using the $k$ reverse operation. Then we will update the answer at the positions $l, l + 2, l + 4, ..., r$ be $res_u + 1$. However, the time complexity of this approach would be $O(n^2)$. \n\nLet\'s optimize the way we traverse from $l$ to $r$. There could be possibly at some moments we could visit some indices more than once. To avoid this, we can use DSU for compress jump. Specifically, denote $nxt_u$ be the next position from position $u$ such that we haven\'t traversed before. Then each time we traverse from $l$ to $r$, when we are at the position $u$, we can jump to position $nxt_u$ immediately to ensure that we visit each index at most once. \n\n# Complexity\n- Time complexity: $O(n \\alpha (n))$\n\n- Space complexity: $O(n)$\n\n# Code\n```cpp []\nconst int mxN = 1e5 + 5;\nint nxt[mxN];\n\nint Find(int u){\n    if(u == nxt[u])\n        return u;\n    return nxt[u] = Find(nxt[u]);\n}\n\nclass Solution {\npublic:\n    vector<int> minReverseOperations(int n, int p, vector<int>& banned, int k) {\n        for(int i = 0; i < n + 5; ++i)\n            nxt[i] = i;\n\n        for(int i: banned)\n            nxt[i] = i + 2;\n\n        vector<int> res(n, -1);\n        res[p] = 0;\n        queue<int> q;\n        q.push(p);\n        nxt[p] = p + 2;\n\n        while(q.size()){\n            int u = q.front(); q.pop();\n            int l = max(0, u - min(k - 1, (u - k / 2) * 2 + (k % 2 == 0)));\n            int r = min(n - 1, u + min(k - 1, (n - 1 - k / 2 - u) * 2 + (k % 2 == 0)));\n            for(int i = Find(l); i <= r; i = Find(i)){\n                res[i] = res[u] + 1;\n                q.push(i);\n                nxt[i] = i + 2; \n            }\n        }\n        return res;\n    }\n};\n```
['C++']