BZOJ 2851 极限满月

Link

Solution

非常神奇的思路。 每个集合\(B_k\)的元素一定是\(\le k\)的数字。这些数字,是几个集合求交的得到的。一切集合追溯到本源,都来源于虚无(\(\emptyset\))。如果把每个集合抽象成到\(\emptyset\)的路径,每个集合的构造过程就是几条路径的并集,加上一个新点。这是一个树结构,然后就可以通过LCA实现求交,通过DFS序实现求并集的大小。 # Tips 集合交:路径交 集合并:路径并 # Code

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
#include "lucida"
import swap;
import sort;
const int MAXN=200000+11,MAXLOG=20;//儮儈儈儈儈儈
int log_2[MAXN];
struct _{_() {
log_2[0]=-1;
for(int i=1;i<MAXN;++i) {
log_2[i]=log_2[i>>1]+1;
}
}}Auto;
struct Edge {
int to;Edge *pre;
Edge(int to,Edge *pre):to(to),pre(pre) {}
void *operator new(size_t) {
static Edge *Me=alloc(Edge,MAXN);
return Me++;
}
}*G[MAXN];
void Adde(int f,int t) {
G[f]=new Edge(t,G[f]);
}
int par[MAXN][MAXLOG],dep[MAXN];
void Link(int pos,int fa) {
Adde(fa,pos);
par[pos][0]=fa;
dep[pos]=dep[fa]+1;
for(int lg=1;lg<=log_2[dep[pos]];++lg) {
par[pos][lg]=par[par[pos][lg-1]][lg-1];
}
}
int LCA(int p1,int p2) {
if (dep[p1]<dep[p2]) {
swap(p1,p2);
}
for(int len=dep[p1]-dep[p2],lg=log_2[len];~lg;--lg) if(len>>lg&1) {
p1=par[p1][lg];
}
if(p1!=p2) {
for(int lg=log_2[dep[p1]];~lg;--lg) if(par[p1][lg]!=par[p2][lg]) {
p1=par[p1][lg];
p2=par[p2][lg];
}
p1=par[p1][0];
}
return p1;
}
int dfn[MAXN],dc;
void DFS(int pos) {
dfn[pos]=++dc;
for(Edge *e=G[pos];e;e=e->pre) {
int u=e->to;
DFS(u);
}
}
bool cmpDFN(const int &p1,const int &p2) {
return dfn[p1]<dfn[p2];
}
int main() {
// freopen("input","r",stdin);
//A_i 的元素都比i小
//B_k 最大的元素一定是k
int n;is>>n;
for(int i=1;i<=n;++i) {
int lca=-1,cnt;is>>cnt;
for(int j=1;j<=cnt;++j) {
int x;is>>x;
lca=lca==-1?x:LCA(x,lca);
}
Link(i,lca=lca==-1?0:lca);
}
DFS(0);
int Q;is>>Q;
for(int rep=1;rep<=Q;++rep) {
int cnt;is>>cnt;
static int x[MAXN];
for(int i=1;i<=cnt;++i) {
is>>x[i];
}
sort(x+1,x+1+cnt,cmpDFN);
int Ans=0;
for(int i=1;i<=cnt-1;++i) {
Ans+=dep[x[i]]-dep[LCA(x[i],x[i+1])];
}
Ans+=dep[x[cnt]];
os<<Ans<<'\n';
}
return 0;
}

Powered by Hexo and Hexo-theme-hiker

Copyright © 2013 - 2017 Hey,Lucida here. All Rights Reserved.

Lucida Lu 保留所有权利