P7234 [JSOI2014] 歌剧表演

· · 题解

首先考虑如何区分两个人（假设只有两个人）。

不难发现对于任意两个人 x,y，如果他们参加的表演集合不同（即至少有一天 x 上场了但是 y 没上场，或者 y 上场了但是 x 没上场），就可以区分 x,y。

这启发我们可以维护若干个集合，每个集合中的人参加的表演集合相同。

如果一个集合大小为 1，此时我们就能认出这个人（你可以同时对照片和姓名维护上文所述集合，你发现这个时候只有一张照片能与这个姓名在表演集合上匹配，然后你就能认出他，但是维护的时候显然不需要维护两个，仅供理解）。

接下来考虑如何维护上文所述集合。

首先，你无需维护参加的表演集合，因为我们只需要知道有哪些（人的）集合，而不需知道他们参加过那些表演。

这样初始时所有人都在集合 0 中。

每进行一场表演，就相当于更改一些人的表演集合，此时有些集合会分裂，注意到分裂的时候只会分裂参加这场表演的人。

于是对于每场表演，在参演人员中找到在同一个集合里的，直接分裂成一个新集合，考虑到此时只有原集合以及新集合的大小可能为 1，暴力检查就行。

注意到分裂出一个新集合至少需要一个人参加表演，所以集合数目至多为 \sum k。

这样就可以把一场表演的复杂度降到 O(k \log k)，带 \log 是因为找相同集合的人的时候用了 \text{sort} 实现。

具体细节可以看代码。

Code:


int n,m,k;
int tag[100005],xorsum[200005],num[200005],cnttag;
// tag 表示这个人在哪个集合
// xorsum 是一个集合里所有人编号的异或和，用于在集合大小为 1 的时候找到这个人。
int Ans[100005];
pii tmp[100005]; int cnt;
int checklist[100005],cntchecklist;
signed main() {
    n=read(); m=read(); tmp[0]=make_pair(-1,-1);
    for(int i=1; i<=n; ++i) xorsum[0]^=i; num[0]=n;
    for(int T=1; T<=m; ++T) {
        k=read(); cnt=0; cntchecklist=0;
        for(int i=1,x; i<=k; ++i) {
            x=read();
            if(!Ans[x]) tmp[++cnt]=make_pair(tag[x],x);
        }
        sort(tmp+1,tmp+cnt+1);
        for(int i=1; i<=cnt; ++i) {
            if(tmp[i].first!=tmp[i-1].first) {
                tag[tmp[i].second]=++cnttag;
                checklist[++cntchecklist]=tmp[i].first;
                checklist[++cntchecklist]=cnttag;
            } else tag[tmp[i].second]=cnttag;
            --num[tmp[i].first]; xorsum[tmp[i].first]^=tmp[i].second;
            ++num[cnttag];       xorsum[cnttag]^=tmp[i].second;
        }
        for(int i=1; i<=cntchecklist; ++i) if(num[checklist[i]]==1) Ans[xorsum[checklist[i]]]=T; 
    }
    for(int i=1; i<=n; ++i) write(Ans[i]),putchar(" \n"[i==n]);
    return 0;
}