我预感到以考代练的模式会让我这个罗马数字的标号特别丑陋……
另外 T2 是道模拟，就不写了
# 题面
A. 监控中心 center
给出一个 $n$ 个点，$m$ 条边的连通图。对一些点作标记。当所有作标记操作结束后，对于一个被做了标记的点 $u$，与它相邻的没有标记的点 $v$ 会“报告”信息 v->u。
输入 $n,m$ 和一个图，第 $i$ 条边的表示方式是 E[i][0],E[i][1]，即 E[i][0] 和 E[i][1] 之间有边。
现在进行 $Q$ 组询问，每组询问独立。一个询问的内容如下：给出 $k$ 条“报告”信息，一条信息的表述方式是 id——若 id<0 则报告为 E[-id][1]->E[-id][0]；若 id>0 则为 E[id][0]->E[id][1]。
对于每个询问，计算出有多少个点被标记。（保证输入的信息合法）
数据规模： $1\le n\le10^6$，$n-1\le m\le 2.5\times 10^6$，$Q,\sum k\le 10^6$
给出 $m$ 个数组 $A_1$ 到 $A_m$，其中 $A_i$ 大小为 $n_i$。将 $A_i$ 和 $A_j$ 拼成一个数组 $S_{i,j}$，则 $f(i,j)$ 表示 $S_{i,j}$ 的第 $\left\lfloor\frac{n_i+n_j+1}{2}\right\rfloor$ 大的数。
对于每个 $u\in[1,m]$ 求：
数据规模： $m\le 10^4$，$n_i\le500$，数组元素在 $0$ 到 $10^9$ 之间。
# 解析
A. 监控中心 center
我们把信息看成一条条的有向边，那么被有向边围在内侧的点就是被标记的。比如：
Tab. 橙色的点就是被有向边围起来的，也就是被标记的点。
我们把图中所有的有向边都删去，那么原图就变成了一个个的块。
那么我们从简单的情况——树，来考虑。对于一棵树，有向边无非两种情况：
- 从父亲 $u$ 指向儿子 $v$：这说明 $v$ 所在的块 被围起来了；
- 从儿子 $v$ 指向父亲 $u$：说明 $v$ 所在的块 没有被围起来；
怎么计算被围起来的块的大小？
比如上图这个例子，当出现①这个有向边时，把 U 的子树大小加上，出现 ② 时就把 V 的子树大小减去。
总结一下就是：
- 从父亲 $u$ 指向儿子 $v$：加上子树 $v$ 的大小
- 从儿子 $v$ 指向父亲 $u$：减去子树 $v$ 的大小
但是有个 Bug，根节点没法统计到，因为根节点如果有标记，也不可能有从“根的父亲”指向根的边。
这个也有解决方法，此时我们计算出的答案会<0，于是如果最后算出来答案小于0，就直接把整棵树加上（+=n）就好了。
怎么处理一般的图？我们发现，因为输入是合法的，我们只需要原图的一棵生成树就可以判断哪些点被标记。因此随便生成一棵树，再用树的方法做就好了。
首先把所有数组排序。
考虑当数组 $A$ 和 $B$ 拼起来时，$A$ 中的元素 $a_i$ 成为中位数的条件。设 $A,B$ 的大小分别为 $s,t$，且存在 $k$ 使得 $b_k\le a_i\le b_{k+1}$。
$a_j$ 成为中位数的条件就是 $i+j=\lfloor\frac{s+t+1}{2}\rfloor$。
- $s,t$ 奇偶性相同：$i+j=\frac{s+t}2$，整理可得 $(2i-s)+(2j-t)=0$；
- $s,t$ 奇偶性不同：$i+j=\frac{s+t+1}2$，整理可得 $(2i-s)+(2j-t)=1$；
于是可以将所有数组拼起来得到一个大小为 $\sum n_i$ 的数组 $S$，然后把 $S$ 排序。
从小到大枚举 $S$ 中的元素 $x$。
设 $x$ 原来是 $A_i$ 的第 $p$ 个元素；如果 $A_i$ 能与 $A_j$ 拼起来使得 $x$ 成为中位数，设 $A_j$ 中的第 $q$ 个元素 $A_j$ 中比 $x$ 小的最大数，则 $p+q=\lfloor\frac{n_i+n_j+1}2\rfloor$，即 $2q-n_j=n_i-2p$ 或 $2q-n_j=1+n_i-2p$。
由于是从小到大枚举的元素，那么 $p,q$ 是非常好维护的，关键是如何找满足条件的 $A_j$。于是想到可以维护——定义 $A_j$ 的特征值 $P_j$ 是 $n_j-2q$（$q$ 这里是一直维护的），那么我们可以随时维护这个特征值，同时维护对于一个特征值 $P’$，有哪些数组的特征值是 $P’$。
维护这个信息需要支持随时插入删除一个指定元素——链表！
那么枚举到 $x$ 时，我们只要找特征值为 $P_j=-P_i$ 或 $P_j=1-P_i$ 的 $A_j$ 就好了。
由于合法的情况是 $O(m^2)$ 个（即数组两两之间可以产生一个合法的情况），所以这样维护并且暴力枚举的方法是 $O(m^2)$ 的~
# 源代码
A. center.cpp
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
|
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
const int N=1e6,M=2500000;
int n,m;
struct GRAPH{
int to[M*2+3],nxt[M*2+3],head[N+3],ncnt;
void AddEdge(int u,int v){
int p=++ncnt,q=++ncnt;
to[p]=v;nxt[p]=head[u];head[u]=p;
to[q]=u;nxt[q]=head[v];head[v]=q;
}
int operator [](int id){return head[id];}
}Tr;
struct DSU{
int fa[N+3];
void Init(int exn){
for(int i=1;i<=exn;i++)
fa[i]=i;
}
int FindFa(int u){return fa[u]=(u==fa[u]? u:FindFa(fa[u]));}
bool Merge(int u,int v){
int fu=FindFa(u),fv=FindFa(v);
if(fu==fv) return false;
fa[fu]=fv;
return true;
}
}Ds;
int edg[M+3][2];
int dep[N+3],siz[N+3];
int RI(){
int a=0,b=1,c=getchar();
while(c<'0' || '9'<c){
b=c=='-'? -1:b;
c=getchar();
}
while('0'<=c && c<='9'){
a=(a<<1)+(a<<3)+c-'0';
c=getchar();
}
return a*b;
}
void DFS(int u,int fa){
siz[u]=1;dep[u]=dep[fa]+1;
for(int it=Tr[u];it;it=Tr.nxt[it]){
int v=Tr.to[it];
if(v==fa) continue;
DFS(v,u);
siz[u]+=siz[v];
}
}
int main(){
freopen("center.in","r",stdin);
freopen("center.out","w",stdout);
n=RI();m=RI();
for(int i=1;i<=m;i++)
edg[i][0]=RI(),edg[i][1]=RI();
Ds.Init(n);
for(int i=1;i<=m;i++)
if(Ds.Merge(edg[i][0],edg[i][1]))
Tr.AddEdge(edg[i][0],edg[i][1]);
else
edg[i][0]=edg[i][1]=0;
DFS(1,0);
int cas=RI();
while(cas--){
int ans=0,k=RI();
for(int i=1;i<=k;i++){
int id=RI(),u,v;
if(id>0) u=edg[id][0],v=edg[id][1];
else u=edg[-id][1],v=edg[-id][0];
if(dep[u]>dep[v]) ans-=siz[u];
else ans+=siz[v];
}
if(ans<0) ans+=n;
printf("%d\n",ans);
}
return 0;
}
|
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
|
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
const int M=1e4,N=500;
int m,totn;
int n[M+3],sp[M+3];
pair<int,int> val[N*M+3];
struct LIST{
int lef[M*2+3],rig[M*2+3],bel[M*2+3],head[2*N+3];
void Insert(int now,int id){
int nxt=head[id];
head[id]=now;
lef[now]=0;
rig[now]=nxt;
if(nxt) lef[nxt]=now;
bel[now]=id;
}
void Delete(int now){
if(head[bel[now]]==now) head[bel[now]]=rig[now];
if(rig[now]) lef[rig[now]]=lef[now];
if(lef[now]) rig[lef[now]]=rig[now];
}
}Li;
int ans[M+3];
int main(){
freopen("median.in","r",stdin);
freopen("median.out","w",stdout);
scanf("%d",&m);
for(int i=1;i<=m;i++){
scanf("%d",&n[i]);
for(int j=1,inp;j<=n[i];j++){
scanf("%d",&inp);
val[++totn]=make_pair(inp,i);
}
sp[i]=-n[i];
Li.Insert(i,N+sp[i]);
}
sort(val+1,val+totn+1);
for(int i=1;i<=totn;i++){
int bel=val[i].second,num=val[i].first;
Li.Delete(bel);sp[bel]+=2;
if(sp[bel]==0 || sp[bel]==1) ans[bel]^=(num+bel+bel);
for(int it=Li.head[N-sp[bel]];it;it=Li.rig[it])
ans[bel]^=(num+it+bel),ans[it]^=(num+it+bel);
for(int it=Li.head[N+1-sp[bel]];it;it=Li.rig[it])
ans[bel]^=(num+it+bel),ans[it]^=(num+it+bel);
Li.Insert(bel,N+sp[bel]);
}
for(int i=1;i<=m;i++)
printf("%d\n",ans[i]);
return 0;
}
|
THE END
Thanks for reading!