A classic problem, Ants on a Plank + Prefix sum O(n log n)
This is a variation of a very classic problem: There are some ants on a plank at some positions. They are moving right or left, and change directions when they 
This is a variation of a very classic [problem](https://leetcode.com/problems/last-moment-before-all-ants-fall-out-of-a-plank/#:~:text=When%20an%20ant%20reaches%20one,fall%20out%20of%20the%20plank.): There are some ants on a plank at some positions. They are moving right or left, and change directions when they bump into each other. When does the last ant fall off the plank?\nAt first glance, this may seem difficult to compute, as many collisions may be happening and it is hard to keep track of them all. But there is a very important key observation here: When two ants bump into each other, we can just act like they "phased" through each other! When one ant is going left, and another is going right, and they bump into each other, the left ant is now going right and the right ant is going left. There would be no difference if we had just swapped the ants, or let them pass through each other.\n\nWe can now apply this idea to the robots. Let us ignore any collisions, and just imagine all robots simply passed through each other, as if they were ghosts. Then now we can simply just subtract the distance from them if they were going left or add the distance to them if they were going right. Now, we simply need to compute the distance between each pair of robots. Note that (i, j) and (j,i) should not both be counted, so we will *only* use a prefix sum. If (j,i) was meant to be counted, we would use a prefix and postfix sum. We can compute this easily by sorting the array, then multiplying the number times the index, minus the prefix sum. This gives us the distance between all pairs of robots without double counting. \n\n```\nclass Solution {\npublic:\n    int MOD = 1000000007;\n    int sumDistance(vector<int>& nums, string s, int d) {\n        for(int i = 0; i < nums.size(); i++){\n            if(s[i] == \'R\') nums[i] += d;\n            else nums[i] -= d;\n        }\n        long long ans = 0;\n        long long pref = 0;\n        sort(nums.begin(), nums.end());\n        long long n = s.length()-1;\n        for(long long i = 0; i < nums.size(); i++){\n            ans += i * (long long) nums[i] - pref;\n            ans %= MOD;\n            pref += nums[i];\n        }\n        return ans;\n    }\n};
[]