把FAL什么的（之前只有I，D，W

来源：蜘蛛抓取(WebSpider) 时间：2018-09-28 02:23 标签： I D

版权声明：本文为博主原创文章，未经博主允许不得转载。 /qq_/article/details/

一开始觉得nlog2的算法过不了，其实跑的飞快。
因为这题涉及到子树和祖先的修改和询问，所以直接就想到了树剖。
分母上的值显然可以预处理，那么我们就考虑如何维护分子上的值。
我们直接用一个ans数组记录每个节点的答案，现在考虑修改。
首先先用线段树维护树剖。用一个数组nx[x]表示x所在的重链中x的子节点，没有则为0
对于一个S操作，先修改当前点的答案，然后考虑如何维护其祖先的答案。
对于一条需要修改的重链，除了其第一个节点外，不难发现其余节点的答案所修改的权值就是delta*(size[x]-size[nx[x]])，那么就可以先修改每条链的第一个点，其余节点就可以在线段树上打标记啦。M操作除了先修改其子树的答案然后把delta变为size[x]*delta其余同理。

我要回帖

更多关于 I D 的文章

 

随机推荐