uoj55 紫荆花之恋

Link

Solution

嗯。做法来自Po姐。 >紫荆花之恋。我在WC 2014中出的题目,这个题目的核心在于可以意识到替罪羊树这一技巧,能够适用于一切依靠子树大小来维持平衡的结构。那么,它必然也可以被使用于点分治这一结构。那么我们就可以用替罪羊树来维护动态的点分治。当时觉得还挺有意思的,不过现在也已经不怎么研究数据结构了>_>。 –WJMZBMR

支持加点,实时维护\(dis(i,j)\le r_i+r_j\)的点对数目。 考虑不是动态加点的做法。 (口胡begin) 对树点分治,重心为\(p\)的一层内,问题变成\(dis(i,p)+dis(j,p)\le r_i+r_j\),即\(dis(i,p)-r_i \le r_j-dis(j,p)\) 维护一个有序的数组\(a[]=\{dis(i,p)-r_i\}\),对于一个新分支,求出\(b[]=\{r_j-dis(j,p)\}\)。用双指针统计答案,然后把\(b[]\)取反,将两个表\(std::merge\)。 (如果我说的有问题欢迎指教。。) (口胡end) 加点的话,要想办法统计一个新的点对答案的贡献,即以从它一直到根节点为LCA的所有合法路径。这样,在每个重心处维护一个\(Treap\)维护\(r_i-dis(i,p)\),然后查询值\(dis(j,p)-r_j\)在其中的排名即可。 然后复杂度会爆棚,于是借助替罪羊思想,如果一个点点分出来的某个分支的size过大,就重新点分治这棵子树。 # Tips * 在以\(p\)为重心的一层统计答案的时候要减去LCA不是\(p\)的点对。一开始想的是减去以\(p\)的子节点为LCA的路径,,然后发现不一定只有这样的不合法。。于是不可避免地要开两棵\(Treap\),设\(p\)分出的一棵子树为\(u\)\(u\)的另一棵记录的是\(p\)\(u\)内产生的\(r_i-dis(i,p)\)。由此,统计答案的时候直接减去即可。 * 在重新分治的时候要把\(Treap\)重新赋值,用filltreap()实现。一开始这个函数的Treap::Insert()操作写在了遍历边的循环里,结果最顶上的点的值没有Insert()进去。。 * TreapNode::cnt++之后,没有立即\(TreapNode::up()\) * 维护点分出来的分支的时候只能用平衡树,因为涉及节点的查找和删除操作。 * 千万不要把原树的father和点分分支的uplayer混淆。 * 点分中各种操作都严禁跑出当前一层的点集。 * 一开始的时候std::queue出了问题,调试的时候在那里挂掉。然后还真的研究了很长时间queue的问题。然而弃疗之后发现某个细节写错了,改了之后立即好了。。由此,崩溃的位置不一定是bug的位置。。 * 在Rebuild中,一开始我的filltreap(DyNode::anti)是写在遍历边的循环里的,结果和上面的一样,最顶上的点没有把anti赋值。 * 于是学习Po姐的代码,发现在Rebuild之前可以直接保留这棵子树的anti,因为anti不会随着树的结构改变。于是开心地效仿了,发现立即崩溃。研究了好久才顿悟——在Rebuild之前有垃圾回收,里面的TreapNode等同于已经被析构了,再调用必死啊。还是语言逻辑不好啊。。 * 于是又把代码改成在每层的一开始处理本层的anti,结果崩。苦想,明白了问题:Rebuild(pos)pos我传的是替罪羊树中的节点编号。它和它的上一层不一定是父子关系。这样filltreap的值就是错的。所以pos应该传这棵子树在原树上的节点编号。 * 倍增LCA支持动态加点操作。 * 替罪羊树只需检测每次加了点的分支。 * 一开始T了,加了fread优化T的更厉害,然后加了fwrite优化,调整了替罪羊树的\(\alpha\)值,才卡过去。如果看出我的代码复杂度写错,或者有常数的缺陷,欢迎指教。看到BZOJ上%jvcb%跑的那么快简直BUG一样。 upd:发现替罪羊树写错了,改过来之后T飞了,然后有各种卡常数改\(\alpha\),结果最后发现是点分治写错了。太愚蠢了。 # 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
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
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
326
327
328
329
330
331
332
333
334
335
336
337
338
339
340
341
342
343
344
345
346
347
//Code by Lucida
#include<bits/stdc++.h>
//#define red(x) scanf("%d",&x)
#define debug(x) printf(#x"=%d\n",x)
template <class T> inline bool chkmx(T &a,const T &b){return a<b?a=b,1:0;}
template <class T> inline bool chkmn(T &a,const T &b){return a>b?a=b,1:0;}
typedef long long LL;
using std::swap;
using std::queue;
using std::set;
const int MAXN=1e5+100,P=1e7;
LL last=0;int r[MAXN];
//IO begin
const int INBUF=1e7;
char inbuf[INBUF],*iptr=inbuf,*iptrend=inbuf;
#define getc() (iptr==iptrend && (iptrend=(iptr=inbuf)+fread(inbuf,1,INBUF,stdin),iptr==iptrend)?EOF:*iptr++)
inline void red(int &x)
{
static int flag;
static char ch;
flag=1;
while(!isdigit(ch=getc())) if(ch=='-') flag=-1;
x=ch-'0';
while(isdigit(ch=getc()))
(x*=10)+=ch-'0';
x*=flag;
}
const int OUTBUF=1e7;
char outbuf[OUTBUF],*optr=outbuf;
inline void white(LL x)
{
if(x<0) *optr++='-';
if(x==0) *optr++='0';
if(x)
{
static char stack[100],*top;
for(top=stack;x;x/=10)
*top++=(x%10)+'0';
while(top!=stack)
*optr++=*--top;
}
*optr++='\n';
}
//IO end
//LCA begin
namespace fullgraph
{
const int LOG=20;
struct Edge{int to,v,pre;}e[MAXN<<1];int id[MAXN],ec=0;
inline void Adde(int f,int t,int v)
{
if(!f || !t) return;//1 0...
e[++ec].to=t;e[ec].v=v;e[ec].pre=id[f];id[f]=ec;
e[++ec].to=f;e[ec].v=v;e[ec].pre=id[t];id[t]=ec;
}
int dep[MAXN],dis[MAXN],fa[MAXN][LOG];
}
inline void AddNode(int pos,int father,int c)
{
using namespace fullgraph;
fa[pos][0]=father;
for(int j=1;j<=LOG-1;j++)
fa[pos][j]=fa[fa[pos][j-1]][j-1];
dep[pos]=dep[father]+1;
dis[pos]=dis[father]+c;
Adde(pos,father,c);
}
inline int LCA(int p1,int p2)
{
using namespace fullgraph;
if(dep[p1]<dep[p2]) swap(p1,p2);
for(int j=LOG-1;~j;j--)
if(dep[fa[p1][j]]>=dep[p2]) p1=fa[p1][j];
if(p1==p2) return p1;
for(int j=LOG-1;~j;j--)
if(fa[p1][j]!=fa[p2][j]) p1=fa[p1][j],p2=fa[p2][j];
return fa[p1][0];
}
inline int Dist(int p1,int p2)
{
using namespace fullgraph;
return dis[p1]+dis[p2]-2*dis[LCA(p1,p2)];
}
//LCA END
//Treap BEGIN
struct Treap
{
struct TreapNode
{
TreapNode *son[2];
int key,v,sz,cnt;
TreapNode(){key=P;}
inline void up()
{
sz=cnt;
if(son[0]) sz+=son[0]->sz;
if(son[1]) sz+=son[1]->sz;
}
inline int mkyson()
{
if(!son[0] && !son[1]) return -1;
else return (son[0]?son[0]->key:P)<(son[1]?son[1]->key:P)?0:1;
}
};
static queue<TreapNode*> trash;
TreapNode *root;
Treap(){root=0;}
inline int size(){return root?root->sz:0;}
inline TreapNode *newTreapNode(int v)
{
static TreapNode *cur,*ME=new TreapNode[MAXN<<5],*END=ME+(MAXN<<5);
//if(0)
if(!trash.empty())
{
cur=trash.front();
trash.pop();
}
else
{
if(ME==END)
END=(ME=new TreapNode[MAXN<<5])+(MAXN<<5);
cur=++ME;
}
cur->son[0]=cur->son[1]=0;
cur->key=rand()%P;cur->v=v;cur->cnt=cur->sz=1;
return cur;
}
inline void deleteTreapNode(TreapNode *cur){trash.push(cur);}
inline void trans(TreapNode *&pos,int d)
{
TreapNode *s=pos->son[d];
pos->son[d]=s->son[!d];
s->son[!d]=pos;
pos->up(),s->up();
pos=s;
}
inline int adjust(TreapNode *&pos)
{
int mks=pos->mkyson();
if((~mks) && pos->key>pos->son[mks]->key)
{
trans(pos,mks);
return !mks;
}
else return -1;
}
void Insert(TreapNode *&pos,int v)
{
if(pos==0) pos=newTreapNode(v);
else if(pos->v==v) pos->cnt++,pos->up();//pos->up....??.
else
{
Insert(pos->son[pos->v<v],v),pos->up();
adjust(pos);
}
}
inline void Insert(int v){Insert(root,v);}
inline int Rnk(int v)//返回不含等于的
{
TreapNode *pos=root;
int res=0;
while(pos)
{
if(pos->v<v)
{
res+=(pos->son[0]?pos->son[0]->sz:0)+pos->cnt;
pos=pos->son[1];
}
else pos=pos->son[0];
}
return res;
}
inline int Access(int v){return size()-Rnk(v);}
void clear(TreapNode *&pos)
{
if(!pos) return;
clear(pos->son[0]);
clear(pos->son[1]);
deleteTreapNode(pos);
pos=0;
}
inline void Clear(){clear(root);}
};
queue<Treap::TreapNode*> Treap::trash;
//Treap END
//DC BEGIN
struct DynamicTree
{
static const double lambda=0.88;
struct DyNode
{
Treap rec,anti;
set<int> son;
int orgroot,node;
inline int size(){return rec.size();}
//只需检测每次添加了节点的分支。
}*tree[MAXN];
static queue<DyNode*> recv;
inline DyNode *newDyNode(int node,int root)
{
DyNode *cur;
if(!recv.empty())
cur=recv.front(),recv.pop();
else
{
static DyNode *ME=new DyNode[MAXN<<1];
cur=++ME;
}
cur->node=node;
cur->orgroot=root;
cur->son.clear();
cur->rec.Clear();
cur->anti.Clear();
return cur;
}
inline void deleteDyNode(DyNode *cur){recv.push(cur);}
int f[MAXN],sz[MAXN],tol,uplayer[MAXN];
void calcsize(int pos,int from)
{
using namespace fullgraph;
sz[pos]=1;
for(int i=id[pos];i;i=e[i].pre)
{
int u=e[i].to;
if(u==from || tree[u]) continue;
calcsize(u,pos);
sz[pos]+=sz[u];
}
}
int DP(int pos,int from)
{
using namespace fullgraph;
int rs=pos,mi=-1;f[pos]=0;
for(int i=id[pos];i;i=e[i].pre)
{
int u=e[i].to;
if(u==from || tree[u]) continue;
rs=DP(u,pos);
mi=(mi==-1 || f[mi]>f[rs])?rs:mi;
chkmx(f[pos],sz[u]);
}
chkmx(f[pos],tol-sz[pos]);
return (mi==-1 || f[mi]>f[pos])?pos:mi;
}
inline int GC(int root)
{
using namespace fullgraph;
calcsize(root,0);
tol=sz[root];
return DP(root,0);
}
void filltreap(int pos,Treap &cur,int from,int dist)
{
using namespace fullgraph;
cur.Insert(r[pos]-dist);
for(int i=id[pos];i;i=e[i].pre)
{
int u=e[i].to;
if(u==from || tree[u]) continue;
filltreap(u,cur,pos,dist+e[i].v);
}
}
int DC(int origin,int from)
{
using namespace fullgraph;
Treap temp;
if(from)
filltreap(origin,temp,from,Dist(origin,from));//origin and from gotta be father son
int gc;DyNode *cur=newDyNode(gc=GC(origin),origin);
tree[gc]=cur;
uplayer[gc]=from;
cur->anti=temp;
cur->rec.Insert(r[gc]);
for(int i=id[gc];i;i=e[i].pre)
{
int u=e[i].to;
if(u==from || tree[u]) continue;
filltreap(u,cur->rec,gc,e[i].v);
cur->son.insert(DC(u,gc));
}
return gc;
}
void recycle(DyNode *&cur)
{
for(set<int>::iterator it=cur->son.begin();it!=cur->son.end();++it)
recycle(tree[*it]);
deleteDyNode(cur);
cur=0;
}
inline int Rebuild(int pos)
{
int up=uplayer[pos],org=tree[pos]->orgroot;
if(up) tree[up]->son.erase(pos);
recycle(tree[pos]);
int cur=DC(org,up);
if(up) tree[up]->son.insert(cur);
return cur;
}
void Insert(int pos,int father)
{
DyNode *cur=newDyNode(pos,pos);
tree[pos]=cur;
if(father)
tree[father]->son.insert(pos);
uplayer[pos]=father;
int reb=0;
for(int i=pos,pre=0;i;pre=i,i=uplayer[i])
{
int d=Dist(pos,i);
last+=tree[i]->rec.Access(d-r[pos]);
tree[i]->rec.Insert(r[pos]-d);
if(pre)
{
last-=tree[pre]->anti.Access(d-r[pos]);
tree[pre]->anti.Insert(r[pos]-d);
}
if(pre && ( ((double)tree[pre]->size()/tree[i]->size()) >lambda))
reb=i;
}
if(reb)
Rebuild(reb);
}
}Tree;
queue<DynamicTree::DyNode*> DynamicTree::recv;
//DC END
void Adjust(int pos,int father,int c)
{
AddNode(pos,father,c);
Tree.Insert(pos,father);
}
int main()
{
srand(0x1f1f1f1f);
int n;red(n),red(n);
const int P=1e9;
for(int i=1;i<=n;i++)
{
int a,c;red(a),red(c),red(r[i]);
a=a^(last%P);
Adjust(i,a,c);
white(last);
}
fwrite(outbuf,1,optr-outbuf,stdout);
return 0;
}

Powered by Hexo and Hexo-theme-hiker

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

Lucida Lu 保留所有权利