HYSBZ 1146 网络管理Network (树链剖分,数状数组套treap)

题意:对于一棵树,每个节点有权值,动态修改权值并且询问某条链第k大的权值是多少。

题解:这题首先要用树链剖分将树上的点搞到线段树上,因为要求第k大,所以线段树套个treap。。然而这题RE到死,内存开大就ML,测试了下动态treap的代码过了,目测卡静态treap。这几天学会了树状数组套treap,去怒搞了一发,结果庆幸的是没有RE,不过一直WA。

 

LEAVE A COMMENT