给你一条有n个点的数轴，每个点属于一个种类，总共有k个种类。求一段最短的线段，使对于每个种类，这段线段上有至少一个点属于它。

1.对于50%的数据，N≤10000

对于每一个从左到右枚举的l，从左到右枚举r>=l并不断加入r号彩珠，直到满足条件为止，更新答案。

时间复杂度O(n2)。

2.对于80%的数据，N≤800000

预处理k个种类的前缀和。对于每一个从左到右枚举的l，进行O(klog2n)的二分询问。

时间复杂度O(nklog2n)

3.对于100%的数据，1≤N≤1000000，1≤K≤60，0≤Ti<231

动态维护一个大小为k的离散数组，s[i]表示当前状态下第i个种类的彩珠数。深入考虑算法一，我们发现对于每一个从左到右枚举的l，r是单调不减的。于是固定l时，不断将r号彩珠加入s并右移指针r，直到满足条件为止，更新答案；当l自增时，在s中弹出原l号彩珠，不重置r。这样扫描的时间就是线性的了。

时间复杂度O(nk)

#pragma GCC optimize(2)
#include
#include
#include
#define REP(i,low,high) for(register int i=(low);i<=(high);i++)
using namespace std;

//ex_cmp {
template inline bool getcmp(T &target,const T &pattern,Compare comp)
{
return comp(pattern,target)?target=pattern,:;
}
//} ex_cmp

struct beat
{
int kind,pos; void input(const int &K) {kind=K,scanf("%d",&pos);}
bool operator<(const beat &another)const{return posn) break; getcmp(ans,beats[j].pos-beats[i].pos,less());
}
return printf("%d\n",ans),;
}