No Binary search, just use sweep line and prefix sum
Intuition\nFor a given query x, answer will be sum of left answer and right answer.\nleft answer = x * number of smaller values than x - sum of smaller values t
# Intuition\nFor a given query `x`, answer will be sum of `left answer` and `right answer`.\n`left answer` = `x` * `number of smaller values than x` - `sum of smaller values than x`\n`right answer` = `sum of bigger values than x` - `x` * `number of bigger values than x`\n\n\n# Approach\nSort both array and queries.\nYou can find number of smaller(`ln`) and larger values(`rn`) using sweep line.\nAnd find sum of smaller(`ls`) and larger values(`rs`) using prefix sum + sweep line.\n\n# Complexity\n- Time complexity:\n<!-- Add your time complexity here, e.g. $$O(n)$$ -->\n`O(nlogn + mlogm + n + m)`\n\n- Space complexity:\n<!-- Add your space complexity here, e.g. $$O(n)$$ -->\n`O(n)` for prefix sum\n\n# Code\n```\nclass Solution {\npublic:\n\tvector<long long> minOperations(vector<int>& a, vector<int>& queries) {\n\t\tsort(a.begin(), a.end());\n\t\tvector dp(1, 0ll);\n\t\tfor(auto &x: a) dp.push_back(dp.back() + x);\n\n\t\tvector <pair <long long, int>> q;\n\t\tfor(int i = 0; i < queries.size(); i++) q.push_back({queries[i], i});\n\t\tsort(q.begin(), q.end());\n\n\t\tvector ans(q.size(), 0ll);\n\t\tlong long i = 0, n = a.size(), ln = 0, rn = n, ls = 0, rs = dp[n];\n\t\tfor(auto &[x, idx]: q) {\n\t\t\tfor( ; i < n && a[i] <= x; i++) {\n\t\t\t\tln = i + 1, rn = n - (i + 1);\n\t\t\t\tls = dp[i + 1], rs = dp[n] - dp[i + 1];\n\t\t\t}\n\t\t\tans[idx] = (x * ln - ls) + (rs - x * rn);\n\t\t}\n\t\treturn ans;\n\t}\n};\n```
['C++']