O(NlogN) Segment Tree solution & O(N) math solution
Intuition\n Describe your first thoughts on how to solve this problem. \nline and an edge = a circle with 2 "ears"\n\nlet C denote the circle\nL1, L2 denote the
# Intuition\n<!-- Describe your first thoughts on how to solve this problem. -->\nline and an edge = a circle with 2 "ears"\n\nlet C denote the circle\nL1, L2 denote the lines\nalso the size of each part\n\n# Approach\n<!-- Describe your approach to solving the problem. -->\nuse segment tree to do range addition and query\n\n# Complexity\n- Time complexity:\n<!-- Add your time complexity here, e.g. $$O(n)$$ -->\nO(Nlg(N))\n\n- Space complexity:\n<!-- Add your space complexity here, e.g. $$O(n)$$ -->\nO(N)\n\n# Code\n```\nclass Solution:\n    def countOfPairs(self, N: int, x: int, y: int) -> List[int]:\n        \n        def add(i, s, t, qs, qt, d):\n            if s == qs and t == qt:\n                f[i] += d\n                return\n            m = (s + t) // 2\n            if qt <= m:\n                return add(i * 2 + 1, s, m, qs, qt, d)\n            if qs > m:\n                return add(i * 2 + 2, m + 1, t, qs, qt, d)\n            add(i * 2 + 1, s, m, qs, m, d)\n            add(i * 2 + 2, m + 1, t, m + 1, qt, d) \n\n        def qry(i, s, t, q):\n            if s == t:\n                return f[i]\n            m = (s + t) // 2\n            if q <= m:\n                return f[i] + qry(i * 2 + 1, s, m, q)\n            return f[i] + qry(i * 2 + 2, m + 1, t, q)\n\n        def line(n):\n            for i in range(0, n - 1):\n                add(0, 1, N, 1, n - 1 - i, 2)\n\n        def circle(n):\n            if n % 2 == 1:\n                return add(0, 1, N, 1, n // 2, n * 2)\n            add(0, 1, N, 1, n // 2, n)\n            add(0, 1, N, 1, n // 2 - 1, n)\n        \n        def node_to_circle(d, n, q):\n            if n % 2 == 1:\n                add(0, 1, N, d, d + n // 2, q)\n                add(0, 1, N, d + 1, d + n // 2, q)\n            else:\n                add(0, 1, N, d, d + n // 2 - 1, q)\n                add(0, 1, N, d + 1, d + n // 2, q)\n\n        def node_to_line(d, n, q):\n            add(0, 1, N, d, d + n - 1, q)    \n\n        def res():\n            return [qry(0, 1, N, i) for i in range(1, N + 1)]\n\n\n        f = [0] * (N * 4)\n\n        if x > y:\n            x, y = y, x\n        C = y - x + 1\n        if C <= 2:\n            line(N)\n            return res()\n\n        L1 = x - 1\n        L2 = N - y\n        \n        if L1 >= 1:\n            line(L1)\n            for i in range(L1):\n                node_to_circle(i + 1, C, 2)\n                if L2 >= 1:\n                    node_to_line(i + 3, L2, 2)\n\n        if L2 >= 1:\n            line(L2)\n            for i in range(L2):\n                node_to_circle(i + 1, C, 2)\n\n\n        circle(C)\n\n        return res()\n```\n\nI think this segment-tree solution is really straight forward, less error-prone, while add some math trick we will reach a solution of time complexity O(N)\n\n```\nclass Solution:\n    def countOfPairs(self, N: int, x: int, y: int) -> List[int]:\n        \n        def add(s, t, d):\n            for i in range(s, t + 1):\n                f[i] += d\n\n        def add_arr(s, a, q):\n            for i in range(len(a)):\n                f[s + i] += a[i] * q\n\n        def line(n):\n            for i in range(1, n):\n                f[i] += 2 * (n - i)\n\n        def circle(n):\n            if n % 2 == 1:\n                add(1, n // 2, n * 2)\n            else:\n                add(1, n // 2, n)\n                add(1, n // 2 - 1, n)\n        \n        def make_tz(l, rep):\n            max_value = min(rep, l)\n            a = list(range(1, max_value))\n            return a + [max_value] * (l + rep - 1 - 2 * len(a)) + a[::-1]\n\n        def line_to_circle(l, c):\n            tz = make_tz(l, c // 2 + 1)\n            add_arr(1, tz, 2)\n            tz = make_tz(l, (c - 1) // 2)            \n            add_arr(2, tz, 2)\n\n        def line_to_line(l1, l2):\n            tz = make_tz(l2, l1)\n            add_arr(3, tz, 2)\n\n        f = [0] * (N + 1)\n\n        if x > y:\n            x, y = y, x\n        C = y - x + 1\n        if C <= 2:\n            line(N)\n            return f[1:]\n\n        L1 = x - 1\n        L2 = N - y\n        \n        if L1:\n            line(L1)\n            line_to_circle(L1, C)\n        \n        if L2:\n            line(L2)\n            line_to_circle(L2, C)\n        \n        if L1 and L2:\n            line_to_line(L1, L2)\n\n        circle(C)\n\n        return f[1:]\n```\n
['Python3']