[洛谷P2564][题解][SCOI2009]生日礼物

0.杂谈

这里似乎咕了好久了呢……刚水过掉了一个挺有意思的题，特此水写题解记录。

1.题目

给出一段序列，每个位置可能对应0到多种颜色，求一段最短的区间，使其包含所有的颜色。

2.题解

先给出此题核心代码：

sort(p+1,p+1+n);
for(rg int tl=1,hd=1,cnt=0;tl<=n;tl++){
	if(!ps[p[tl].kind])cnt++;
	ps[p[tl].kind]=p[tl].pos;
	while(hd<=tl&&p[hd].pos!=ps[p[hd].kind])hd++;
	if(cnt==k&&(p[tl].pos-p[hd].pos<ans))ans=(p[tl].pos-p[hd].pos);
}

一行一行地解释。
p是珠子数组，存了位置和种类，按位置从小到大排序；hd和tl是当前队列的头尾。
if(!ps[p[tl].kind])cnt++;：第一次出现，计数。
ps[p[tl].kind]=p[tl].pos;：更新位置数组。
while(hd<=tl&&p[hd].pos!=ps[p[hd].kind])hd++;：队头已不是唯一，对答案没有帮助。
if(cnt==k&&(p[tl].pos-p[hd].pos<ans))ans=(p[tl].pos-p[hd].pos);：当前区间满足条件，更新答案。

3.代码

什么？上面给的不是代码？

4.完结撒花

听说这算法叫(2-pointer)...怕是学过忘了......
复杂度排序(O(nlog n))，模拟(O(n))。
然而洛咕的算法标签是单调队列。。。