[数据结构与算法]【双指针模板】

有时在一个序列上，二段边界会和左边界同向移动，这时可以用双指针来降低一个 log 的时间复杂度。

模板分为两种：

1. 寻找最右 / 最左二段边界
2. 寻找等于某数值的区间

按边界左是 0 还是 1 分类：

• 寻找 11110000 的最右的一个 1
• 寻找 00001111 的最右的一个 0

按两指针是否能重合 ： 1. 不可重合 2. 可重合

在实现上的细节：假设序列范围是 [1,n]

• 如果能重合，i = 1 -> n，if(i == j) j ++ ;要放到循环最后
• 如果不能重合，i = 1 -> n-1，为 j 腾出位置，if(i == j) j ++ ;要放到循环最前

如果不存在有效区间，要注意防止 j 的回退。

模板：

寻找最右的 1

    for(int i = 1, j = 1; i <= n;  i ++ ) // 可重合， 11110000
    {
        while(j <= n && check(i, j)) j ++ ; if(i != j) j -- ;
        if(check(i, j)) ans += j - i + 1;
        if(i == j) j ++ ;
    }

寻找最右的 0

    for(int i = 1, j = 1; i < n;  i ++ ) // 不可重合， 00001111
    {
        if(i == j) j ++ ;
        while(j <= n && check(i, j) == 0) j ++ ; if(i + 1 != j) j -- ;
        if(check(i, j)) ans += j - i + 1;
    }

同理，如果要找最左的 1 或最左的 0，不用让 j 回退即可。注意特判越界的情况，要改为 if(j == n + 1) j -- ;

应用：在一个非严格递增（非严格递减同理）离散序列中，找到对应值的区间的左右端点。

举例：问一个序列中有多少个子序列满足和刚好等于 k 。

模板：固定左端点，右移两个右端点，要找到右端点的有效区间，则找到第一个 $a_{j_1}\ge k$ 和 $a_{j_2}\ge k+1$ 的区间， 即 $[j1,j2)$ 为所求。注意要排除不存在有效区间的情况，即 $j1>n$.

    for(int i = 1, j1 = 1, j2 = 1; i <= n; i ++ )
    {
        while(j1 <= n && query(i, j1) < k) j1 ++ ;
        while(j2 <= n && query(i, j2) <= k) j2 ++ ;
        if(j1 <= n) ans += j2 - j1;
        if(j1 == i) j1 ++ ;
        if(j2 == i) j2 ++ ;
    }

注：$query(i,j)$ 表示 ${\sum }_{k=i}^j{a}_k$
题目：小y的序列

最长连续不重复子序列： AC代码
dd爱框框：AC代码
Xor Sum 2：AC代码