[SCOI2009] 生日礼物

题意

有 (n) 个二元组 ((a_i,b_i),1leq a_ileq k)，将他们按 (b) 的升序排列，求区间 ([l,r]) 满足：

• (1leq lleq rleq n).
• (igcup_{i=l}^ra_i={1,2,cdots,k}).

要求最小化 (b_r-b_l).

(nleq 10^6,kleq 60,b_ileq 2^{31}).

分析

典型的尺取法，维护每一类出现的次数以及出现的类数，尺取一下就行

#include<cstdio>
#include<algorithm>
#include<queue>
#define pii pair<int,int>
using namespace std;
const int N=1e6+6,K=65;
int n,k,l,r,ans=0x3f3f3f3f;
pii a[N];

int times[K],tot;
void movel(){
    times[a[l].second]--;
	if(!times[a[l].second])tot--;
	++l;
}
void mover(){
    while(r<n&&tot<k){
		++r;
		if(!times[a[r].second])++tot;
		times[a[r].second]++;
	}
}

int main(){
    scanf("%d%d",&n,&k);
	for(int i=1,cnt;i<=k;i++){
        scanf("%d",&cnt);
		for(int j=1,x;j<=cnt;j++)scanf("%d",&x),a[++l]=make_pair(x,i);
	}
	sort(a+1,a+n+1);
	l=1,r=0;
	do{
        mover();
		ans=min(ans,a[r].first-a[l].first);
		movel();
    }while(r<n);
	printf("%d",ans);
	return 0;
}