C++ with thinking process
Intuition\nThe first time I saw this question, I have no idea about that LOL. I check the input range, there is a $d \sim 1e9$, and $nums \sim 1e5$, and this is
## Intuition\nThe first time I saw this question, I have no idea about that LOL. I check the input range, there is a $d \\sim 1e9$, and $nums \\sim 1e5$, and this is not a simulation, search, dynamic programming, etc. I guess it must have some method to avoid simulating $d$ seconds and get the final state, the situation is too complicated with collision.\n\nAnd, surprisingly, there is.\nLet\'s think about what happened when two robots collide. Here is the simplified version of collision situaltion.\n* (x - 1 $\\rightarrow$,$\\leftarrow$ x + 1) $\\Rightarrow$ ($\\leftarrow$ x, x$\\rightarrow$) $\\Rightarrow$ ($\\leftarrow$ x - 1, x + 1$\\rightarrow$)\n* (x$\\rightarrow$,$\\leftarrow$ x + 1) $\\Rightarrow$ ($\\leftarrow$ x, x + 1$\\rightarrow$)\n\nCan we know something from it? Obviously, I can\'t see anything, they just switch the direction as the question said.\n\nWhat about we **not only** change their direction, but also **change their identity**? Let\'s see what\'s happening now.\n\n* (x - 1 $\\rightarrow$,$\\leftarrow$ y + 1) $\\Rightarrow$ ($\\leftarrow$ y, x$\\rightarrow$) $\\Rightarrow$ ($\\leftarrow$ y - 1, x + 1$\\rightarrow$)\n* (x$\\rightarrow$,$\\leftarrow$ y + 1) $\\Rightarrow$ ($\\leftarrow$ y, x + 1$\\rightarrow$)\n\nThey just "pass through" each other, as if **no collision** happens!\n\nSo the final problem is, how to get the final answer without nested for loop? Yes!\n\nLet\'s see this picture, assuming we have 4 robots (dots).\n\n![picture](https://assets.leetcode.com/users/images/412967dc-17ae-434d-9299-6206fcddb703_1686418475.0609558.png)\n\nThink about it, if we use nested for loop, we will repeated calculate the intermedia distance. We can remove those redundancy. \n\nWe can calculate the distance from robot[0] to robot[1-3] (the brackets below, i.e. $y_0+y_1+y_2$). If we want to calculate the distance from robot[1] to others, we need to calcualte $x_0 + x_1 + x_2$ (the brackets above). \n\nHowever, we can see that all brackets below "contain" the brackets above (one-to-one). To be specific, $y_0$ contains $x_0$, $y_1$ contains $x_1$, $y_2$ contains $x_2$. Since we already calculate pair[0, 1], we don\'t need $x_0$ anymore, i.e. we don\'t need to care about the left robots, and we just care about the right part, $x_1+x_2$ in this example, and we can get that by $y_0 + y_1 + y_2 - 3 * x_0$.\n\nThis pattern follows, if we want to calculate the robot[2] distance with others, we have $y_0 + y_1 + y_2 - 3 * x_0 - 2 * x_1$, that\'s exactly the last pair we don\'t have.\n\nAnd that\'s the idea, we don\'t need iterate through every pair, we just iterate through every "gap" between two robots.\n\n## Approach\n\nFirst we can get the final state by iterating the `nums`, because every robot is just like they "step forward" without any collision.\n\nSecond, we sort the final state.\n\nFinally, we get the answer just like said above. Note: We first get the sum of distance `temp` between all other robots and the leftest robot $robot_0$, and this is within long long range.\n\nDone!\n\n\n## Complexity\n- Time complexity: $O(mlogm)$, m is the length of array `nums`.\n- Space complexity: Don\'t care :D\n\n## Code\n```\nclass Solution {\npublic:\n    const long long mod = 1e9+7;\n    int sumDistance(vector<int>& nums, string s, int d) {\n        vector<long long> finalState;\n        for(auto n : nums) {\n            finalState.emplace_back(n);\n        }\n        for(int i = 0; i < finalState.size(); i++) {\n            if (s[i] == \'L\')\n                finalState[i] -= d;\n            else finalState[i] += d;\n        }\n        sort(finalState.begin(), finalState.end());\n        unsigned long long temp = 0, ans = 0;\n        for(int i = 0; i < finalState.size(); i++) {\n            if (i == 0) {\n                for(int j = 1; j < finalState.size(); j++) {\n                    temp += abs(finalState[j] - finalState[i]);\n                    ans = temp % mod;\n                }\n            } else {\n                temp = temp - (nums.size() - i) * abs(finalState[i] - finalState[i - 1]);\n                ans = (ans + temp) % mod;\n            }\n        }\n        return ans;\n    }\n};\n```
['C++']