fix house1-> generate intervals -> sweep line.  o(n) || short code
Intuition\n Describe your first thoughts on how to solve this problem. \n1. fix the house1, for every possible house2 > house1, find min distance, double result
# Intuition\n<!-- Describe your first thoughts on how to solve this problem. -->\n1. fix the `house1`, for every possible `house2 > house1`, find min distance, double result. (easy version of this problem)\n2. observe: if there is no `x and y`, then for a given `house1`, min distance is `list=[1,2,3,4,5,..., n-house1]` for all `house2` that `house2 > house1`.\n### now for a given house1\n3. with `x and y`: `x and y` only take effect when we can take a shortcut from `house1` to `y`, that is` y-house1 > 1 + abs(house1-x)`. Because we are finding the min distance.\n![Untitled-2023-09-25-1658.png](https://assets.leetcode.com/users/images/72cffa0d-6256-408a-bde2-f1c140e18e7b_1705810316.4744036.png)\n\n4. so, when there is a shortcut from `house1`, distance of all houses rightside of `y` should make use of this shortcut, distance of these hosues should be `1 + abs(house1 - x) + (house2 - y)`.\n5. as for houses between `hosue1` and `y`, we check from `y` to `house1`, we have two distance: \n- (chosen at `y`) shorter distance of `y` is `1 + abs(house1 - x)`, increases as we move from `y` to `house1` if we take shortcut, and \n- (chosen later) the longer distance (`y-house1`) decreases as we move. \n8. So for each step we move from `y` to `hosue1`, the difference between the two distance decreases by 2. when below zero, the optimal choice changes to the other one.\n9. That is to say: the distance of hosues from `y` to `house1` consists of two lists `left_half=[1,2,...,y-step] and right_half=[shortcut, shortcut+1, shortcut+2, ..., shortcut+step]`\n# Approach\n<!-- Describe your approach to solving the problem. -->\nTo get the final result, we need to count frequence of elements in these distance lists.\nOne approach is lazy propagation segment tree, which allows range modification. This is too complex for this problem.\nWe may think of sweep line for interval ops. The lists can be transfrom into intervals (continuous), then we can apply sweep line to get the value for each index.\n# Complexity\n- Time complexity:\n<!-- Add your time complexity here, e.g. $$O(n)$$ -->\no(n)\n- Space complexity:\n<!-- Add your space complexity here, e.g. $$O(n)$$ -->\n\n# Code\n```\nfunc abs(x int) int {\n\tif x < 0 {\n\t\treturn -x\n\t}\n\treturn x\n}\n\ntype it struct {\n\tl, r int\n}\n\nfunc countOfPairs(n int, x int, y int) []int64 {\n\tif x > y {\n\t\tx, y = y, x\n\t}\n    // generate intervals\n\tret := []int64{}\n\tintervals := []it{}\n\tfor i := 1; i < n; i++ {\n\t\tshort := 1 + abs(i-x)\n\t\tif y-i > short { // shortcut\n\t\t\tif y<n{ // y to n\n\t\t\t\tintervals = append(intervals, it{short+1, short + n - y})\n\t\t\t}\t\n            t := y - i - short\n\t\t\tstep := t / 2\n\t\t\tif t&1 == 1 {\n\t\t\t\tstep++\n\t\t\t}\n\t\t\tintervals = append(intervals, it{short, short + step - 1}) // right half of house1 to y\n\t\t\tintervals = append(intervals, it{1, y - step - i}) // left half of house1 to y\n\t\t} else { // x y is not a shortcut\n\t\t\tintervals = append(intervals, it{1, n - i})\n\t\t}\n\t}\n    // sweep line\n\tarr := make([]int64, n+1)\n\tfor _, i := range intervals {\n\t\tarr[i.l]++\n\t\tarr[i.r+1]--\n\t}\n\tcur := int64(0)\n\tfor k := 1; k <= n; k++ {\n\t\tcur += arr[k]\n\t\tret = append(ret, 2*cur)\n\t}\n\n\treturn ret\n}\n```
['Go']