[C++] Binary Indexed Tree + Math, O(nlogn)
Intuition\nSeparate the houses into 3 parts by the additional street: left, mid and right.\nFor example, for n = 5, x = 2, y = 4,\nleft = x-1 = 1\nmid = y-x+1 =
# Intuition\nSeparate the houses into 3 parts by the additional street: left, mid and right.\nFor example, for n = 5, x = 2, y = 4,\nleft = x-1 = 1\nmid = y-x+1 = 4-2+1 = 3\nright = n-x = 5-4 = 1\n\nCalculate 9=3*3 types of pairs: [left, right, mid] * [left, right, mid]\nClassify them into 4 types:\n1. (mid, mid)\n2. (left, right), (right, left)\n3. (left, mid), (mid, left), (right, mid), (mid, right)\n4. (left, left), (right, right)\n\n# Approach\n1. (mid, mid)\nSuppose the circle\'s length is k.\nFor every house, the distance of other houses should be [1, 2, 3, ... k/2] and [2, 3, 4, ..., (k+1)/2].\nWe can use Binary Indexed Tree to maintain this.\nIf we need to add [1, 2, 3, ... maxDistance] by Num, we just add Num to position 1, and add -Num to position maxDistance+1 in the Binary Indexed Tree.\n\n2. (left, right), (right, left)\nIf the circle\'s length is larger than 1, Travelling from every house in the left part should use additional street to shorten the distance from houses in the right.\nFor example, the closest house has distance array: [3, 4, 5, ... right+2+0],\nthe next closest house has distance array: [4, 5, 6, ... right+2+1]\nand so on.\n\n3. (left, mid), (mid, left), (right, mid), (mid, right)\nSimilar to (mid, mid), Travelling from every house in the left part should first go to the circle, and then it should be like (mid, mid)\n\n4. (left, left), (right, right)\nWithout the additional street.\nSuppose the size is k.\nWe have k of 1, (k-1) of 2, (k-2) of 3, ..., 1 of (k-1)\n\nFinally, for distance x, we calculate the sum from 1 to x in the Binary Indexed Tree.\n\n# Complexity\n- Time complexity:\n$$O(nlogn)$$\n\n- Space complexity:\n$$O(n)$$\n\n# Code\n```\nclass Solution {\npublic:\n    int tot;\n    int c[100001];\n    int lowbit(int k) {\n        return k & (-k);\n    }\n    long long query(int k) {\n        long long ret = 0;\n        while (k > 0) {\n            ret += c[k];\n            k -= lowbit(k);\n        }\n        return ret;\n    }\n    void insert(int k, long long d){\n        while (k <= tot) {\n            c[k] += d;\n            k += lowbit(k);\n        }\n        return;\n    }\n    void update(int l, int r, long long d) {\n        if (l == 0 || r == 0 || l > r)\n            return;\n        insert(l, d);\n        insert(r + 1, -d);\n    }\n    vector<long long> countOfPairs(int n, int x, int y) {\n        tot = n;\n        if (x > y) {\n            int temp = x; x = y; y = temp;\n        }\n        int left = x - 1;\n        int right = n - y;\n        int mid = y - x + 1;\n        //1. mid\n        int r1 = mid / 2;\n        int r2 = (mid - 1) / 2;\n        update(1, r1, mid);\n        update(1, r2, mid);\n\n        //2. left to right, right to left\n        int minDist = 2;\n        if (x == y) minDist = 1;\n        for (int i = 1; i <= left; i++) {\n            update(i + minDist, i + minDist-1 + right, 1);\n        }\n        for (int i = 1; i <= right; i++) {\n            update(i + minDist, i + minDist-1 + left, 1);\n        }\n\n        //3. left to mid, right to mid\n        r1 = (mid+1) / 2;\n        r2 = mid / 2;\n        for (int i = 1; i <= left; i++) {\n            update(i, i + r1 - 1, 2);\n            update(i + 1, i + r2, 2);\n        }\n        for (int i = 1; i <= right; i++) {\n            update(i, i + r1 - 1, 2);\n            update(i + 1, i + r2, 2);\n        }\n\n        //4. left to left, right to right\n        for (int i = 2; i <= left; i++) {\n            update(i - 1, i - 1, 2*(left + 1 - i));\n        }\n        for (int i = 2; i <= right; i++) {\n            update(i - 1, i - 1, 2*(right + 1 - i));\n        }\n\n        vector<long long> ans;\n        for (int i = 1; i <= n; i++) {\n            ans.push_back(query(i));\n        }\n\n        return ans;\n    }\n};\n```
['Math', 'Binary Indexed Tree', 'C++']