3562. 面向对象程序设计

79#0197

谢谢热心帮助!@16jsj107

79#0197

大佬能否分享下解法,TLE中…

cubercsl

提供一个在线的做法,对树上的每个结点建一个大小为$10^6$的数组,维护当前结点中每个函数的版本,没有提到的函数版本信息全部从父亲结点继承,提到的函数则进行覆盖(就是题意)。
当然直接开数组是开不下的,但是注意到每个结点之间相同的信息较多,所以可以将数组可持久化。把可持久化线段树当数组用就可以了?

16jsj107

思路就是将最后的询问先保存下来,然后在用栈表示每一个被询问的函数处理到第x个类应该是多少,一遍dfs,每次到达一个点就把这个点有的函数全是更新为当前节点,也就是入栈操作,回溯时将刚刚入栈的点退出就好,离线处理,还是挺巧妙的。。。。

你当前正在回复 博客/题目
存在问题!