操作树 引入 有的时候我们需要处理一个可持久化信息,但是我们知道可持久化一般比较难写,所以对于离线的题目,有一种新的解决办法。 我们建立一颗树,然后这棵树的每一个界点代表做一次操作,当离线做某一个操作时: 如果这个操作时回到以前的某个版本 \(x\) ,那么么连边 \((x, i)\) 如果这个操作为正常的修改,那么连边 \((i-1, i)\) 最终会变成一颗树,然后我们按照这棵树正常 DFS ,回溯时撤销修改。 OK(()) !!!