# 尺取法与区间统计课堂笔记

一、连续区间

连续的一段范围用两个指针表示：

l              r
↓              ↓
a[l] ... ... a[r]

区间长度：

r-l+1

尺取法中，l和r只向右移动，因此复杂度通常是O(n)。

---

二、前缀和统计区间数量

s[i]表示前i个位置中，满足条件的元素数量。

s[i]=s[i-1]+(a[i]==0);

区间[l,r]内满足条件的数量：

int sum=s[r]-s[l-1];

记忆：

右端点的前缀和 - 左端点前一位的前缀和

---

三、类型一：最多包含K个特殊元素的最长区间

例如：连续选择一段奶牛，最多把K头黑牛变成白牛，求最长长度。

指针移动

特殊元素数量 <= K：当前区间合法，更新最长答案，r向右
特殊元素数量 > K ：当前区间不合法，l向右

模板

#include<bits/stdc++.h>
const int N =1e6+10;
using namespace std;
int n,k,a[N],s[N],ans;
int main(){
	cin>>n>>k;
	for(int i=1;i<=n;i++){
		cin>>a[i];
		s[i]=s[i-1]+(a[i]==0);
	}
	int l=1,r=1;
	while(r<=n){
		int sum=s[r]-s[l-1];
		if(sum<=k) ans=max(ans,r-l+1),r++;
		else l++;
		if(l>r) r=l;
	}
	cout<<ans;
	return 0;
}

最长答案初值设为：

int ans=0;

不要使用INT_MIN。当一个位置都不能选时，正确答案可能是0。

---

四、输入的是“位置”时要先标记

有些题目不会给出完整的0/1数组，而是只给出特殊元素的位置。

例如输入：

10 30 55 56 90

表示这些位置是香蕉，不是把它们依次存入a[1]~a[n]。

正确标记：

for(int i=1;i<=n;i++){
	int x;
	cin>>x;
	a[x]=1;
}

然后建立前缀和：

for(int i=1;i<=L;i++)
	s[i]=s[i-1]+a[i];

读题时先判断

输入的是每个位置的内容？ → cin>>a[i]
输入的是若干特殊位置？   → cin>>x，a[x]=1

---

五、类型二：每种元素最多出现m次的最长区间

用cnt[x]表示当前区间中编号x出现了多少次。

模板

#include<bits/stdc++.h>
const int N =1e6+10;
using namespace std;
int n,m,a[N],cnt[N],ans;
int main(){
	cin>>n;
	for(int i=1;i<=n;i++) cin>>a[i];
	cin>>m;
	int l=1;
	for(int r=1;r<=n;r++){
		cnt[a[r]]++;
		//新加入的兵种超过m次，移动左端点
		while(cnt[a[r]]>m){
			cnt[a[l]]--;
			l++;
		}
		ans=max(ans,r-l+1);
	}
	cout<<ans;
	return 0;
}

为什么只检查a[r]

加入a[r]之前，原区间是合法的。加入新元素后，只有a[r]这一种元素的数量可能超过m。

这种写法的好处

• 不需要额外使用bool记录区间是否合法。
• 不会在r++后访问a[n+1]。
• 每次循环结束时，区间一定合法。

---

六、类型三：包含全部种类的最短区间

先统计整个数组一共有多少种不同元素，记为need。

尺取过程中：

• cnt[x]：当前区间中x出现的次数。
• have：当前区间已经包含多少种不同元素。

指针移动

have < need ：种类不够，r向右扩大区间
have == need：已经包含全部种类，记录最短答案，l向右缩短

模板

#include<bits/stdc++.h>
const int N =1e6+10;
using namespace std;
int n,a[N],all[N],cnt[N],need,have,ans=N;
int main(){
	cin>>n;
	for(int i=1;i<=n;i++){
		cin>>a[i];
		if(all[a[i]]==0) need++;
		all[a[i]]++;
	}
	int l=1;
	for(int r=1;r<=n;r++){
		cnt[a[r]]++;
		if(cnt[a[r]]==1) have++;
		while(have==need){
			ans=min(ans,r-l+1);
			cnt[a[l]]--;
			if(cnt[a[l]]==0) have--;
			l++;
		}
	}
	cout<<ans;
	return 0;
}

---

七、前缀计数判断区间中是否出现某个值

当元素值范围较小，可以记录每个值的前缀出现次数。

s[i][v]

表示前i个数中，数值v出现了多少次。

建立：

for(int i=1;i<=n;i++){
	cin>>a[i];
	for(int v=0;v<=500;v++) s[i][v]=s[i-1][v];
	s[i][a[i]]++;
}

区间[L,R]中数值v出现的次数：

s[R][v]-s[L-1][v]

判断是否出现过：

if(s[R][v]-s[L-1][v]>0)

注意：判断“是否出现”要和0比较，不能和数值v比较。

错误：

if(s[R][v]-s[L-1][v]==v)

正确：

if(s[R][v]-s[L-1][v]>0)

---

八、三种题型快速判断

题目要求	满足条件时	不满足条件时	答案
最长，特殊元素不超过K	更新答案，扩大右边	缩小左边	max
最长，每种元素不超过m	更新答案	删除左边直到合法
最短，包含全部种类	更新答案，缩小左边	扩大右边	min

记忆

求最长：合法就继续扩大。
求最短：合法就尝试缩小。

---

九、常见错误

1. 把“特殊位置”错误存进a[i]，应该标记a[x]。
2. 区间和写成a[r]-a[l-1]，正确是s[r]-s[l-1]。
3. 最长答案使用INT_MIN，正确初值通常是0。
4. 最短答案初值太小，应该先设成很大的数。
5. r++后直接访问a[r]，可能访问到a[n+1]。
6. 计数数组增加后，忘记在l右移时减掉a[l]。
7. “出现过”应该判断次数>0。
8. 最长和最短问题的指针移动方向写反。
9. 没有根据n和元素值范围开足数组。

---

十、考前速记

区间长度：r-l+1
区间数量：s[r]-s[l-1]

最长且数量<=K：
合法 → ans=max，r++
不合法 → l++

最短且包含全部种类：
种类不够 → r++
种类齐全 → ans=min，l++

当前种类第一次加入：cnt[x]从0变1，have++
当前种类全部删除：cnt[x]从1变0，have--

输入特殊位置：a[x]=1
判断区间出现：次数>0