Fork me on GitHub

BZOJ3159 决战

BZOJ3159 决战 题解

题意:

  • 给出一棵树,每次支持一个点到根路径上一部分的路径加,路径和,路径最大最小值,路径权值翻转。
  • $1\le n,m\le 5\times 10^4$。

题解:

  • 我并不知道这个路径有啥用?可能方便其他写法?
  • 这种一大堆路径操作,自然可以想到$\rm lct$啦。
  • 然后我发现这种路径翻转,与$\rm lct$自带的翻转非常不能兼容。
  • 于是我们只弄出一棵$\rm splay$维护一条链所有信息是很难的 。
  • 所以我们对于每条链开两棵$\rm splay$,一棵维护形态,一棵维护权值。
  • 具体实现时,就是需要注意两棵$\rm splay$维护的必须是同一条链,也就是形态$\rm splay$重链改变时,也就是$\rm access$时,需要对权值$\rm splay$进行一样的分割合并操作。
  • 注意点主要有:
    • 形态$\rm splay$翻转时,要对权值$\rm splay$进行同样操作。
    • 需要维护一个$size$数组来方便查找对应的节点。
    • 对于两棵对应的$\rm splay$,我们只需要知道形态$\rm splay$的根对应的权值$\rm splay$上的点即可。
    • 每次$\rm access$时,需要通过$size$找到$\rm$$x$对应的节点,并旋转到根,然后两棵$\rm splay$同步分裂。
  • 总复杂度$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
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
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
#include <bits/stdc++.h>
#define gc getchar()
#define ll long long
#define N 50009
using namespace std;
ll n,q,rt;
ll read()
{
ll x=1;
char ch;
while (ch=gc,ch<'0'||ch>'9') if (ch=='-') x=-1;
ll s=ch-'0';
while (ch=gc,ch>='0'&&ch<='9') s=s*10+ch-'0';
return s*x;
}
struct VLCT
{
ll fa[N],ch[N][2],val[N],Min[N],Max[N],sum[N],rev[N],tg[N],size[N];
bool is_root(ll x)
{
return (ch[fa[x]][0]!=x&&ch[fa[x]][1]!=x);
}
void down(ll x)
{
if (!x) return;
if (rev[x]) rever(ch[x][0]),rever(ch[x][1]),rev[x]=0;
if (tg[x]) add(ch[x][0],tg[x]),add(ch[x][1],tg[x]),tg[x]=0;
}
void push_down(ll x)
{
if (!is_root(x)) push_down(fa[x]);
down(x);
}
void up(ll x)
{
sum[x]=Min[x]=Max[x]=val[x],size[x]=1;
if (ch[x][0])
{
sum[x]+=sum[ch[x][0]],size[x]+=size[ch[x][0]];
Min[x]=min(Min[x],Min[ch[x][0]]),Max[x]=max(Max[x],Max[ch[x][0]]);
}
if (ch[x][1])
{
sum[x]+=sum[ch[x][1]],size[x]+=size[ch[x][1]];
Min[x]=min(Min[x],Min[ch[x][1]]),Max[x]=max(Max[x],Max[ch[x][1]]);
}
}
void rotate(ll x)
{
ll y=fa[x],z=fa[y],l=ch[y][1]==x;
if (!is_root(y)) ch[z][ch[z][1]==y]=x;
fa[x]=z,fa[y]=x,fa[ch[x][!l]]=y;
ch[y][l]=ch[x][!l],ch[x][!l]=y;
up(y),up(x);
}
void splay(ll x,ll y=0)
{
for (push_down(x);!is_root(x);rotate(x))
if (!is_root(y=fa[x])) rotate(ch[fa[y]][0]==y^ch[y][0]==x?x:y);
}
void add(ll x,ll z)
{
if (!x) return;
sum[x]+=size[x]*z,val[x]+=z,tg[x]+=z,Max[x]+=z,Min[x]+=z;
}
void rever(ll x)
{
if (!x) return;
rev[x]^=1,swap(ch[x][0],ch[x][1]);
}
ll find_root(ll &x)
{
for (;fa[x];x=fa[x]);
return x;
}
void find(ll &x,ll rk)
{
while (1)
{
down(x);
if (rk<=size[ch[x][0]]) x=ch[x][0];
else if (rk==size[ch[x][0]]+1) return;
else rk-=size[ch[x][0]]+1,x=ch[x][1];
}
}
}val_lct;
ll first[N],number;
struct edge
{
ll to,next;
void add(ll x,ll y)
{
to=y,next=first[x],first[x]=number;
}
}e[N<<1];
struct LCT
{
ll fa[N],ch[N][2],rev[N],size[N],bel[N];
bool is_root(ll x)
{
return (ch[fa[x]][0]!=x&&ch[fa[x]][1]!=x);
}
void down(ll x)
{
if (!x||!rev[x]) return;
rev[x]=0,rever(ch[x][0]),rever(ch[x][1]);
}
ll push_down(ll x)
{
ll ret=!is_root(x)?push_down(fa[x]):x;
down(x);
return ret;
}
void up(ll x)
{
size[x]=1;
if (ch[x][0]) size[x]+=size[ch[x][0]];
if (ch[x][1]) size[x]+=size[ch[x][1]];
}
void rotate(ll x)
{
ll y=fa[x],z=fa[y],l=ch[y][1]==x;
if (!is_root(y)) ch[z][ch[z][1]==y]=x;
fa[x]=z,fa[y]=x,fa[ch[x][!l]]=y;
ch[y][l]=ch[x][!l],ch[x][!l]=y;
up(y),up(x);
}
void rever(ll x)
{
if (!x) return;
rev[x]^=1,swap(ch[x][0],ch[x][1]);
}
void splay(ll x,ll y=0)
{
for (bel[x]=bel[push_down(x)];!is_root(x);rotate(x))
if (!is_root(y=fa[x])) rotate(ch[fa[y]][0]==y^ch[y][0]==x?x:y);
}
void access(ll x)
{
for (ll t=0;x;t=x,x=fa[x])
{
splay(x);
ll xx=val_lct.find_root(bel[x]),tt=val_lct.find_root(bel[t]);
if (!t) tt=0;
val_lct.find(xx,size[ch[x][0]]+1);
val_lct.splay(xx);
bel[x]=xx;
bel[ch[x][1]]=val_lct.ch[xx][1],val_lct.fa[val_lct.ch[xx][1]]=0;
val_lct.ch[xx][1]=tt,val_lct.fa[tt]=xx;
val_lct.up(xx);
ch[x][1]=t;
up(x);
}
}
void make_root(ll x)
{
access(x),splay(x),rever(x),val_lct.rever(bel[x]);
}
void split(ll x,ll y)
{
make_root(x),access(y),splay(y);
}
void dfs(ll x,ll y)
{
fa[x]=y;
for (ll i=first[x];i;i=e[i].next)
if (e[i].to!=y) dfs(e[i].to,x);
}
}lct;
char str[10];
int main()
{
n=read(),q=read(),rt=read();
for (ll i=1;i<=n;i++) lct.bel[i]=i,lct.size[i]=1,val_lct.size[i]=1;
for (ll i=1;i<n;i++)
{
ll x=read(),y=read();
e[++number].add(x,y),e[++number].add(y,x);
}
lct.dfs(rt,0);
while (q--)
{
scanf("%s",str);
ll x=read(),y=read();
lct.split(x,y);
y=val_lct.find_root(lct.bel[y]);
if (str[2]=='c')
{
ll z=read();
val_lct.add(y,z);
}
if (str[0]=='S') printf("%lld\n",val_lct.sum[y]);
if (str[1]=='a') printf("%lld\n",val_lct.Max[y]);
if (str[1]=='i') printf("%lld\n",val_lct.Min[y]);
if (str[2]=='v') val_lct.rever(y);
}
return 0;
}
-------------本文结束感谢您的阅读-------------

本文标题:BZOJ3159 决战

文章作者:wzf2000

发布时间:2018年03月16日 - 07:03

最后更新:2018年03月16日 - 14:03

原始链接:https://wzf2000.github.io/2018/03/16/BZOJ3159/

许可协议: 署名-非商业性使用-禁止演绎 4.0 国际 转载请保留原文链接及作者。