门户网站建设与运行,安装wordpress出现500错误,自学网站建设看什么书,html5 wordpress我觉得很厉害。要是考场上能把这道题切了的话数据结构的水平肯定是不低的。
考虑简化版问题#xff1a;如果只询问一个点的答案怎么做。
注意#xff0c;我这么做是有风险的。我把战线拉长了。不过当然#xff0c;如果连简化版的问题都做不了#xff0c;那何谈正解#…我觉得很厉害。要是考场上能把这道题切了的话数据结构的水平肯定是不低的。
考虑简化版问题如果只询问一个点的答案怎么做。
注意我这么做是有风险的。我把战线拉长了。不过当然如果连简化版的问题都做不了那何谈正解幸运的是这确实是一道数据结构多合一的题。
考虑 长链剖分 。那么在 x x x节点上加入棋子时子树外的点就异或上 x x x子树的最大深度如果以 x x x为根的最长链在重儿子上面那么就给除了重儿子外的子树打标记注意到 其 dfn \text{dfn} dfn序是连续的 可以直接打标对于重儿子也可以直接对整颗树打标只需处理出 x x x去掉重儿子后的最长链长度即可如果最长链在父亲上那么直接对 x x x整颗子树修改即可。
发现了吗经过细致分析我们发现这道题其实并不复杂。当然要建立在想到长链剖分的基础上。
这题更神奇的地方在于让我们求 dist(x,v) ≤ 1 \text{dist(x,v)}\le 1 dist(x,v)≤1的所有根的答案。这是个非常恼人的限制因为你知道会被菊花图卡但是不知道会被卡成多少分。
有没有严格的做法呢答案是有的。但是我一定想不到。 但是需要用到非常高级的技巧。其实说白了询问可以拆分成 x x x x x x的父亲 x x x的重儿子以及 x x x的所有轻儿子。如果一次插入影响到点的数目是 O ( 1 ) O(1) O(1)那么我们的目的就达到了。
考虑这样一个问题如何用字典树维护 c i ⊕ x d i c_i\oplus xd_i ci⊕xdi的所有点对这个问题也非常具有迷惑性。因为 d i d_i di是定值 x x x又是每次询问给定的那么维护 c i c_i ci然后在 trie \text{trie} trie树上查不就完了并且 trie \text{trie} trie树查询的复杂度也是 log n \log n logn的。这样分析下来觉得越来越有道理了但是考场上完全想不到这里来啊
初始化的时候 c i c_i ci都是定值。手动分讨一波如果最长链在重儿子上面那么 x x x的所有轻儿子都异或上同一个数直接在 x x x上打标就完了如果最长链在父亲上面那么轻儿子还是异或上同一个数。事实上可以发现任意时刻轻儿子的标都和这个点上的标是一样的唯一的例外是当插入的点就是这个轻儿子的情况。但是正如前所说修改影响到的节点数目是 O ( 1 ) O(1) O(1)的所以直接在 trie \text{trie} trie树上暴力修改就行。然后就做完了。
所以发现了吗这种题逻辑链条太长了。其实思维难度并不大。
复杂度 O ( n log n ) O(n\log n) O(nlogn)。
要考虑的细节挺多了。所以代码先咕了。
