# Bao Phủ

## Tóm tắt đề bài

Cho một dãy $a$ độ dài $n$ yêu cầu đếm số lượng cặp vị trí $(x, y), x \ne y$ sao cho: $min(|x - y|, |x + y|) \le min(|x|, |y|) \le max(|x|, |y|) \le max(|x - y|, |x + y|)$.

## Lời giải

### SubTask $01$ $(n \le 10^3)$ $\to$ $<O(n^2)>$

Ta đơn giản là duyệt trâu bỏ, xét tất cả các vị trí $(x, y)$ thỏa mãn và đếm.

    for (int i = 1; i <= n; i++)
    {
        for (int j = i + 1; j <= n; j++)
        {
            if (i == j) continue;
            if (min(abs(a[i] + a[j]),abs(a[i] - a[j])) <= min(abs(a[j]), abs(a[i])) && max(abs(a[j]), abs(a[i])) <= max(abs(a[i] + a[j]), abs(a[i] - a[j])))
            {
                dem++;
            }
        }
    }

### SubTask $02$ $(a_i \ge1 \forall i)$ $\to$ $<O(nlog(n))>$

**Nhận xét**: Ta nhìn vào công thức, khi $a_i \ge 1$ thì $|x - y| \le x$ khi mà $1 \le y \le 2 \times x$ và dĩ nhiêu $|x|, |y| \le |x + y|$.

Ta đưa về bài toán với mỗi $a_i$ ta đếm các giá trị chưa được xét có giá trị không vượt quá $2 \times a_i$. Ta sẽ quy định $a_i$ là giá trị bé hơn, giả sử $u$ là vị trí thỏa mãn $a_u \le 2 \times a_i$ và $u$ là lớn nhất, số cặp ta có thể tìm được với vị trí $i$ là $u - i$.

    sort(a + 1, a + n + 1);
    ll res = 0;
    for (int i = 1; i <= n; i++)
    {
        int u = upper_bound(a + 1, a + n + 1, a[i] * 2) - a - 1;
        if (a[u] > 2 * a[i]) u--;
        if (u > i) res += u - i;
    }
    cout << res;

### SubTask $03$ Không có ràng buộc gì $\to$ $<O(nlog(n))>$

**Nhật xét**: Giả sử, $x \le y$, ta có $2$ trường hợp:
$$
|x - y| \le |y|
\leftrightarrow x^2 - 2xy + y^2 \le y^2
\leftrightarrow x(x - 2y) \le 0
\leftrightarrow \begin{align}
\begin{cases}
x \le 0 \\
x \ge 2y
\end{cases} \\
\begin{cases}
x \ge 0 \\
x \le 2y
\end{cases}
\end{align}
\Rightarrow
\begin{cases}
x \ge 0 \\
x \le 2y
\end{cases} \\
$$
$$
|x + y| \le |y|
\leftrightarrow x^2 + 2xy + y^2 \le y^2
\leftrightarrow x(x + 2y) \le 0
\leftrightarrow \begin{align}
\begin{cases}
x \ge 0 \\
x \le -2y
\end{cases} \\
\begin{cases}
x \le 0 \\
x \ge -2y
\end{cases}
\end{align}
\Rightarrow
\begin{cases}
x \le 0 \\
x \ge -2y
\end{cases} \\
$$
$\Rightarrow \forall x \le y$ để thỏa mãn biểu thức thì $|x| \le |2y|$.

Vậy ta chuyển các giá trị $a_i = |a_i|$ và làm như SubTask $02$.
Có thể sử dụng hai con trỏ:

    sort(a + 1, a + n + 1);
    int pos = 1, ans = 0;
    for(int i = 1; i <= n; i++){
        while(a[pos] <= 2 * a[i] && pos <= n) pos++;
        ans += pos - i - 1;
    }