按距离统计房屋对数目 II

难度: Hard

给你三个 正整数 n 、x 和 y 。

在城市中，存在编号从 1 到 n 的房屋，由 n 条街道相连。对所有 1 <= i < n ，都存在一条街道连接编号为 i 的房屋与编号为 i + 1 的房屋。另存在一条街道连接编号为 x 的房屋与编号为 y 的房屋。

对于每个 k（1 <= k <= n），你需要找出所有满足要求的 房屋对 [house₁, house₂] ，即从 house₁ 到 house₂ 需要经过的最少街道数为 k 。

返回一个下标从 1 开始且长度为 n 的数组 result ，其中 result[k] 表示所有满足要求的房屋对的数量，即从一个房屋到另一个房屋需要经过的最少街道数为 k 。

注意，x 与 y 可以相等。

示例 1：

输入：n = 3, x = 1, y = 3
输出：[6,0,0]
解释：让我们检视每个房屋对
- 对于房屋对 (1, 2)，可以直接从房屋 1 到房屋 2。
- 对于房屋对 (2, 1)，可以直接从房屋 2 到房屋 1。
- 对于房屋对 (1, 3)，可以直接从房屋 1 到房屋 3。
- 对于房屋对 (3, 1)，可以直接从房屋 3 到房屋 1。
- 对于房屋对 (2, 3)，可以直接从房屋 2 到房屋 3。
- 对于房屋对 (3, 2)，可以直接从房屋 3 到房屋 2。

示例 2：

输入：n = 5, x = 2, y = 4
输出：[10,8,2,0,0]
解释：对于每个距离 k ，满足要求的房屋对如下：
- 对于 k == 1，满足要求的房屋对有 (1, 2), (2, 1), (2, 3), (3, 2), (2, 4), (4, 2), (3, 4), (4, 3), (4, 5), 以及 (5, 4)。
- 对于 k == 2，满足要求的房屋对有 (1, 3), (3, 1), (1, 4), (4, 1), (2, 5), (5, 2), (3, 5), 以及 (5, 3)。
- 对于 k == 3，满足要求的房屋对有 (1, 5)，以及 (5, 1) 。
- 对于 k == 4 和 k == 5，不存在满足要求的房屋对。

示例 3：

输入：n = 4, x = 1, y = 1
输出：[6,4,2,0]
解释：对于每个距离 k ，满足要求的房屋对如下：
- 对于 k == 1，满足要求的房屋对有 (1, 2), (2, 1), (2, 3), (3, 2), (3, 4), 以及 (4, 3)。
- 对于 k == 2，满足要求的房屋对有 (1, 3), (3, 1), (2, 4), 以及 (4, 2)。
- 对于 k == 3，满足要求的房屋对有 (1, 4), 以及 (4, 1)。
- 对于 k == 4，不存在满足要求的房屋对。

提示：

2 <= n <= 10⁵
1 <= x, y <= n

Submission

运行时间: 484 ms

内存: 25.2 MB

# https://leetcode.cn/u/l00/

class Solution:
    def countOfPairs(self, n: int, x: int, y: int) -> List[int]:
        queue = [0] * (n + 1)
        ans = [0] * n

        # 统一标准 x 在前 y 在后
        x, y = min(x, y), max(x, y)
        
        # 最长链的长度 = x链 + y链 + 链接部分
        xLinkLength = x - 1
        yLinkLength = n - y
        linkLength = xLinkLength + yLinkLength + (1 if x == y else 2)

        # 长链上的点对量 - 直链上点对量与长度是两倍关系
        queue[0] = (linkLength - 1) << 1
        queue[1] = -queue[0] - 2
        queue[linkLength] += 2

        # 环的长度，以及环的半长
        ringLength = y - x + 1
        ringHalfLength = ringLength >> 1

        def add(head: int, length: int, num: int):
            queue[head] += num
            queue[head + length] -= num
        
        def linkToRing(linkLength: int):
            add(1, 1, 2)
            add(1 + linkLength, 1, -2)
            if ringHalfLength > 1:
                minLength = min(ringHalfLength - 1, linkLength)
                add(2, minLength, 4)
                tail = ringHalfLength + linkLength
                add(tail - minLength + 1, minLength, -4)
                if ringLength & 1 == 0:
                    add(tail - linkLength, 1, -2)
                    add(tail, 1, 2)

        # 【必要】剪枝 - 如果环不够 3 个点，实际就是没有环
        if ringLength > 2:
            # 剔除环与长度链重复统计部分
            ans[0] -= 2

            # 环上的点对量 - 可以看成链的情况但有两个方向，而且数量只有一半
            add(0, 1, ringLength << 1)
            add(ringHalfLength, 1, -(ringLength << 1))
            if ringLength & 1 == 0:
                add(ringHalfLength - 1, 1, -ringLength)
                add(ringHalfLength, 1, ringLength)

            # x链到环的点对量
            if xLinkLength: linkToRing(xLinkLength)
            # y链到环的点对量
            if yLinkLength: linkToRing(yLinkLength)
            
        res = diff = 0
        for index in range(n):
            diff += queue[index]
            res += diff
            ans[index] = res
        
        # 剔除环与长度链重复统计部分
        if ringLength > 2: ans[0] -= 2

        return ans

Explain

题解采用差分数组的方法来计算每个可能距离 k 下的房屋对数量。通过差分数组，能够高效地统计区间内的变化量，从而避免重复计算。整体策略涉及将房屋排列成一个环状和线性的结构，考虑额外连接的 x 和 y 形成的特殊路径。计算过程首先确定 x 和 y 的位置关系，使得 x 总是小于等于 y。接着计算 x 和 y 形成的环状结构的长度，并对不同的距离 k 计算可能的房屋对数量。这涉及到环内的计算以及环与直链之间的计算。差分数组被用于记录和更新距离变化，最终通过累加差分数组来得到每个距离下的房屋对数。

时间复杂度: O(n)

空间复杂度: O(n)

# 差分数组方法解题

class Solution:
    def countOfPairs(self, n: int, x: int, y: int) -> List[int]:
        queue = [0] * (n + 1)  # 差分数组
        ans = [0] * n  # 结果数组

        # 确保 x < y
        x, y = min(x, y), max(x, y)

        # 计算 x 和 y 之间线性距离
        xLinkLength = x - 1
        yLinkLength = n - y
        linkLength = xLinkLength + yLinkLength + (1 if x == y else 2)

        # 初始化差分数组
        queue[0] = (linkLength - 1) << 1
        queue[1] = -queue[0] - 2
        queue[linkLength] += 2

        # 计算环的长度和环的半长
        ringLength = y - x + 1
        ringHalfLength = ringLength >> 1

        def add(head: int, length: int, num: int):
            # 差分操作
            queue[head] += num
            queue[head + length] -= num

        def linkToRing(linkLength: int):
            # 连接到环的差分操作
            add(1, 1, 2)
            add(1 + linkLength, 1, -2)
            if ringHalfLength > 1:
                minLength = min(ringHalfLength - 1, linkLength)
                add(2, minLength, 4)
                tail = ringHalfLength + linkLength
                add(tail - minLength + 1, minLength, -4)
                if ringLength & 1 == 0:
                    add(tail - linkLength, 1, -2)
                    add(tail, 1, 2)

        # 处理环的影响
        if ringLength > 2:
            ans[0] -= 2
            add(0, 1, ringLength << 1)
            add(ringHalfLength, 1, -(ringLength << 1))
            if ringLength & 1 == 0:
                add(ringHalfLength - 1, 1, -ringLength)
                add(ringHalfLength, 1, ringLength)

            if xLinkLength: linkToRing(xLinkLength)
            if yLinkLength: linkToRing(yLinkLength)

        res = diff = 0
        for index in range(n):
            diff += queue[index]
            res += diff
            ans[index] = res

        # 最终调整
        if ringLength > 2: ans[0] -= 2

        return ans

Explore

在初始化差分数组时，初始值 `(linkLength - 1) << 1` 代表的是链条的长度（不包括两端的 x 和 y），每个间隔可以形成的房屋对数乘以 2（因为每对房屋可以互换位置）。这样设置是为了在累加差分数组时，每次遍历到的位置都能反映出从起点开始直到当前位置的累加房屋对数。使用 `-queue[0] - 2` 是为了在差分数组的第二个位置产生一个负的大幅调整，以结束初始设置的影响，保证后续计算的正确性。

环的长度大于2时，意味着环内至少有三个房屋，可以形成有效的房屋对。在这种情况下，环内的房屋对对差分数组的影响需要特别处理，尤其是考虑到环的对称性和可能的重叠。调整 `ans[0]` 的值是为了消除在环形结构中房屋自身与自身配对的可能性，因为在环的逻辑中，每个房屋都与环中的其他房屋形成对，而不包括自己。

差分数组是一种用来高效处理区间更新和查询的数据结构。`add` 函数通过在差分数组的 `head` 位置增加 `num`，然后在 `head + length` 位置减去 `num`，来表示从 `head` 开始，长度为 `length` 的区间内每个元素都增加 `num`。在通过差分数组更新后，累加差分数组就可以得到每个位置的实际值。在本题中，这种操作用于动态调整每个距离下的房屋对数量，最终通过累加差分数组的结果来填充结果数组 `ans`，每个索引位置的 `ans` 值表示对应距离下的房屋对数量。