一.题意

题意要求找到最短的包含 1 -> m 所有种类的元素的区间
对于这个区间我们可以看成一个set,
则我们需要维护的set信息有:
1: int cnt[N] :每种元素的个数
2: int now :当前种类数
3: int l,r :左右端点(不是废话??)

二.性质&&分析

尝试使用双指针维护这样一个左闭右开的区间 [l,r)
此时区间包含的元素就是 a[l]…a[r-1] , 长度为 r-l
初始情况为集合中没有一个元素,l=r=1
我们只允许左右端点向右移动,容易发现,左端点向右移动会使集合元素种类呈减少的趋势,而右端点呈增加趋势
对于每次区间移动之前,分为两种情况:
case1: now < m :只有移动右端点,才可能找到满足条件的集合
case2: now = m :尝试向右移动左端点,如果now不变,说明找到了更小的区间,更新答案即可
如果now变了,进入case1

三.细节

怎么知道now有没有变呢?
我们维护了一个cnt[N],它实时记录了集合中各种元素的数量
当区间变化时,增加或减少元素,都需要维护cnt[N]
当元素种类数发生变化时
1:增加:只会由右端点右移引起,新添加的元素使得集合中该种元素的数量从0->1
2:减少:只会由左端点右移引起,新删除的元素使得集合中该种元素的数量从1->0
当我们找到一个新的满足条件的集合时,当且仅当当前区间长度小于minlen时才可以更新,这样才能满足题目中的相同长度区间优先在前面 这个条件

四.code