<p>You are given three <strong>positive</strong> integers <code>n</code>, <code>x</code>, and <code>y</code>.</p>

<p>In a city, there exist houses numbered <code>1</code> to <code>n</code> connected by <code>n</code> streets. There is a street connecting the house numbered <code>i</code> with the house numbered <code>i + 1</code> for all <code>1 &lt;= i &lt;= n - 1</code> . An additional street connects the house numbered <code>x</code> with the house numbered <code>y</code>.</p>

<p>For each <code>k</code>, such that <code>1 &lt;= k &lt;= n</code>, you need to find the number of <strong>pairs of houses</strong> <code>(house<sub>1</sub>, house<sub>2</sub>)</code> such that the <strong>minimum</strong> number of streets that need to be traveled to reach <code>house<sub>2</sub></code> from <code>house<sub>1</sub></code> is <code>k</code>.</p>

<p>Return <em>a <strong>1-indexed</strong> array </em><code>result</code><em> of length </em><code>n</code><em> where </em><code>result[k]</code><em> represents the <strong>total</strong> number of pairs of houses such that the <strong>minimum</strong> streets required to reach one house from the other is </em><code>k</code>.</p>

<p><strong>Note</strong> that <code>x</code> and <code>y</code> can be <strong>equal</strong>.</p>

<p>&nbsp;</p>
<p><strong class="example">Example 1:</strong></p>
<img alt="" src="https://assets.leetcode.com/uploads/2023/12/20/example2.png" style="width: 474px; height: 197px;" />
<pre>
<strong>Input:</strong> n = 3, x = 1, y = 3
<strong>Output:</strong> [6,0,0]
<strong>Explanation:</strong> Let&#39;s look at each pair of houses:
- For the pair (1, 2), we can go from house 1 to house 2 directly.
- For the pair (2, 1), we can go from house 2 to house 1 directly.
- For the pair (1, 3), we can go from house 1 to house 3 directly.
- For the pair (3, 1), we can go from house 3 to house 1 directly.
- For the pair (2, 3), we can go from house 2 to house 3 directly.
- For the pair (3, 2), we can go from house 3 to house 2 directly.
</pre>

<p><strong class="example">Example 2:</strong></p>
<img alt="" src="https://assets.leetcode.com/uploads/2023/12/20/example3.png" style="width: 668px; height: 174px;" />
<pre>
<strong>Input:</strong> n = 5, x = 2, y = 4
<strong>Output:</strong> [10,8,2,0,0]
<strong>Explanation:</strong> For each distance k the pairs are:
- For k == 1, the pairs are (1, 2), (2, 1), (2, 3), (3, 2), (2, 4), (4, 2), (3, 4), (4, 3), (4, 5), and (5, 4).
- For k == 2, the pairs are (1, 3), (3, 1), (1, 4), (4, 1), (2, 5), (5, 2), (3, 5), and (5, 3).
- For k == 3, the pairs are (1, 5), and (5, 1).
- For k == 4 and k == 5, there are no pairs.
</pre>

<p><strong class="example">Example 3:</strong></p>
<img alt="" src="https://assets.leetcode.com/uploads/2023/12/20/example5.png" style="width: 544px; height: 130px;" />
<pre>
<strong>Input:</strong> n = 4, x = 1, y = 1
<strong>Output:</strong> [6,4,2,0]
<strong>Explanation:</strong> For each distance k the pairs are:
- For k == 1, the pairs are (1, 2), (2, 1), (2, 3), (3, 2), (3, 4), and (4, 3).
- For k == 2, the pairs are (1, 3), (3, 1), (2, 4), and (4, 2).
- For k == 3, the pairs are (1, 4), and (4, 1).
- For k == 4, there are no pairs.
</pre>

<p>&nbsp;</p>
<p><strong>Constraints:</strong></p>

<ul>
	<li><code>2 &lt;= n &lt;= 10<sup>5</sup></code></li>
	<li><code>1 &lt;= x, y &lt;= n</code></li>
</ul>

class Solution:
    def countOfPairs(self, n: int, x: int, y: int) -> List[int]:
        '''
        for x < j < y, when to take the added edge:
        j - i > x - i + 1 + y - j
        2*j > x + 1 + y
        j in [(x+1+y)/2 + 1, y - 1]
        '''
        if x > y:
            x, y = y, x
        diff = [0]*(n+1)
        def add(l, r, v):
            if l > r:
                return
            diff[l] += v
            diff[r+1] -= v
            return
        '''
        1 1 <= i <= x:
          undo  [y-i, n-i] -1
          dec = y - x - 1
          update  [y-i-dec, n-i-dec] + 1
          for destination on the ring:
          j-i > x-i+1+y-j => j > (x+1+y)/2
          
          mid = (x+1+y)/2 + 1
          undo [mid-i, y-1-i]-1
          dec = (mid-i)-(x-i+1+y-mid)=2*mid-(x+1+y)
          update [mid-i-dec, y-1-i-dec]+1
        '''
        def update1(i, x, y):
            add(y-i, n-i, -1)
            dec = y - x - 1
            add(y-i-dec, n-i-dec, 1)
            mid = (x+1+y)//2 + 1
            add(mid-i, y-1-i, -1)
            dec = 2*mid-(x+1+y)
            add(x - i + 2, x - i + y - mid + 1, 1)
        '''
        2 x < i <= (x + y)/2
          undo  [y-i, n-i] -1
          dec = (y - i) - (i - x + 1)
          update  [y - i - dec, n - i - dec] +1

          j = i + (y - x + 1) // 2 + 1
          undo [j - i, y - 1 - i] -1
          dec = x - 2*i - 2
          update [i - x + 2, i - x + y - j + 1]+1
        '''
        def update2(i, x, y):
            add(y - i, n - i, -1)  # 撤销 [y,n]
            dec = (y - i) - (i - x + 1)  # 缩短的距离
            add(y - i - dec, n - i - dec, 1)

            mid = i + (y - x + 1) // 2 + 1
            add(mid - i, y - 1 - i, -1)  # 撤销 [j, y-1]
            add(i - x + 2, i - x + y - mid + 1, 1)
        
        for i in range(1, n + 1):
            '''        
            without edge, for point i:
            left: [1, i-1] +1
            right [1, n-i] +1
            '''
            add(1, i - 1, 1)
            add(1, n - i, 1)
            if x + 1 >= y:
                continue
            if i <= x:
                update1(i, x, y)
            elif x < i < (x + y) // 2:
                update2(i, x, y)
            elif y > i > (x + y + 1) // 2:
                update2(n + 1 - i, n + 1 - y, n + 1 - x)
            elif i >= y:
                update1(n + 1 - i, n + 1 - y, n + 1 - x)
            '''
            3 (x + y)/2 < i < y
            4 y <= i <= n

            3 and 4 can be obtained with synmetry by replacing point
            i with n + 1 - i
            '''
        return list(itertools.accumulate(diff))[1:]
1373