题目传送门

模拟赛的题，我什么时候也能场切蓝了？

思路：

双指针，因为要找满足条件的最短区间，显然可以双指针解决。

初值左指针 $l=1$，右指针 $r=0$。

操作如下：

1. 若区间 $[l,r]$ 还不满足满足条件，则 $r \gets r+1$。
2. 若区间 $[l,r]$ 已经满足条件，更新答案 $ans=\min(ans,r-l+1)$ 并 $l \gets l+1$。
3. 重复操作一和操作二直到 $r>N$。

对于判断一个区间是否满足条件，使用一个数组记录要满足的条件离满足还差什么，每次右指针右移时更新，当整个数组中所有值均小于等于 $0$ 时就满足条件了。

完整代码：

#include <bits/stdc++.h>
using namespace std;
inline int read() {
	int x=0,f=1;
	char ch=getchar();
	while (ch<'0'||ch>'9') {
		if (ch=='-') f=-1;
		ch=getchar();
	}
	while (ch>='0'&&ch<='9') {
		x=x*10+ch-48;
		ch=getchar();
	}
	return x*f;
}
void out(int x) {
	if(x<0)putchar('-'),x=-x;
	if(x<10)putchar(x+'0');
	else out(x/10),putchar(x%10+'0');
}
int n,k,r;
int m[200005];
bool vis[200005];
int mq[200005],ss=0;
int main() {
	n=read();
	k=read();
	r=read();
	for(int i=1; i<=n; i++) m[i]=read();
	for(int i=1; i<=r; i++) {
		int a=read(),b=read();
		mq[a]=b;
		ss+=b;
		vis[a]=true;
	}
	int l=1,r=0,ans=INT_MAX;
	while(1) {
		if(ss!=0) {
			r++;
			if(r>n) break;
			if(vis[m[r]]==true) {
				mq[m[r]]--;
				if(mq[m[r]]>=0) ss--;
			}
		}
		else{
			l++;
			if(vis[m[l-1]]==true){
				mq[m[l-1]]++;
				if(mq[m[l-1]]>0) ss++;
			}
		}
		if(ss==0) ans=min(ans,r-l+1);
	}
	if(ans==INT_MAX) cout<<"impossible\n";
	else cout<<ans<<endl;
	return 0;
}