自动搬运

查看原文

来自洛谷，原作者为

	unputdownable 下雨不是任何人的错。

搬运于2025-08-24 22:37:20，当前版本为作者最后更新于2022-03-27 19:48:40，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

文中 $k_x$ 和 $S_x$ 的定义与题目相同。

文中所有 $x,y,z$ 都指人的编号，$i$ 都指题目的编号。

首先考虑一个暴力：

对于每一个题目 $i$，找出会 $i$ 这道题的所有人，将其按会的题目数 $k_x$ 从小到大排序。

然后我们检查上述排序后相邻的两个人是否会讨论即可。

这个暴力的正确性证明：

因为每次被排序的人都至少会同一道题 $i$，所以只要考虑是否完全包含即可。

假设 $x,y,z$ 三个人会同一题 $i$ 并且 $k_x \leq k_y \leq k_z$，那么如果 $x,y$ 和 $y,z$ 间都不会讨论，那么必然有 $S_x \subseteq S_y \subseteq S_z$，那么 $x,z$ 也必然不会讨论。

考虑优化上述暴力。

首先将所有人按 $k_x$ 从小到大排序，依次插入。

如果我们对于每一道题 $i$ 记录下会 $i$ 这道题的上一个人 $lst_i$，那么每次插入一个人 $x$ 的时候只需要检查 $\forall i \in S_x$，$lst_i$ 与 $x$ 会不会讨论。

但是这样由于每一个 $S_x$ 会被多次检查，复杂度仍然不对。

随后我们发现，在遍历 $S_x$ 的时候可以顺便求出 $S_x$ 与所有 $S_{lst_i}$ 的交集大小，于是我们可以直接通过交集大小是否为 $k_{lst_i}$ 来判断两个集合是否完全包含，即会不会讨论。

这样每次插入一个人的时间复杂度变为 $\Theta(|S_x|)$。

总体复杂度 $\Theta(n \log n +m)$，使用桶排可以去掉 $\log$。

Code：

int n;
int k[1000006],a[1000006];
vector <int> p[1000006];
int cnt[1000006];
inline void clear(vector <int> X) {
    vector <int> e;
    e.swap(X);
}
inline bool cmp(int x,int y) {
    return k[x]<k[y];
}
int vis[1000006];
inline void work() {
    for(int i=1; i<=n; ++i) vis[i]=0;
    for(int i=1; i<=n; ++i) cnt[i]=0;
    n=read();
    for(int i=1; i<=n; ++i) {
        k[i]=read();
        clear(p[i]);
        p[i].resize(k[i]);
        for(int u=0; u<k[i]; ++u) p[i][u]=read();
        a[i]=i;
    }
    sort(a+1,a+n+1,cmp);
    for(int t=1; t<=n; ++t) {
        int i=a[t];
        if(k[i]==0) continue;
        for(int u=0; u<k[i]; ++u) {
            ++cnt[vis[p[i][u]]];
        }
        for(int u=0; u<k[i]; ++u) {
            int g=vis[p[i][u]];
            if(g!=0&&cnt[g]<k[g]&&cnt[g]<k[i]) {
                puts("YES");
                write(i); putchar(' '); write(g); puts("");
                return ;
            }
        }
        for(int u=0; u<k[i]; ++u) {
            --cnt[vis[p[i][u]]];
            vis[p[i][u]]=i;
        }
    }
    puts("NO");
}