[JZOJ3864]【JSOI2014】歌剧表演

Description

Solution

这题非常有意思。
本来我想各种二进制搞一波，但我看到数据后我放弃了。。。

其实这题十分的水。

我们把目前分辨不出的放在同一集合。

那么对于演出操作，就是将演出的演员从原本的集合中分裂出来，如果某两个演员原本在同一集合，他们同时演出，那么显然还是分不出来，所以原来在同一集合的要连在新的同一集合。

对于每个集合，维护元素个数和元素最早变为1的时间即可。

Code

#include <cstdio>
#include <cstdlib>
#include <iostream>
#include <algorithm>
#include <cstring>
#include <cmath>
#define fo(i,a,b) for(int i=a;i<=b;i++)
#define fod(i,a,b) for(int i=a;i>=b;i--)
#define N 100005 
#define LL long long
using namespace std;
int n,m,ans[N],ft[N],sz[N],n1,pt[N],bz[N],ls[N],a[N],yh[N];
int main()
{
    cin>>n>>m;
    n1=1;
    fo(i,1,n) ft[i]=1;
    sz[1]=n;
    memset(ls,107,sizeof(ls));
    fo(i,1,m)
    {
        int q,x;
        scanf("%d",&q);
        fo(j,1,q)
        {
            scanf("%d",&x);
            a[j]=x;
            if(bz[ft[x]]!=i) 
            {
                if(sz[ft[x]]!=1) bz[ft[x]]=i,pt[ft[x]]=++n1;
                else pt[ft[x]]=ft[x];
            }
            sz[ft[x]]--,sz[pt[ft[x]]]++;
            yh[x]=ft[x];
            ft[x]=pt[ft[x]];
        }
        fo(j,1,q) 
        {
            if(sz[ft[a[j]]]==1) ls[ft[a[j]]]=min(ls[ft[a[j]]],i);
            if(sz[yh[a[j]]]==1) ls[yh[a[j]]]=min(ls[yh[a[j]]],i);
        }
    }
    fo(i,1,n)
    {
        if(sz[ft[i]]==1) printf("%d ",ls[ft[i]]);
        else printf("0 ");
    }
}