[Python] Modify a Grid
Let $(x_0, y_0)$ be the added edge in question and relabel the houses as $[0, 1, \dots, N-1]$.\n\nConsider points $x \leq y$ on a grid $A_{x, y} = \min(d_1(x, y
Let $(x_0, y_0)$ be the added edge in question and relabel the houses as $[0, 1, \\dots, N-1]$.\n\nConsider points $x \\leq y$ on a grid $A_{x, y} = \\min(d_1(x, y), d_2(x, y))$ where $d_1(x, y) = y - x$ and $d_2(x,y) = \\left| x-x_0 \\right| + \\left|y-y_0\\right| + 1$.  We want to tabulate these values.\n\nUsing a standard difference array trick, adding $[L, L+1, \\dots, R]$ to our tabulation can be done with `A[L] += 1; A[R+1] -= 1` and taking partial sums after.\n\nConsider the `y`-th row.  It naturally has values from `x=y..0` of `0, 1, ..., y`.  If $d_1(x_0, y) > d_2(x_0, y)$, then these values change.  Let $\\delta = d_2(x_0, y)$ and $x_{\\text{left}}$ be the largest value of $x$ for which $d_1(x, y) < d_2(x, y)$.\n- for $x \\in [0, x_0]$, we add values $[\\delta, \\cdots, \\delta + x_0]$\n- for $x \\in (x_0, x_{\\text{left}}]$, we add values $[\\delta + 1, \\cdots, \\delta + x_{\\text{left}} - x_0 - 1]$\n- for $x \\in (x_{\\text{left}}, y)$, we add values $[1, \\cdots, y - x_{\\text{left}}]$.\n\n# Code\n```python3 []\nclass Solution:\n    def countOfPairs(self, N: int, X: int, Y: int) -> List[int]:\n        x0, y0 = sorted([X-1, Y-1])\n        A = [0] * N\n\n        def add(x, y):\n            if x <= y:\n                A[x-1] += 2\n                A[y] -= 2\n\n        for y in range(N):\n            d1 = y - x0\n            d2 = abs(y - y0) + 1\n            if d1 <= d2:\n                add(1, y)\n                continue\n            add(d2, d2 + x0)  # x in [0, x0]\n            x_left = bisect_left(range(N), True, x0, y+1, key=lambda x: y-x < abs(y-y0) + abs(x-x0) + 1)\n            add(d2 + 1, d2 + x_left - x0 - 1)  # x in (x0, x_left]\n            add(1, y - x_left)  # x in (x_left, y)\n\n        return list(accumulate(A))\n```
['Python3']