AcWing 2455 合法三元组的个数 Solution

#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;
}