在此处输入标题

未分类

小明：$|x|\to |y|$
小红：$|x-y| \to |x+y|$

假设$x \ge 0$,$y \ge 0$

• 若$x \ge 0$,$y \ge 0$，$~x >= y$
  此时二者的区间分别是：

  • 小明：$[y, x]$
  • 小红：$[x-y, x+y]$

  令：
  

  $$x - y \le y \le x \le x + y$$
  可得：
  $$y \ge {x\over 2}$$

  即只需要满足$~y\ge {x\over 2} \ge 0~$，就可以达到要求。

• 若$x \ge 0$,$y \ge 0$，且$~x < y$
  此时二者的区间分别是：

  • 小明：$[x, y]$
  • 小红：$[y-x, y+x]$

  令：
  

  $$y - x \le x \le y \le y + x$$
  可得：
  $$y \le {2x}$$

  即需要满足$~0 \le y \le 2x~$。

综上，若$~x \ge 0, y\ge 0$，则需要满足$~{x\over 2} \le y \le 2x$

类似地，可以得出$~x \ge 0, y\lt 0$，$x \lt 0, y \ge 0$，$x \lt 0, y \lt 0~$三种情形的结果。综合起来就是：

只需要$~(x,y)~$落在以下区间内即可：

因此，可以遍历$~x$，然后求出和上述区间的4个交点（假设从下往上依次为$~(x,y_0),(x,y_1),(x,y_2),(x,y_3)$），然后计算原数组中有多少个元素满足$~y_0\le a_i\le y_1~$或者$~y_2 \le a_i \le y_3~$，累加起来就是总个数。当然，还有2点需要注意：
- 第1/3象限的区块包含了$~y=x~$这条直线，而题目中还隐含了$~y\ne x~$的条件，所以这条直线上的点需要排除掉
- 4个区块关于$~y=x~$对称，这会导致对任意的$~(x,y)~$，$(y,x)~$也必然落在区间内，所以最后求出的结果需要除以2

下面考虑对任意的$~x=a_i$，怎么求原数组中满足$~y_0\le a_i \le y_1~$的个数：只需要将数组排序，求出第一个$~\ge y_0~$的下标$~s~$和最后一个$~\le y_1~$的下标$~t$，结果就是$~t-s+1$。用二分就可以了。

#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
typedef long long ll;
const int MAX = 200019;
ll a[MAX];
int n;
// find num of elements in range [low, high]
int find_range(ll low, ll high, ll target) {
    if (low > a[n-1] || high < a[0]) {
        return 0;
    }
    int lb = lower_bound(a, a + n, low) - a;
    int ub = upper_bound(a, a + n, high) - a - 1;
    // printf("find_range(%d,%d)=%d\n", low, high, ub - lb);
    if (a[lb] <= target && target <= a[ub]) {
        return ub - lb < 0 ? 0 : ub - lb;
    }
    return ub - lb + 1;
}
int main() {
    while (~scanf("%d", &n)) {
        for (int i = 0; i < n; i++) {
            scanf("%lld", a + i);
        }
        sort(a, a + n);
        ll sum = 0LL;
        for (int i = 0; i < n; i++) {
            if (a[i] < 0) {
                sum += find_range(a[i]<<1, a[i]-1>>1, a[i]);
                sum += find_range(-a[i]-1>>1, -a[i]<<1, a[i]);
            } else {
                sum += find_range(-a[i]<<1, -a[i]-1>>1, a[i]);
                sum += find_range(a[i]+1>>1, a[i]<<1, a[i]);
            }
        }
        printf("%lld\n", sum>>1);
    }
    return 0;
}