「BalticOI 2021 Day1」Inside information

Posted on Edited on In

「BalticOI 2021 Day1」Inside information

题目大意

有 \(n\) 个集合 \(S_i\) ，一开始 \(S_i=\{i\}\)。

执行 \(m\) 个操作：

  1. 选择 \(u,v\) ，令 \(S_u,S_v:=S_u\cup S_v\)。
  2. 对于 \(u,x\)，回答 \([x\in S_u]\)。
  3. 对于 \(x\)，回答 \(\sum_i [x\in S_i]\)。

保证操作 \(1\) 恰好出现 \(n-1\) 次，且所有边 \((u,v)\) 构成一棵树。

分析

题目保证或操作构成一棵树，考虑一个熟悉的问题：

每次选择两个点连边，维护连通块中的点集。

用并查集+线段树合并处理。

在这道题中，点之间的关系无法用并查集处理，但依然可以考虑线段树合并。

容易发现，每次被合并的树 \(tree_u,tree_v\)，它们的节点集合都是 \(block_u,block_v\) 的子集，其中 \(block_u\) 表示 \(u\) 所在连通块的点集。

而由上面的提到的经典问题，我们知道合并 \(block_u,block_v\) 的线段树合并复杂度为 \(O(n\log n)\)。

而合并 \(tree_u,tree_v\) 的线段树合并复杂度不高于合并 \(block_u,block_v\)，因此不高于 \(O(n\log n)\)。

因此 \(2\) 操作可以直接用线段树合并处理，由于一棵树可能被合并多次，需要进行可持久化操作。

对于第二个问题，考虑合并的关系构成一个 \(\text{DAG}\)，每次合并会新建一个 \(\text{DAG}\) 节点，\(3\) 操作的答案就是当前节点在 \(\text{DAG}\) 反图上可达的节点数目。

容易发现在反图上用线段树合并维护可达点集的复杂度分析与正向的合并相同，而查询当前时刻的节点数量，可以改为查询编号 \(\leq i\) 的节点数量，其中 \(i\) 表示在查询时的编号最大的 \(\text{DAG}\) 节点。

只需要进行正反两次可持久化线段树合并，复杂度为 \(O(n\log n)\)。

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
bool Mbe;
const int N=1.2e5+10,M=N*40,INF=1e9+10;

int n,m;
int rt[N*2],ls[M],rs[M],s[M],cnt;
void Ins(int &p,int l,int r,int x){
	p=++cnt,s[p]=1;
	if(l==r) return;
	int mid=(l+r)>>1;
	x<=mid?Ins(ls[p],l,mid,x):Ins(rs[p],mid+1,r,x);
}
int Union(int x,int y) {
	if(!x || !y) return x|y;
	int u=++cnt;
	ls[u]=Union(ls[x],ls[y]);
	rs[u]=Union(rs[x],rs[y]);
	s[u]=s[x]+s[y];
	return u;
}
int Que(int p,int l,int r,int x){
	if(!p) return 0;
	if(l==r) return 1;
	int mid=(l+r)>>1;
	return x<=mid?Que(ls[p],l,mid,x):Que(rs[p],mid+1,r,x);
}
int Que(int p,int l,int r,int ql,int qr) {
	if(!p || ql>qr) return 0;
	if(ql<=l && r<=qr) return s[p];
	int mid=(l+r)>>1,res=0;
	if(ql<=mid) res+=Que(ls[p],l,mid,ql,qr);
	if(qr>mid) res+=Que(rs[p],mid+1,r,ql,qr);
	return res;
}

char op[3];
int I[N],J[N];
vector <int> G[N*2];
int QX[N],QY[N];

bool Med;
int main() {
	n=rd(),m=rd()+n-1;
	rep(i,1,n) Ins(rt[i],1,n,i),J[i]=i;
	int c=0,t=n;
	rep(i,1,m) {
		scanf("%s",op);
		if(*op=='S') {
			int a=rd(),b=rd();
			++t;
			if(!I[a]) I[a]=t;
			else G[J[a]].pb(t);
			if(!I[b]) I[b]=t;
			else G[J[b]].pb(t);
			rt[t]=Union(rt[J[a]],rt[J[b]]);
			J[a]=J[b]=t;
		} else if(*op=='Q') {
			int a=J[rd()],b=rd();
			QX[++c]=-Que(rt[a],1,n,b);
		} else {
			QX[++c]=rd(),QY[c]=t;
		}
	}
	rep(i,1,::cnt) ls[i]=rs[i]=s[i]=0;
	cnt=0;
	drep(i,n*2-1,n+1) {
		int u=i-n;
		Ins(rt[u],1,n,u);
		for(int j:G[i]) {
			int v=j-n;
			rt[u]=Union(rt[u],rt[v]);
		}
	}
	rep(i,1,c) {
		if(QX[i]<=0) puts(QX[i]?"yes":"no");
		else printf("%d\n",Que(rt[I[QX[i]]-n],1,n,1,QY[i]-n)+1);
	}
}