注册 登录  
 加关注
   显示下一条  |  关闭
温馨提示!由于新浪微博认证机制调整,您的新浪微博帐号绑定已过期,请重新绑定!立即重新绑定新浪微博》  |  关闭

vfleaking的博客

My name is VFlea King

 
 
 

日志

 
 

WC 2013 糖果公园 park 题解  

2013-02-11 01:01:47|  分类: WC |  标签: |举报 |字号 订阅

  下载LOFTER 我的照片书  |
题目大意:
(网上现在没有电子版,我以后补……)
update:我扫描了个电子版,见:http://pan.baidu.com/share/link?shareid=279493&uk=235772034

orz 莫队算法。
首先对树进行分块,不会分块请先去AC BZOJ 1086 [SCOI2005]王室联邦。
我以前写过王室联邦的题解:(见我的日志:省选前衡八题目汇总梳理(1080-1089))
“首先以任意节点为根DFS,DFS的任务是解决以当前节点为根的子树(不包括当前节点)中的节点的归属,并汇报不知道去向何方者。具体做法是:对于每个正在处理的节点v,定义一个等待序列,扫一遍它的孩子。在扫的时候,假设当前for循环正在处理的是孩子u,DFS(u),然后把传回来的等待序列加到v的等待序列中。如果v的等待序列节点数超过了B,那么就让等待队列中的节点组成一个省,省会是v,但v不划入那个省中。最后,for循环结束,把v加入到等待序列中,return。在主函数中接收DFS的返回值,若等待序列为空,皆大欢喜;但事实上,等待序列不可能为空。那么等待序列中的节点数一定不超过B + 1,怎么办?答案就是放在上一个被划分出的省中去,那么上一个被划分出的省一定<=2B - 1,而现在最后无家可归的节点数一定<= B + 1,所以放在上一个被划分出的省中去节点数一定不超过3B!而且最后被划分出来的省一定和最后无家可归的节点中的某一个相邻!”
觉得刚才描述太长了?呜呜我也没办法,反正是个很sb的做法,神犇自己YY下就搞出来了。

那么通过刚才的算法每个块的大小介于[B, 3B]之间(借用王室联邦符号),并且如果设块大小为L,则易证块中两两之间的距离不超过L。

如果没有修改,则令B = sqrt(n),对于询问(v, u),按照v、u所在块的编号排序。v所在块的编号为第一关键字,u所在块的编号为第二关键字排个序,然后搞莫队算法,按顺序扫询问,在树上爬一爬。这样是O(n * sqrt(n))。(n、q是同阶的)

考虑一个询问(v, u),这样是肯定不够的。
于是变成:(v, u, ti),ti是询问时的时间,即这次询问是第几次操作。
然后v所在块的编号为第一关键字,u所在块的编号为第二关键字,ti为第三关键字。
然后搞莫队算法,按顺序扫询问,在树上爬一爬,时间有时向前有时倒流。这样令B = n ^ (2 / 3),则时间复杂度是O(n ^ (5 / 3))。(n、q是同阶的)

神犇读完上面已经明白咋写的可以直接去写代码鸟~(我觉得我啥也没说清楚,上面的描述已经足够抽象了)
下面是细节。兼职介绍莫队算法。

上一次询问用(curV, curU, curTi)表示,并且我们还保留了
visited[v]:v节点在不在curV到curU的路径上
col[v]:v节点的颜色(原题好像是糖果来着?我就叫颜色了。)
occur[c]:颜色c在curV到curU的路径上出现的次数
outcome:当前的答案。
这些信息。
现在又来了一个神奇的询问!(targetV, targetU, targetTi)
那么将curV 移动到targetV去,curU移动到targetU, 时间curTi移动到targetTi上去,然后再回答询问。

先说时间的移动好了,这个比较简单。
预处理出来每个修改在修改之前的颜色。(修改之后的颜色是输入)
如果targetTi > curTi
那么不停地curTi++,执行当前修改。
如果targetTi <= curTi
那么不停地curTi++,撤销当前修改,利用刚才的预处理。
给一个节点改变颜色的方式是,如果visited了,就XXXXXX,如果没visited,就XXXXXX。讨论一下就行了囧。

然后是节点的移动。
好像巨纠结啊囧!!!
我只会sb方法,求神犇赐教。
用S(v, u)代表 v到u的路径上的结点的集合。
用root来代表根结点,用lca(v, u)来代表v、u的最近公共祖先。
那么
S(v, u) = S(root, v) xor S(root, u) xor lca(v, u)
其中xor是集合的对称差。
简单来说就是节点出现两次消掉。

lca很讨厌,于是再定义
T(v, u) = S(root, v) xor S(root, u)
观察将curV移动到targetV前后T(curV, curU)变化:
T(curV, curU) = S(root, curV) xor S(root, curU)
T(targetV, curU) = S(root, targetV) xor S(root, curU)
取对称差:
T(curV, curU) xor T(targetV, curU)= (S(root, curV) xor S(root, curU)) xor (S(root, targetV) xor S(root, curU))
由于对称差的交换律、结合律:
T(curV, curU) xor T(targetV, curU)= S(root, curV) xor S(root, targetV)
两边同时xor T(curV, curU):
T(targetV, curU)T(curV, curU) xor S(root, curV) xor S(root, targetV)
发现最后两项很爽……哇哈哈
T(targetV, curU)T(curV, curU) xor T(curV, targetV)
(有公式恐惧症的不要走啊 T_T)

也就是说,更新的时候,xor T(curV, targetV)就行了。
即,对curV到targetV路径(除开lca(curV, targetV))上的结点,将它们的存在性取反即可。

我之前说的visited[]、occur[]、outcome的定义并不方便,因为有个lca搀和。
干脆用这仨记录集合T(curV, curU)的情况,更加方便处理。

我觉得还是上代码比较有亲切感。
verXor函数的作用是将一个结点的存在性取反。
val 即题目中的V。
sumCoe是题目中的W的前缀和。
father[v][0]是结点v的父亲。
depth[v]是结点的深度。

145     inline void verXor(const int &v)
146     {
147         outcome -= val[col[v]] * sumCoe[occur[col[v]]];
148         if (visited[v])
149             occur[col[v]]--, visited[v] = false;
150         else
151             occur[col[v]]++, visited[v] = true;
152         outcome += val[col[v]] * sumCoe[occur[col[v]]];
153     }
154 
155     inline void pathXorWithoutLCA(int v, int u)
156     {
157         if (depth[v] < depth[u])
158             swap(v, u);
159         while (depth[v] > depth[u])
160             verXor(v), v = father[v][0];
161         if (v == u)
162             return;
163         while (v != u)
164         {
165             verXor(v), verXor(u);
166             v = father[v][0], u = father[u][0];
167         }
168     }

于是定义MoveTo函数,是从上一个询问移动到当前询问去。即:
移动时间。
curV移动至targetV。
curU移动至targetU。
如何移动如前所述。

那么再定义Query函数返回当前询问的答案。Query时对curV和curU用倍增法求LCA,计入答案,然后作为返回。

于是我们就有了强大的MoveTo和Query。
吐槽:移动一次要花费那么长时间,可能到达O(n + n + q),要这两个有啥用?
没关系!虽然log级老大哥我们是搞不到了,但是根号级的小朋友还是可以搞一搞的嘛!!
对于两个形如(v, u, ti)的询问,之间的距离定义为MoveTo函数移动所需的次数。
即两个询问的结点v之间的距离,结点u之间的距离,ti之间的距离之和。
抽象成点,搞然后三维空间MST!!!!
至于你会不会写反正我不会写……

艾雨青大神犇教导我们,将树分块!
如前所述的分块方法。当时艾雨青神犇讲题的时候的分块方法没听清 T_T,上面的分块方法是我自己YY出来的。
取B = n ^ (2 / 3),设 nBlo为块的个数,用bloNum[v]来代表v所在块的编号。(block number)
则同一个块内任意两结点的距离为O(n ^ (2 / 3))的。
按照之前我说的方式对询问进行排序,按顺序作答。
注意到(bloNum[curV], bloNum[curU])一共有nBlo ^ 2个取值。
那么如果移动一次,curV还在原来的块,curU还在原来的块,这种移动的总时间复杂度是O(nBlo ^ 2 * q)的。(因为curTi还要移动)
如果移动一次,curV不在原来的块,curU不在原来的块,这种移动发生的次数最多为 nBlo ^ 2。因为我是排好序的了嘛,相同块的是放在一起的。而这种移动发生一次最坏是O(n + n + q) = O(n)。(n、q是同阶的)
所以这样回答所有询问,时间复杂度就是O(nBlo ^ 2 * n)的。
由于B = n ^ (2 / 3),块的大小介于[B, 3 * B]之间。
则nBlo = O(n ^ (1 / 3))
则时间复杂度为O(n ^ (5 / 3))。

等等……好像Query时要求LCA吧……
我写的倍增,一次O(logn)
不过O(n ^ (5 / 3) + qlogn) = O(n ^ (5 / 3))啊囧……

有个小常数优化:
对于询问(v, u, ti)
如果bloNum[v] > bloNum[u]
就交换v、u。
这样快了3s。

有什么不清楚的可以看我的代码:

orz 艾雨青的莫队算法的树上推广。
莫队算法是莫涛提出来的。给跪了……
解决离线区间询问的通用算法。
原版是维护区间[curL, curR]的信息,然后挪到其它询问去。
对形如[l, r]的询问排序,floor(l / sqrt(n)) 作为第一关键字,r作为第二关键字。
挪一挪就出解了。

艾雨青神犇说:
“其实这题有个更显然的解法”
对树分块,然后枚举每个块i,枚举每个块j,按时间顺序模拟,遇到修改就改一下,回答只回答左端点在i,右端点在j的询问。
至于神犇能不能A,反正我是不能A……最后一个点跑了10秒多一点。

其实这题dfs序列也是可做的。也用对称差就行了,这样就是传统的莫队算法。
不知道WC时上去讲解法的kac是怎么用dfs序列做的,一笔带过了。orz kac。

orz wyx吐槽:
糖果公园为什么没人能跑进100s
BZOJ上全是100s以上的。
我完全布吉岛是怎么回事……
我自己测最大的点是7s。
没开O2的总耗时是48s。

我的配置:
第2代英特尔 酷睿 i5-2410M,双核 2.3GHz。
NVIDIA GeForce GT 520M 独立显示卡(吐槽:你秀个显卡有啥用……)
内存 4GB
64位机,64位ubuntu 12.04 LTS。

求神犇鉴定……莫非BZOJ将数据复制了两份?

update: 现在有很多人跑进100s了……囧……给跪……
  评论这张
 
阅读(6947)| 评论(4)
推荐 转载

历史上的今天

评论

<#--最新日志,群博日志--> <#--推荐日志--> <#--引用记录--> <#--博主推荐--> <#--随机阅读--> <#--首页推荐--> <#--历史上的今天--> <#--被推荐日志--> <#--上一篇,下一篇--> <#-- 热度 --> <#-- 网易新闻广告 --> <#--右边模块结构--> <#--评论模块结构--> <#--引用模块结构--> <#--博主发起的投票-->
 
 
 
 
 
 
 
 
 
 
 
 
 
 

页脚

网易公司版权所有 ©1997-2017