三指针

在使用双指针维护一段序列时，可能会出现多个区间的情况，这时若是仅采用双指针移动，则会漏掉部分情况

可以再加入一个指针来，使两个指针维护一个子序列，使子序列和另外一个指针共同维护

这里以洛谷P1102为例：

我们需要对一段序列求满足条件的数对的数量，但由于序列中元素可以重复，所以两个快慢指针会漏掉一部分情况：

2 2 3 3 4 5 5 5 6 7 

假设 $i$ 指针和 $j$ 指针从头开始，当我们计算的 $A-B=C=3$ 时，数对数加一。

for (int i = 1, j=1; i <= n; i++) {
    while (i >= j && a[i] - a[j] >= c) {//保证i在j前面
        j++;
        if (a[i] - a[j] == c) ans++;
    }
}

当 $i$ 运动到第一个 $5$ 时，满足要求，此时移动 $j$ 到第二个 $2$，再次满足要求，在移动 $j$ 指向 $3$ ，不满足要求

则 $i$ 移动，但是会发现 $i$ 仍然指向的是 $5$ ，$j$ 却移动出了 $2$ 所在的区间，则答案会丢失一部分

采用三指针维护：

for (int i = 1, j1 = 1, j2 = 1; i <= n; i++) {
    while (i >= j1 && a[i] - a[j1] >= c)
        j1++;
    while (i >= j2 && a[i] - a[j2] > c)
        j2++;
    ans += j1 - j2;
}

我们让 $j_1$ 这个指针指向满足 $A-B=C=3$ 时，$j$ 序列的最后元素的下一个元素，即指向 $2$ 之后的 $3$ 、$j_2$ 指向 $j$ 序列的第一个元素，即指向第一个 $2$

ps：

a[i] - a[j1] >= c 可移项为 a[j1] <= a[i] - c
a[i] - a[j2] > c 可移项为 a[j2] < a[i] - c
可以看出在有序数列中 j2是小于j1 的

这时 $j_1-j_2$ 就是 $j$ 序列的长度，随后移动 $i$ 指针，直到移动出 $5$ 的区间，$ans$ 每次都加上 $j$ 序列的长度，保证不漏

完整代码：

#include <stdio.h>
#include <iostream>
#include <algorithm>
using namespace std;

int a[200010];
int n, c;
long long ans;
int main()
{
    scanf("%d %d", &n, &c);
    for (int i = 1; i <= n; i++) scanf("%d", &a[i]);
    sort(a + 1, a + n + 1);
    for (int i = 1, j1 = 1, j2 = 1; i <= n; i++) {
        while (i >= j1 && a[i] - a[j1] >= c)
            j1++;
        while (i >= j2 && a[i] - a[j2] > c)
            j2++;
        ans += j1 - j2;
    }
    printf("%lld", ans);
    return 0;
}