自动搬运

查看原文

来自洛谷，原作者为

	Limitless_lmw 因为我的羽翼，是为你而生的！

搬运于2025-08-24 21:14:28，当前版本为作者最后更新于2023-01-18 17:37:47，作者可能在搬运后再次修改，您可在原文处查看最新版

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

以下是正文

建议先阅读扶苏的bitset浅谈

本文主要描述如何实现题目中所述操作。

我们用一个 bitset<30005> 的第 $i$ 位是 $0/1$ 表示存在/不存在。

那么我们一个一个操作来看：

操作 $1$:

我们观察一个序列 1 3 5 9 在一个 bitset<15> 中的映射：000000100010101

再观察这个序列所有元素都加上 $6$ 之后的映射：100010101000000

你发现了什么？

对，就是左移，所以操作 $1$，就是左移这个 bitset。

你是不是以为，我们建一个 bitset<m>，然后左移之后超出去的部分就为自动删掉？

这里有一个坑点：bitset<N> 中的 $N$ 必须为一个编译期常数，那么这里的 $m$ 显然在输入了之后不是一个编译期常数，那么就不能 bitset<m>，怎么办？

我们可以给另一个 bitset<30005> 的 $1\sim m$ 位都赋为 $1$，剩余的位 $0$，那么在左移之后，我们就用左移了的这个 bitset 与上后一个 bitset，就能起到将不在 $[1,m]$ 内的元素删除的作用。

操作 $2$:

相对操作 $1$ 就简单了，因为操作 $2$ 中的右移出了 $0$ 之后会自动删除，那么直接左移即可。

操作 $3$:

交集是由同时在两个集合中的元素构成的，那么这恰好符合哪种位运算？——与运算 &。

所以操作 $3$ 就是 S[x]&S[y]。

操作 $4$:

同理可得，并集是由在任意一个集合中的元素构成的，那么这就是或运算 |，操作 $4$ 便是 S[x]|S[y]。

操作 $5$:

对称差是由只在其中一个集合的元素构成的，那么这就是异或运算 ^，得操作 $5$ 为 S[x]^S[y]。

Tip: 如果不知道异或是什么的，记住：若两个布尔值相等，则它们的异或值为 $0$，反之为 $1$。

至此，你就可以利用 STL AC 一道黄题了。

附代码：

#include <bitset>
#include <vector>
#include <iostream>

const int maxn=30005;
int n,m,q;
std::bitset<maxn> s[maxn];

int main(){
    std::ios::sync_with_stdio(false);
    std::cin.tie(nullptr);
    std::cin>>n>>m>>q;
    for(int i = 1,c,x;i<=n; i++){
        for(std::cin>>c;c;--c){
            std::cin>>x;
            s[i].set(x-1,1);
        }
    }
    for(int i = 0; i<m; i++) s[0].set(i,1);
    for(int o,x,y;q;--q){
        std::cin>>o>>x>>y;
        if(o==1){
            s[x]<<=y;
            s[x]&=s[0];
        }else if(o==2){
            s[x]>>=y;
        }else if(o==3){
            std::cout<<(s[x]&s[y]).count()<<'\n';
        }else if(o==4){
            std::cout<<(s[x]|s[y]).count()<<'\n';
        }else if(o==5){
            std::cout<<(s[x]^s[y]).count()<<'\n';
        }
    }
    return 0;
}