【FZU2020 J】集合并 题解

OI/XCPC Comments

题目大意

  对于集合 $a$，定义集合 $S(a)$ 表示集合 $a$ 生成的集合，生成方式为通过以下步骤任意多次：

  • 初始，$S(a)=a$；
  • 若存在 $x,y \in S(a)$，但是 $x\oplus y \not \in S(a)$，将其插入到 $S(a)$ 中。

  现在给定集合 $a,b$，你需要维护一个数据结构，支持以下操作，共 $m$ 次：

  • $1\ x$，表示插入 $x$ 到集合 $a$ 中，保证插入之前 $x \not\in a$
  • $2\ x$，表示插入 $x$ 到集合 $b$ 中，保证插入之前 $x \not\in b$
  • $3\ x$，表示从集合 $a$ 中删除元素 $x$，保证删除之前 $x \in a$
  • $4\ x$，表示从集合 $b$ 中删除元素 $x$，保证删除之前 $x \in b$
  • $5$，表示询问：输出 $|S(a) \cup S(b)| \bmod 998244353$​，即集合并的元素个数

  
  $|a|,|b| \le 10^5,\ \ m \leq 2\times 10^5$，所有的集合元素 $\in [0,2^{63})$
  多测，时限比较迷。。反正 $O(n \log^2 x)$ 跑不过

题解

  首先，这个 $S(a)$、$S(b)$ 肯定是考虑维护其线性基了。
  这里要用到带删除的线性基，删除有在线和离线两种方式，在线是真正地实现删除操作，看这里学一学；离线是计算出每个元素的过期时间，然后线性基插入操作的时候用更新式的插入法，保持基元都是最新的，参考这题。

  然后看怎么计算答案。容斥一下有 $ans=|S(a)|+|S(b)|-|S(a) \cap S(b)|$，那怎么算 $|S(a) \cap S(b)|$ 呢？
  可以想到两种方法，一是直接求交，拿 $S(a)$ 的每个基元放到 $S(b)$ 里去看看能不能被表示出来，能就说明它是 $S(a)$ 和 $S(b)$ 交空间的基。（qaq为啥我觉得一点都不显然啊） 但这样是 $O(m \log^2 x)$ 的，被卡掉了。
  第二种方法是再容斥一下，$S(a) \cap S(b)$ 的基元个数 = $S(a)$ 基元个数 + $S(b)$ 基元个数 - $S(a \cup b)$ 基元个数。（qaq这个也很不显然啊为啥你们就觉得显然了啊） 于是这样就只需要维护三个线性基：$S(a)$、$S(b)$、$S(a) \cup S(b)=S(a\cup b)$，就变成 $O(m \log x)$ 的了。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
#include<cstdio>
#include<cstring>
#include<map>
#include<iostream>
#define fo(i,a,b) for(int i=a;i<=b;i++)
#define fd(i,a,b) for(int i=a;i>=b;i--)
using namespace std;

typedef long long LL;
typedef unsigned long long ULL;
typedef pair<ULL,int> pr;

const int maxop=5e5+5, MX=62;
const int inf=1e9;
const LL mo=998244353;

struct OP{
	ULL x;
	bool ab,ty;
	int endt,t;
};

int n,m,q,op0;
OP op[maxop];
map<ULL,int> Sa,Sb;

pr Ba[MX+2],Bb[MX+2],Bab[MX+2];
void add(pr *B,pr x)
{
	fd(i,MX,0) if ((x.first>>i)&1)
	{
		if (B[i].first)
		{
			if (B[i].second<x.second) swap(B[i],x);
			x.first^=B[i].first;
			if (!x.first) break;
		} else
		{
			B[i]=x;
			break;
		}
	}
}
int qry(pr *B,int endt)
{
	int cnt=0;
	fo(i,0,MX) cnt+=(B[i].first>0 && B[i].second>endt);
	return cnt;
}

LL er[MX+5];
int main()
{
	er[0]=1;
	fo(i,1,MX+2) er[i]=(er[i-1]<<1)%mo;
	
	while (scanf("%d %d",&n,&m)!=EOF)
	{
		Sa.clear();
		Sb.clear();
		op0=0;
		fo(i,1,n)
		{
			ULL x;
			scanf("%llu",&x);
			op[++op0]=(OP){x,0,0,inf,i};
			Sa[x]=op0;
		}
		fo(i,1,m)
		{
			ULL x;
			scanf("%llu",&x);
			op[++op0]=(OP){x,1,0,inf,n+i};
			Sb[x]=op0;
		}
		scanf("%d",&q);
		fo(i,1,q)
		{
			int ty; ULL x;
			scanf("%d",&ty);
			if (ty<=4) scanf("%llu",&x);
			if (ty==1)
			{
				op[++op0]=(OP){x,0,0,inf,n+m+i};
				Sa[x]=op0;
			} else if (ty==2)
			{
				op[++op0]=(OP){x,1,0,inf,n+m+i};
				Sb[x]=op0;
			} else if (ty==3)
			{
				op[Sa[x]].endt=n+m+i;
			} else if (ty==4)
			{
				op[Sb[x]].endt=n+m+i;
			} else
			{
				op[++op0]=(OP){0,0,1,0,n+m+i};
			}
		}
		
		fo(i,0,MX) Ba[i]=Bb[i]=Bab[i]=pr(0,0);
		fo(i,1,op0) if (!op[i].ty)
		{
			if (op[i].ab==0) add(Ba,make_pair(op[i].x,op[i].endt));
				else add(Bb,make_pair(op[i].x,op[i].endt));
			add(Bab,make_pair(op[i].x,op[i].endt));
		} else
		{
			int x=qry(Ba,op[i].t), y=qry(Bb,op[i].t), z=qry(Bab,op[i].t);
			LL ans=((er[x]+er[y]-er[x+y-z])%mo+mo)%mo;
			printf("%lld\n",ans);
		}
	}
}

kqpOIACMer / HKU_CS / LLer / TCS

糖少许，盐少许