Graph flipping and interval merging | Optimised solution | Cases explained
Intuition\nWe can simplify the cases by considering the ranges [1:x] and [x+1:m] where m is the middle point in between x and y. We can then flip the graph and 
# Intuition\nWe can simplify the cases by considering the ranges `[1:x]` and `[x+1:m]` where m is the middle point in between `x` and `y`. We can then flip the graph and do the same from the other side. So in total we only need to consider 2 cases.\n\nWe can then calculate for each `i` in these ranges, the total increase in the distances. \n\nWhen i is outside the loop ($i < x$), we will have:\n1. 1 node on the left, outside the loop, starting with distance 1.\n2. $x-i$ nodes on the right, upto middle of the loop, starting with distance 1.\n3. $y-m$ nodes in the right side of the loop starting with distance $x-i+1$ (takign the shortcut).\n3. $n-y$ nodes in the right side of the loop starting with distance $x-i+1$ (taking the shortcut).\n\nWhen i is inside the loop on the left side ($x <= i <= m$), we will have:\n1. Half of the loop nodes ($(y-x)//2$), starting  with distance 1.\n2. Other, half of the loop nodes ($(y-x)//2$), starting  with distance 1.\n3. If the number of loop nodes is odd, we will have one more middle node at distance $(y-x+1)//2$\n4. The left nodes outside the loop will either be through the shortcut starting with distance $(y-i+2)$ or not throught the shortbut with distance $(i-x+1)$.\n5. Similarly, The right nodes outside the loop will either be through the shortcut starting with distance $(i-x+2)$ or not throught the shortbut with distance $(y-i+1)$.\n\n# Interval merging\nInstead of adding 1 for each item every time we have to increment a range of distances, we store the range of intervals to increment in a dictionary with their counts.\n\nAfter getting all the ranges, we use interval counting technique and calculate the total at each distance by removing the count of ended ranges and adding the count of started ranges.\n\n# Complexity\n- Time complexity: $n log(n)$\n\n- Space complexity: $n$\n\n# Code\n```python\nclass Solution:\n    def countOfPairs(self, n: int, x: int, y: int) -> List[int]:\n        if y < x:\n            x, y = y, x\n        m = (y+x)//2\n\n        # Optimization: (Single Chain) In case jumping 0 or 1 nodes, the new edge can be ignored.\n        if y-x <= 1:\n            return [(n-l)*2 for l in range(1, n+1)]\n        \n        interv = defaultdict(int)\n        \n        def add(start, count):\n            if count <= 0: return\n            interv[(start, start+count)] += 1\n        \n        def addRanges(i):\n            if i < x:\n                add(1, i-1)\n                add(1, m-i)\n                add(x-i+1, y-m)\n                add(x-i+2, n-y)\n            elif i <= m:\n                add(1, (y-x)//2)\n                add(1, (y-x)//2)\n                if (y-x)%2 != 0:\n                    mid = (y-x+1)//2\n                    add(mid, 1)\n                \n                add(min(i-x+1, y-i+2), x-1)\n                add(min(i-x+2, y-i+1), n-y)\n\n        \n        for i in range(1, m+1):\n            addRanges(i)\n        \n        x = n-x+1\n        y = n-y+1\n        if y < x:\n            x, y = y, x\n        m = math.ceil((y+x)/2)\n        for i in range(1, m):\n            addRanges(i)\n\n        result = []\n        ends = []\n        ranges = sorted(interv.keys(), reverse=True)\n        total = 0\n        for i in range(1, n+1):\n            while ranges and ranges[-1][0] <= i:\n                start, end = ranges.pop()\n                c = interv[(start, end)]\n                heappush(ends, (end, c))\n                total += c\n            while ends and ends[0][0] <= i:\n                total -= heappop(ends)[1]\n            result.append(total)\n\n        return result\n        \n```
['Python3']