BFS with C++ Set and lower_bound/upper_bound
Intuition\n Describe your first thoughts on how to solve this problem. \nThe problem seems to be a BFS or SSSP(single source shortest path) problem. But given t
# Intuition\n<!-- Describe your first thoughts on how to solve this problem. -->\nThe problem seems to be a BFS or SSSP(single source shortest path) problem. But given the input size, the general approach won\'t work . We need to find and use the specificity of the problem\n\n# Approach\n<!-- Describe your approach to solving the problem. -->\n## Rephrase the problem\nStart from the BFS or SSSP problem, the starting point is P and every legal operation that covers a vertice is an outgoing "edge" of a vertice. But given the number of nodes (10 ** 5) and number of edges (n * k, 10 ** 10 in the worst case), naive BFS or SSSP won\'t work.\n\n## Reduce the number of edges\nImagine how the naive method will be implemented. In a BFS, for current vertice, we try to find the vertices that are reachable by this vertice. To reduce the redundancy, if a vertice is banned or visited before, we should skip that vertice.\n\nWe can maintain an unvisited nodes list and only traverse nodes in the list. Consider the specificity of the problem -- the nodes are array indices and the "edges" are in a contiguous range. We need a data structure that could add, remove elements and get elements in a given range. So:\n\n- When start, all the vertices are in the list\n- In BFS, we calculate the reachable range, query the list to get unvisited nodes in the range\n- Once a vertice is visited, remove it from the list\n\nSo we could skip visited vertices. It\'s doable with C++ set or Java TreeSet. A BST will work as well.\n\n## Parity \nFor k = 3, 5, 7... the \'1\' could only move even steps, that is to say only half of the array which has the same parity of P is reachable. \n\nFor k = 2, 4, 6.... the \'1\' could move odd steps, by moving +1 -3, it creates +2. So all the array is reachable.\n\nI tried to use parity to solve the problem but that doesn\'t work. However, this discovers a corner case. If k is odd, half of the array is not reachable and will never be removed from the list. We need either not to add them into the list, or split the list by parity.\n\n# Complexity\n- Time complexity: O(nlogn), Use amortized analysis.\n<!-- Add your time complexity here, e.g. $$O(n)$$ -->\n\n\n- Space complexity: O(n)\n<!-- Add your space complexity here, e.g. $$O(n)$$ -->\n\n# Code\n```\nclass Solution {\npublic:\n    vector<int> minReverseOperations(int n, int p, vector<int>& banned, int k) {\n        const int inf = 1E9;\n        vector<int> dist(n, inf);\n        queue<int> q;\n        dist[p] = 0;\n        q.push(p);\n        \n        set<int> allowed[2];\n        for (int i = 0; i < n; i++) {\n            allowed[i % 2].insert(i);\n        }\n        allowed[p % 2].erase(p);\n        for (int e : banned) {\n            allowed[e % 2].erase(e);\n        }\n        \n        while (q.size()) {\n            int now = q.front();\n            q.pop();\n\n            int op_left = max(0, now - k + 1);\n            int op_right = min(now, n - k);\n\n            if (op_left > op_right) {\n                continue;\n            }\n\n            int l = op_left + (k - 1) - (now - op_left);\n            int r = op_right + (k - 1) - (now - op_right);\n            \n            //                    k % 2 == 0   k % 2 == 1\n            //   now % 2 == 0              1            0\n            //   now % 2 == 1              0            1\n            auto &allowed_ref = allowed[1 ^ (k % 2) ^ (now % 2)];\n\n            auto lower = allowed_ref.lower_bound(l);\n            auto upper = allowed_ref.upper_bound(r);\n            vector<int> to_erase;\n            for (auto it = lower; it != upper; it++) {\n                int next = *it;                \n                if (dist[next] > dist[now] + 1) {\n                    dist[next] = dist[now] + 1;\n                    q.push(next);\n                    to_erase.push_back(next);\n                }\n            }\n            for (auto e: to_erase) {\n                allowed[e % 2].erase(e);\n            }\n        }\n        for (auto &e : dist) {\n            if (e == inf) {\n                e = -1;\n            }\n        }\n        return dist;\n    }\n};\n```
['Breadth-First Search', 'Binary Search Tree', 'C++']