做题感悟:这题比赛的时候果断没做连树链剖分是什么都搞不明白就不用提去做了,而且知道树链剖分也不一定做出来。
解题思路:
这题用线段树貌似过不了,和NYOJ 的士兵杀敌五一样,经过树链剖分后,就把树剖分成许多链,这样可以对整个链操作,结合前缀和的思想,如果某个节点到祖先节点更新这间的所有节点,可以把祖先节点 + k ,让当前节点编号 + 1 减 k ,这样最后跑一边数组就可以了,叶子节点的时候类似。
代码:
#pragma comment(linker, "/STACK:1024000000,1024000000")
#include<iostream>
#include&......
阅读全文