76ms[100%]
Intuition\n Describe your first thoughts on how to solve this problem. \nReturn a 1-indexed array result of length n where result[k] represents the total number
# Intuition\n<!-- Describe your first thoughts on how to solve this problem. -->\nReturn a 1-indexed array result of length n where result[k] represents the total number of pairs of houses such that the minimum streets required to reach one house from the other is k\n\nThis basicly return the an distant array \ndistant[i] is number of node pair has distant == i + 1 \n\nExample 2:\n![example3.png](https://assets.leetcode.com/users/images/4fca166e-cd71-4325-a5b9-0fee845885ba_1705813831.9143014.png)\n\nPart1:\n1 -> 2 -> 4 -> 5 form a line\n\nPart2:\n2 -> 3 -> 4 form a circle\n\nPart3:\n1 form the left line to the circle\n\nPart4:\n5 form the right line to the circle\n\n\n\n# Approach\n<!-- Describe your approach to solving the problem. -->\n\nStep 1\nCaculate distant array for Part1  inside line.\nNeed to exlcude the cross section node pair connect x and y,\nNeed to exlcude {2, 4} , {4, 2}, {2, 5}, {5, 2}, {1, 4} , {4, 1}\n\nStep 2\nCaculate distant array for Part2  inside circle.\nnumber of nodes in circle is l.\nCaculate the distant answer for each node and then multiple l and add to final answer.\nCaculate a prefix sum array for distant array to step 3.  \n\nStep 3 \nCaculate distant array any pair between Part3 and Part2.\n{1, 3}, {1, 4} , {3, 1}, {4, 1}\n1 Note: need to exclude {1, 2}\n2 use the prefix sum  array in step 2 for slide-window style aggregation.\n\nStep 3 \nCaculate distant array any pair between Part4 and Part2.\n{5, 3}, {5, 2} , {3, 5}, {2, 5}\nNote: need to exclude {5, 4}\n\n\n\n# Complexity\n- Time complexity:\n- O(N)\n<!-- Add your time complexity here, e.g. $$O(n)$$ -->\n\n- Space complexity:\n- O(N)\n<!-- Add your space complexity here, e.g. $$O(n)$$ -->\n\n# Code\n```\ntypedef long long ll;\nclass Solution {\npublic:\n    int n;\n    vector<ll> ans;\n    ll rangesum(vector<ll>& prefix, int l, int r) {\n        ll pre = 0;\n        if (l - 1 >= 0) pre = prefix[l -1];\n        return prefix[r] - pre;\n    }\n    void dump(const string& str, vector<ll>& dp) {\n        cout << str << endl;\n        for (auto v : dp) cout << v << ",";\n        cout << endl; \n    }\n    // \n    // 1 everything on a line\n    // 2 everything on a circle\n    // 3 cicirle * line\n\n    vector<long long> countOfPairs(int n1, int x, int y) {\n        n = n1;\n        ans = vector<ll>(n, 0);\n        bool noc = false;\n        if (x > y) swap(x, y);\n        int cl = 0;\n        int linel = 0;\n        {\n            // line\n            int l;\n            int a;\n            int b;\n            if (x != y && y - x > 1) {\n                a = x;\n                b = n - y + 1;\n                l = a + b;\n                int linel = l;\n            } else {\n                noc = true;\n                l = n;\n                linel = n;\n            }\n            \n            for (int d = 1; d <= l; d++) ans[d - 1] = (l - d) * 2;\n            //dump("line", ans);\n            // dup\n            if (!noc) {\n                for (int i = 1; i < x; i++) {\n                    //ans[x - i - 1]--;\n                    ans[x - i] -= 2;\n                }\n                ans[0] -= 2;\n                for (int i = y + 1; i <= n; i++) {\n                    ans[i - y] -= 2;\n                    //ans[i - y - 1]--;\n                }\n            }\n            //dump("line", ans);\n        }\n        if (noc) {\n            return ans;\n        }\n        //cout << 1 << endl;\n        // circle\n        vector<ll> dp = vector<ll>(n, 0);\n        vector<ll> prefix = vector<ll>(n, 0);\n        if ( x != y && y - x > 1) {\n            int l = y - x + 1;\n            cl = l;\n            int h = (l - 1)/2;\n            for (int i = 0; i < h; i++) {\n                dp[i] = l * 2;\n                ans[i] += dp[i];\n            }\n            if (((l - 1) % 2) == 1) {\n                dp[h] += l;\n                ans[h] += l;\n            }\n            // cout << l << endl;\n            //dump("circle", dp);\n            //dump("circle", ans);\n            for (int i = 0; i <= h; i++) {\n                dp[i] = dp[i] / l;\n            }\n            \n            ll sum = 0;\n            for (int i = 0; i < n; i++) {\n                prefix[i] = dp[i] + sum;\n                sum = prefix[i];\n            } \n            //dump("circle", prefix);\n        }\n        //cout << 2 << endl;\n        // line to circle left\n        if (x > 1) {\n            int len = x - 1;\n            for (int i = n - 1; i >= 0; i--) {\n                    int l = i - len;\n                    int r = i - 1;\n                    if (r < 0) break;\n                    ans[i] += rangesum(prefix, l, r) * 2;\n            }\n            //dump("line_circle_left", ans);\n        }\n        // line to circle right\n        if (y < n ) {\n            int len = n - y;\n            // range(1, l)\n            for (int i = n - 1; i >= 0; i--) {\n                    int l = i - len;\n                    int r = i - 1;\n                    if (r < 0) break;\n                    ans[i] += rangesum(prefix, l, r) * 2;\n            }\n            //dump("line_circle_right", ans);\n        }\n        return ans;\n    }\n};\n```
['C++']