UOJ349 [WC2018]即时战略

题面

http://uoj.ac/problem/349

吐槽

  • 菜到NOIP都卡线的,省选都0分选手人肯定去不了WC,不过反正去了也是划水。

​ 我校神犇周yyLCT的做法秒掉此题之后说LCTLCT常数太大他被hack了。

​ 于是老老实实看题解写动态点分治。

​ 然后纠结为什么大家的点分治(包括网上据大多数题解)使用的size都是上一层getroot得到的,非常的假。然后往UOJ交流群上一丢,就知道答案了:竟然还有这种黑科技?,虽然看不懂,但听说这个复杂度是对的。实测常数还小。


Solution

​ 一个显然的想法是链单独考虑。

​ 先不考虑链具体做法是,你没插入一个点,在点分树上查询是在哪个儿子(这个可以直接explore之后暴力跳father),时间复杂度log^2,我们可以在一只log的查询内找到这个点和点分树连出去的那个叶子。

如图

​ 如果上面这个是原树的话,先找到那个红色的框,然后一路查询下去得到一条链。

​ 然后这个复杂度很快会伪掉,因此需要动态维护。此处可以类似SGT的做法,设一个平衡因子,当不平衡的时候整颗暴力重构。

  • 链的化直接L和R搞一下就行了。
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
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
#include<bits/stdc++.h>
#include "rts.h"
#define mem(x,v) memset(x,v,sizeof(x))
using namespace std;
const int maxn = 300005;
int m,root;
int id[maxn],fa[maxn];
bool discover[maxn];
vector<int> edge[maxn];
void add(int a,int b){
fa[b] = a;
edge[a] . push_back(b);
edge[b] . push_back(a);
}
int size[maxn],mx[maxn],sum,rt=0;
int Osz[maxn];//点分树的子树大小
bool vis[maxn];
void getrt(int u,int fa){
size[u] = 1;
mx[u] = 0;
for(auto v : edge[u]){
if(v == fa || vis[v]) continue;
getrt(v,u);
size[u] += size[v];
mx[u] = max(mx[u],size[v]);
}
mx[u] = max(mx[u],sum - size[u]);
if(mx[u] < mx[rt]) rt = u;
}
int getsize(int u,int fa){
int cnt = 1;
for(auto v : edge[u]){
if(vis[v] || v==fa) continue;
cnt+=getsize(v,u);
}
return cnt;
}//此段可以直接去掉,同时修改下面一处
void divide(int u){
vis[u] = true;
Osz[u]=1;
for(auto v : edge[u]){
if(vis[v]) continue;
sum = getsize(v,u);
//可以把这个改成size[v],原因上面有写
rt = 0;
getrt(v,u);
int __rt = rt;
fa[rt] = u;
divide(rt);
Osz[u] += Osz[__rt];
}
vis[u] = false;
}
vector<int> V;
bool mark[maxn];
void tour(int u,int fa){//遍历得到所有点
V.push_back(u);
for(auto v : edge[u]){
if(vis[v] || v==fa) continue;
tour(v,u);
}
}
void rebuild(int last){//暴力重构
for(int i = fa[last];i;i = fa[i]) vis[i] = true;
V.clear();
tour(last,0);
int ppp = fa[last];
for(auto i:V) fa[i]=0,Osz[i]=0;
rt = 0;sum = V.size();
getrt(last,fa[last]);
int __rt =rt;
divide(rt);
fa[__rt] = ppp;
if(last == root) root = __rt;
for(int i = fa[last];i;i = fa[i]) vis[i] = false;
}
#define alpha 0.7//平衡因子
void solve(int q){
int u = root,v;
while(discover[v = explore(u,q)]){
while(fa[v] != u){
v = fa[v];
}
u = v;
}//找到那个相连的叶子
int _u = u;
add(u,v);u = v;discover[v]=true;
while(v!=q){
v = explore(u,q);
add(u,v);
discover[v] = true;
u = v;
}//剩下一条链,先全部加入
int x,y;
x = v;y = 0;
while(x!=_u){
Osz[x] += ++y;
x = fa[x];
}//修改size,下面是递增,上面都一样
while(x){
Osz[x] += y;
x = fa[x];
}
y = v,x = fa[v];
int last = 0;
while(x){
if(Osz[x] * alpha <= Osz[y]) last = x;
x=fa[x],y=fa[y];
}//找到最上面的不平衡的点
if(last){
rebuild(last);
}
}
void play(int n,int T,int dataType){
srand(time(NULL));
for(int i=2;i<=n;i++) id[i] = i;
random_shuffle(id+2,id+1+n);//随机得到下一个应该选的
if(dataType==3){
mem(vis,false);
int L=1,R=1; vis[1]=1;
for(int i=2;i<=n;i++)if(!vis[id[i]]){
int x=explore(L,id[i]);
if(vis[x])x=R,R=id[i];
else L=id[i],vis[x]=1;
while(x!=id[i])vis[x=explore(x,id[i])]=1;
}
return;
}//链的特判
mx[0]=n;
mem(discover,false);discover[1] = true;
fa[1] = 0;
root = 1;
for(int i=2;i<=n;i++){
if(!discover[id[i]]){
solve(id[i]);
}
}
}

调了一个下午

文章目录
  1. 1. 题面
  2. 2. 吐槽
  • Solution