3妹：2哥2哥，国家又降息啦，贷款市场报价利率（LPR）为：1年期LPR为3.45%，与前值持平；5年期以上LPR为3.95%，较前值下调25个基点。 你的房贷是不是可以又少了？
2哥 : 是啊，一个月能省还好几百呢。
3妹：省下来的钱用来干嘛，不如请我吃饭吧，嘿嘿。😁
2哥 : 也不是不可以，正好我也好久没吃大餐了，走，去搓一顿！
3妹：走着！话说2哥，你买的房子离你公司距离那么远，你准备去住吗？
2哥：暂时不住，近的我也买不起啊。工作可以换的嘛，哈哈
3妹：有道理。
2哥：说到房屋的距离，我今天看到一个关于“房屋的距离”的题目，让我们一起来做下吧~
题目：
给你三个 正整数 n 、x 和 y 。
在城市中，存在编号从 1 到 n 的房屋，由 n 条街道相连。对所有 1 <= i < n ，都存在一条街道连接编号为 i 的房屋与编号为 i + 1 的房屋。另存在一条街道连接编号为 x 的房屋与编号为 y 的房屋。
对于每个 k（1 <= k <= n），你需要找出所有满足要求的 房屋对 [house1, house2] ，即从 house1 到 house2 需要经过的 最少 街道数为 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^5
1 <= x, y <= n
思路：
分类讨论+撤销操作
首先，如果没有额外加一条在 x 和 y 之间的边，那么对于房子 i：
它到它左侧房子的最短距离分别是 1,2,3,⋯ ，用差分数组把 [1,i−1]都加一。
然后考虑 x 和 y 加的这条边带来的影响。假设 x≤y，如果 x+1≥y，那么这条边不影响最短距离. 否则分类讨论
java代码：
class Solution {
public long[] countOfPairs(int n, int x, int y) {
if (x > y) {
int temp = x;
x = y;
y = temp;
}
diff = new int[n + 1];
for (int i = 1; i <= n; i++) {
add(1, i - 1, 1);
add(1, n - i, 1);
if (x + 1 >= y) {
continue;
}
if (i <= x) {
update(i, x, y, n);
} else if (i >= y) {
update(n + 1 - i, n + 1 - y, n + 1 - x, n);
} else if (i < (x + y) / 2) {
update2(i, x, y, n);
} else if (i > (x + y + 1) / 2) {
update2(n + 1 - i, n + 1 - y, n + 1 - x, n);
}
}
long[] ans = new long[n];
long sumD = 0;
for (int i = 0; i < n; i++) {
sumD += diff[i + 1];
ans[i] = sumD;
}
return ans;
}
private int[] diff;
private void add(int l, int r, int v) {
if (l > r) return;
diff[l] += v;
diff[r + 1] -= v;
}
private void update(int i, int x, int y, int n) {
add(y - i, n - i, -1); // 撤销 [y,n]
int dec = y - x - 1; // 缩短的距离
add(y - i - dec, n - i - dec, 1);
int j = (x + y + 1) / 2 + 1;
add(j - i, y - 1 - i, -1); // 撤销 [j, y-1]
add(x - i + 2, x - i + y - j + 1, 1);
}
private void update2(int i, int x, int y, int n) {
add(y - i, n - i, -1); // 撤销 [y,n]
int dec = (y - i) - (i - x + 1); // 缩短的距离
add(y - i - dec, n - i - dec, 1);
int j = i + (y - x + 1) / 2 + 1;
add(j - i, y - 1 - i, -1); // 撤销 [j, y-1]
add(i - x + 2, i - x + y - j + 1, 1);
}
}
