题意

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

• (1leq lleq rleq n).
• (bigcup_{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;
}