每日一题

线段树
这个题可以先排序，从左到右做，每次更新这个颜色最后一次出现的位置，放入线段树。如果所有颜色都出现过，就去线段树中查询所有颜色最后一次出现时间的最小值。每次更新当前位置与这个最小值之差的最小值作为答案，时间复杂度为O(N(log n+log k))。线段树长度只用开k即可。

#include<cstdio>
#include<cstring>
#include<algorithm>
#define ls (k<<1)
#define rs (k<<1|1)
#define mid (l+r>>1)
#define Mid (t[k].l+t[k].r>>1)
int Min(int x,int y)
{
    return x<y?x:y;
}
struct node
{
    int l,r,v;
    node(int l,int r)
    {
        this->l=l;
        this->r=r;
        v=-1;
    }
    node()
    {
        v=-1;
    }
}t[500];
void build(int k,int l,int r)
{
    t[k]=node(l,r);
    if(l==r)
        return;
    build(ls,l,mid);
    build(rs,mid+1,r);
}
void change(int k,int p,int x)
{
    if(t[k].l==t[k].r)
    {
        t[k].v=x;
        return;
    }
    if(p<=Mid)
        change(ls,p,x);
    else
        change(rs,p,x);
    t[k].v=Min(t[ls].v,t[rs].v);
    return;
}
int ask(int k,int l,int r)
{
    if(t[k].l==l&&t[k].r==r)
        return t[k].v;
    if(r<=Mid)
        return ask(ls,l,r);
    else if(l>Mid)
        return ask(rs,l,r);
    else
        return Min(ask(ls,l,Mid),ask(rs,Mid+1,r));
}

struct ball
{
    int c,p;
    friend bool operator <(ball a,ball b)
    {
        return a.p<b.p;
    }
}a[1000010];
int cnt=0;
int main()
{
    int n,k,t,u;
    scanf("%d%d",&n,&k);
    build(1,1,k);
    for(int i=1;i<=k;i++)
    {
        scanf("%d",&t);
        for(int j=1;j<=t;j++)
        {
            scanf("%d",&u);
            a[++cnt].c=i;
            a[cnt].p=u;
        }
    }
    std::sort(a+1,a+1+n);
    int ans=0x7fffffff;
    for(int i=1;i<=n;i++)
    {
        change(1,a[i].c,a[i].p);
        int tmp=ask(1,1,k);//更新最晚值
        if(tmp==-1)//为-1说明还有颜色没找到
            continue;
        ans=ans<(a[i].p-tmp)?ans:(a[i].p-tmp);
    }
    printf("%d\n",ans);
    return 0;
}