bzoj 3631: [JLOI2014]松鼠的新家 tarjanlca 树状差分

我们用tarjan 求出所有的lca,然后我们只要用树状差分区间修改一下就行,最后线性求出每个点的值。开始我默认a1 = 1,然后就gg。

差分为当前节点的值减去所有孩子节点的差分值。然后我们最后只要根据bfs倒叙推一下就好啦。

Read more

bzoj 3223: Tyvj 1729 文艺平衡树 splay

题意是给出一段排列,有一些操作,翻转一个序列。最后得出最终的序列的形态。我们可以通过平衡树来实现。

我们考虑如果我们把序列元素按照其开始的位置为权值加入到一颗平衡树中,那么如果我们要旋转区间[l,r]我们只需要将l – 1元素旋转到根。那么l-1元素的右子树则为原区间[l,n]的部分。然后我们[……]

Read more