【P2564】生日礼物（单调队列）

这个题看上去状态比较多，实际上由于题目的输出需要，又因为是一个线性的结构，所以我们可以有一些操作。

这么想，如果我们有了一个满足条件的区间，此时我们缩减左端点，然后判断此时是否还是满足，满足就继续缩减，不满足就伸长右端点，直到下一次又满足条件为止，复杂度差不多O（N）。

#include<iostream>
#include<cstdio>
#include<cstring>
#include<cmath>
#include<algorithm>
#include<queue>
#define re register
#define ll long long
using namespace std;
struct zz
{
    int a,b;
};
int b[1000001],h,t,n,m,x,num,minn=999999999,cnt;
zz d[1000001],q[1000001];
inline bool cmp(zz x,zz y)
{
    return x.a<y.a;
}
int main()
{
    cin>>n>>m;
    for(re int i=1;i<=m;i++)
    {
        cin>>x;
        for(re int j=1;j<=x;j++)
        {
            cin>>d[++num].a;
            d[num].b=i;
        }
    }
    h=1;t=0;
    sort(d+1,d+num+1,cmp);
    for(re int i=1;i<=n;i++)
    {
        q[++t]=d[i];
        b[d[i].b]++;
        if(b[d[i].b]==1)
        cnt++;
        while(cnt==m)
        {
            minn=min(minn,q[t].a-q[h].a);
            b[q[h].b]--;    
            if(b[q[h].b]==0)
            cnt--;
            h++;
        }
    }
    cout<<minn;
}