尺取法

Codeforces 也把这种算法叫做 "two pointers" ,翻译为双指针。我觉得“双指针”的叫法比较宽泛，“尺取法”专指两个下标指针 $l$ 和 $r$ 单向移动，类似于“尺蠖[chǐ huò]”，移动过程,一般用于解决一类具有单调性的区间问题（区间左端点 l 往前移动，右端点 r 只会单调往前移动），当然这类问题很多情况下可以用二分解决，使用尺取法左右指针扫描一次区间，算法复杂度比二分优，能达到 $O(n)$. 算法基本过程可以描述为： 维护两个下标指针 $l$ 和 $r$, 每次 $l$ 往前移动 $1$ 个位置, $r$ 往前移动直到区间 $[l,r]$ 题目要求，更新一下当前答案或输出。

例1 . 子序列

改编自 Sequence poj 3061 , UVA1121

题意：给定一个长度为 $n(10 \leq n \leq 10^7)$ 的正整数序列 和一个正整数 $S$,求一段最短的子区间(连续)，区间和大于等于 $S$ ,输出最短子区间长度.

分析：

暴力枚举区间左右端点，使用前缀和计算区间和，时间复杂度为 $O(n^2)$ ,显然 $TLE$ 。

1. (二分) 当固定区间左端点 $l$ ,由于所有数都是正整数，区间右端点 $r$ 越大，对应区间值越大，存在单调性，可以二分找到最小的 $r$ 使得区间 $[l,r]$ 和大于等于 $S$,那么我们枚举区间左端点，二分查找区间右端点，时间复杂度为 $O(n\log {n})$.

2. (尺取法) 我们发现区间左端点 $l$ 往前移动，区间右端点 $r$ 只会往右移动(所有数大于等于 $0$ )，那么可以用尺取法。

• 1. 初始化当前区间为空: $l=1,r=0$，区间和 $sum=0$
• 2. 循环进行，直到 $l$ 越界：
  • 循环移动 $r$ 直到 区间 $[l,r]$ 区间和 $sum$ 大于等于 S , 即 while(r+1<=n && sum<S)r++,sum+=a[r];
  • 判断 $sum$ 如果小于 S，跳出循环
  • 更新答案 ans=min(ans,r-l+1);
  • 移动左指针 $l$，即 sum-=a[l],l++;

时间复杂度为: $O(n)$,参考代码：

#include<bits/stdc++.h>
using namespace std;
#define int long long
const int N=1e7+10;
int n,a[N],s;
signed main()
{
	ios::sync_with_stdio(false);
	cin.tie(0);
	while(cin>>n>>s)
	{
		for(int i=1;i<=n;i++)cin>>a[i];
		
		int ans=N;
		int l=1,r=0,sum=0;   //初始化当前区间为空 
		while(l<=n)
		{
			while(r+1<=n && sum<s){r++;sum+=a[r]; }  //向前移动 r 直到符合要求
			
			if(sum<s)break;       //说明区间不可能满足答案
			
			ans=min(ans,r-l+1);     //更新答案 
			sum-=a[l];l++;        //移动左端点
		}
		
		if(ans<N) cout<<ans<<"\n";
		else  cout<<0<<"\n";
	}
	return 0;
}

反思： 本题中如果数字 $a_i$ 可以是负数,那么尺取法还正确吗？想一想

练习题：P1147 连续自然数和

例2：P1638 逛画展

问题：给定一个长度为 $n(1 \leq n \leq 10^6)$ 由 $1 \dots m (1 \leq m \leq 2*10^3)$ 构成的整数序列，求一个最短的子区间，子区间包括 $1 \dots m$中任意一个数。

分析：本题也存在单调性，当固定区间左端点 $l$, 右端点 $r$ 越大区间 $[l,r]$ 越会满足条件(包含 $1 \dots m$ 中任意一个数),理论上也可以二分求得最小的 $r$ ,但判断一个区间 $[l,r]$ 是否包含 $1 \dots m$ 中任意一个数比较麻烦(有 $\log$ 的时间复杂度)，我们发现 $l$ 每次往前移动，$r$ 也必然增大，存在单调性，尺取法可以派上用处。

• 初始化定义一个 num[1...m] 数组，num[i] 表示 $i$ 出现的次数, $cnt$ 表示 $num$ 数组中非零的个数。 l=1,r=0,num[]=0,cnt=0
• 循环进行直到区间左端点 $l$ 越界
  • 循环移动 $r$ ，直到区间 $[l,r]$ 符合题意，借助 $num[]$ 计数数组
  • 如果数量不够（cnt<m），跳出循环 （此时说明后续也不可能）
  • 用当前区间 $[l,r]$ 更新答案
  • $l$ 往前移动 $1$ 个位置

时间复杂度 $O(n)$ ,参考代码如下：

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=1e6+10;
int n,m,a[N];
int num[2005],cnt; 
int main()
{
	ios::sync_with_stdio(0);cin.tie(0);  //关闭流同步，优化读入输出速度
	cin>>n>>m;
	for(int i=1;i<=n;i++)cin>>a[i];
	int len=n+1,l=1,r=0;
	int ansa,ansb;
	while(l<=n)
	{
		while(r+1<=n && cnt<m)   //移动 r 直到区间[l,r]满足题意 
		{
			++r;
			num[a[r]]++;
			if(num[a[r]]==1)cnt++;
		}
		if(cnt<m)break;
		if(r-l+1<len)   //更新答案 
		{
			len=r-l+1;
			ansa=l,ansb=r;
		}                
		//移动 l,移动前把个数减少 
		num[a[l]]--;
		if(num[a[l]]==0)cnt--;
		l++;
	} 
	cout<<ansa<<" "<<ansb; 
	return 0;
}

类似题目：唯一的雪花 Unique Snowflakes

问题简述： 给定一个长度为 $n$ 的序列，求一个最长的区间 使得区间内没有相同的数字，输出区间长度。

尺取法参考代码：点击

例3 [ABC098D] Xor Sum 2

题意：给定一个长度为 $n(1 \leq n \leq 2*10^5)$ 的数组 $a_i( 0 \leq a_i \leq 2^{20})$,求有多少个非空子区间的 区间和等于区间异或和。

样例1

4
2 5 4 6

6

分析：首先找一些规律，样例 $1$ 中 $4$ 个数写成二进制 10,101,100,110,发现区间 $a[1,2]$ 是符合区间和等于区间异或和的，进而可以得到规律：如果一个区间中所有数对应二进制各个位上 $1$ 只出现了 $1$ 次，那么这个区间必然符合区间和等于区间异或和，这个规律是充要的。

当区间左端点 $l$ 固定，寻找最大的右端点 $r$,那么区间 $[l,l]、[l,l+1]...[l,r]$ 这些区间必然都符合要求,对答案的贡献增加 $r-l+1$。 当 $l$ 向前移动，$r$ 只会单调往前移动(移动长度大于等于 $0$ ),这是可以使用尺取法的根本原因。

参考代码如下：

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=2e5+10;
ll n,a[N],sum,s;   //sum为区间和 s为区间异或和 
//区间a[l...r] 中二进制各位上 1 只出现一次 就会符合题意 
// 固定l,r具有单调性 因此可以使用尺取法 
int main()
{
	ios::sync_with_stdio(0);cin.tie(0);
	cin>>n;
	for(int i=1;i<=n;i++)cin>>a[i];
	int l=1,r=0;
	ll ans=0;
	while(l<=n)
	{
		while(r+1<=n && (sum+a[r+1])==(s^a[r+1]))  // 异或运算优先级低 括号不能省
		{
			r++;
			sum+=a[r];
			s^=a[r];
		}
		ans+=r-l+1;
		sum-=a[l];
		s^=a[l];
		l++;
	} 
	cout<<ans;
	return 0;
}