O(NlogN), throw a random data structure and pass the question
Clearly it is BFS, and it is easily to determine in a range which indexes are valid from this index (but be careful about parity). However, it isn\'t clear abou
Clearly it is BFS, and it is easily to determine in a range which indexes are valid from this index (but be careful about parity). However, it isn\'t clear about how to find the edges in BFS efficiently.\n\nSo I just throwed a segment tree on the question and passed. Actually we could just use a set but I was too lazy to think at that time.\n\n```cpp\nconstexpr int MAXN = 1e5 + 5;\nconstexpr int INF = 0x3f3f3f3f;\n\nint M;\npair<int,int> segodd[MAXN << 2];\npair<int,int> segeven[MAXN << 2];\n\ninline void maintain(int x) {\n    segodd[x] = min(segodd[x << 1], segodd[x << 1 | 1]);\n    segeven[x] = min(segeven[x << 1], segeven[x << 1 | 1]);\n}\n\ninline void build(int N) {\n    for (M = 1; M <= N + 1; M <<= 1);\n    for (int i = M + 1; i <= 2 * M; i ++) {\n        segodd[i] = segeven[i] = {0, i - M};\n    }\n    for (int i = M - 1; i >= 1; i --) {\n        maintain(i);\n    }\n}\n\ninline void updodd(int x) {\n    for (segodd[x += M].first = 1, x >>= 1; x; x >>= 1) {\n        maintain(x);\n    }\n}\n\ninline void updeven(int x) {\n    for (segeven[x += M].first = 1, x >>= 1; x; x >>= 1) {\n        maintain(x);\n    }\n}\n\ninline pair<int,int> queryodd(int l, int r, int N) {\n    if (l > r) {\n        return {1, 0x3f3f3f3f};\n    }\n    if (l < 1) {\n        l = 1;\n    }\n    if (r > N) {\n        r = N;\n    }\n    pair<int,int> ans = {1, 0x3f3f3f3f};\n    for (l += M - 1, r += M + 1; l ^ r ^ 1; l >>= 1,r >>= 1) {\n        if (~l & 1) {\n            ans = min(ans, segodd[l ^ 1]);\n        }\n        if (r & 1) {\n            ans = min(ans, segodd[r ^ 1]);\n        }\n    }\n    return ans;\n}\n\ninline pair<int,int> queryeven(int l, int r, int N) {\n    if (l > r) {\n        return {1, 0x3f3f3f3f};\n    }\n    if (l < 1) {\n        l = 1;\n    }\n    if (r > N) {\n        r = N;\n    }\n    pair<int,int> ans = {1, 0x3f3f3f3f};\n    for (l += M - 1, r += M + 1; l ^ r ^ 1; l >>= 1,r >>= 1) {\n        if (~l & 1) {\n            ans = min(ans, segeven[l ^ 1]);\n        }\n        if (r & 1) {\n            ans = min(ans, segeven[r ^ 1]);\n        }\n    }\n    return ans;\n}\n\nclass Solution {\npublic:\n    vector<int> minReverseOperations(int n, int p, vector<int>& banned, int k) {\n        p ++;\n        build(n);\n        if (p & 1) {\n            updodd(p);\n        } else {\n            updeven(p);\n        }\n        \n        \n        vector<int> ans(n + 1, -1);\n        for (auto x: banned) {\n            ans[x + 1] = -1;\n            if ((x + 1) & 1) {\n                updodd(x + 1);\n            } else {\n                updeven(x + 1);\n            }\n        }\n        for (int i = 1; i <= n; i ++) {\n            if (i & 1) {\n                updeven(i);\n            } else {\n                updodd(i);\n            }\n        }\n        ans[p] = 0;\n        \n        queue<int> q;\n        q.push(p);\n        \n        while (!q.empty()) {\n            int on =q.front();\n            int i = on;\n            \n            q.pop();\n            \n            int to = n - (k - (n - i + 1) + 1) + 1;\n            int from = k - i + 1;\n            to = min(to, i + k - 1);\n            from = max(from, i - k + 1);\n            \n            if (k & 1) {\n                if (i % 2 == 1) {\n                    auto [a, b] = queryodd(from, to, n);\n                    while (a == 0) {\n                        q.push(b);\n                        ans[b] = ans[on] + 1;\n                        updodd(b);\n                        auto [x, y] = queryodd(from, to, n);\n                        a = x;\n                        b = y;\n                    }\n                } else {\n                    auto [a, b] = queryeven(from, to, n);\n                    while (a == 0) {\n                        q.push(b);\n                        ans[b] = ans[on] + 1;\n                        updeven(b);\n                        auto [x, y] = queryeven(from, to, n);\n                        a = x;\n                        b = y;\n                    }\n                }\n            } else {\n                if (i % 2 == 1) {\n                    auto [a, b] = queryeven(from, to, n);\n                    while (a == 0) {\n                        q.push(b);\n                        ans[b] = ans[on] + 1;\n                        updeven(b);\n                        auto [x, y] = queryeven(from, to, n);\n                        a = x;\n                        b = y;\n                    }\n                } else {\n                    auto [a, b] = queryodd(from, to, n);\n                    while (a == 0) {\n                        q.push(b);\n                        ans[b] = ans[on] + 1;\n                        updodd(b);\n                        auto [x, y] = queryodd(from, to, n);\n                        a = x;\n                        b = y;\n                    }\n                }\n            }\n        }\n        ans.erase(ans.begin());\n        return ans;\n    }\n};\n```
['C++']