题目链接

题目大意

给定三个数组 $A, B, C$，以及一个非负整数 $d$。
求共有多少个三元组 $(i, j, k)$，满足：$|A_i - B_j| \le d, |A_i - C_k| \le d, |B_j - C_k| \le d$。

解题思路

双指针常用于解决计数类问题。

如果把 $A,B,C$ 三个数组合并到一个数组 $D$ 中，并将 D 数组排序，问题就转化为求所有满足 $D[j] - D[i]$ 的区间中能选出多少个 $A, B, C$；考虑到直接枚举区间的时间复杂度较高，而 D 数组具有单调性，因此可以使用双指针中的快慢指针来选择区间。

算法流程

还没写~

Code

#include <iostream>
#include <cstring>
#include <cmath>
#include <algorithm>
#include <utility>

const int MAXN = 300010;
typedef std::pair<int, int> PII;
typedef long long ll;
#define val first
#define id second

int n, d, cnt[3][MAXN];
PII D[MAXN];

void prework()
{
    std::sort(D + 1, D + n + 1);
    for (int i = 0; i < 3; i ++ )
        for (int j = 1; j <= n; j ++ )
            cnt[i][j] = cnt[i][j - 1] + (D[j].id == i);
}

void solve()
{
    int last = -1; // 上一次快指针的位置。
    ll res = 0;
    for (int i = 1, j = 1; i <= n; i ++ )
    {
        while (j <= n && D[j].val - D[i].val <= d) j ++ ;
        if (j > last)
        {
            int cnta = cnt[0][j - 1] - cnt[0][i - 1];
            int cntb = cnt[1][j - 1] - cnt[1][i - 1];
            int cntc = cnt[2][j - 1] - cnt[2][i - 1];
            res += (ll)cnta * cntb * cntc;
        }
        if (i <= last && last < j)
        {
            int cnta = cnt[0][last - 1] - cnt[0][i - 1];
            int cntb = cnt[1][last - 1] - cnt[1][i - 1];
            int cntc = cnt[2][last - 1] - cnt[2][i - 1];
            res -= (ll)cnta * cntb * cntc;
        }
        last = j;
    }
    printf("%lld\n", res);
}

int main()
{
    int l1, l2, l3, x;
    scanf("%d%d%d%d", &l1, &l2, &l3, &d);
    for (int i = 0; i < l1; i ++ )
    {
        scanf("%d", &x);
        D[++ n] = std::make_pair(x, 0);
    }
    for (int i = 0; i < l2; i ++ )
    {
        scanf("%d", &x);
        D[++ n] = std::make_pair(x, 1);
    }
    for (int i = 0; i < l3; i ++ )
    {
        scanf("%d", &x);
        D[++ n] = std::make_pair(x, 2);
    }

    prework();
    solve();
    return 0;
}