又一道noip模拟题

Description

现在有一棵有n个节点的树,我们有m个操作:
选择节点x,y,在它们之间的唯一路径中的每个节点中都塞入一个数z,
将一个操作记作(x,y,z)
m个操作都处理完后,对于每个节点,找到这个节点出现次数最多的数(若不止一个则输出任意一个)

n=10^5,m=10^5

TUCAO

这是我们学校小朋友做的一套noip模拟题中的一道……但是……QAQ……贴上来代表它也不是那么水……(因为我yy的一个只需要noip知识的解法是错的……)

当时我看到这题和主席yy的做法似乎都有点问题……

而这个的问题的发现是因为有一个小朋友改题的时候……问我这题怎么做……而我的做法被hack掉了……hack掉了……

不吐槽……这破玩意是noip模拟?

SOL

讲课毁一生啊少年 ——wzy

首先这题么……树链剖分肯定是可以做的……我和主席一开始想到的都是树链剖分……( 但是不保证树链剖分我想的做法和主席一样 TAT)……但这是noip模拟……我总不能和小朋友讲这个啊QAQ……会打击自信心的……

一般这种树上路径的操作题目……我们可以yy一下链上怎么做,然后树上怎么做……

链上

选择区间[l,r],在每个位置中都塞入一个数z
最后输出每个节点中出现次数最多的数

我们来看链上的做法:

离线链上有一个非常方便的做法……
就是对于操作[l,r,z],我们在位置l建立一个事件点——扫到l,就把当前状态z出现的次数+1,
同时对位置r+1建立一个事件点——扫到r+1,就把当前状态z出现的次数-1
对所有操作都做这样的操作后……再扫一遍序列就可以得到每个位置的答案了……
注意到我们扫的时候需要快速支持:修改一个数的出现次数,询问出现次数的最大值……这个线段数或平衡树都能很好完成……你想分块也是可以的……2333

怎么扩展到树上?

事件点什么的……最简单直白的想法就是扩用刚才链上的做法= =……

1.首先如果一个操作的两点有祖孙关系,就在深度最深(子孙)的节点打上-1事件点,最浅的点(祖先)打上+1事件点

2.如果没有祖孙关系,我们取它们的LCA……然后把一个操作拆成两个,这样子就变成了上面说的有祖孙关系的操作

……然后dfs,从上往下,由父结点推出子节点的各个数出现的次数……

我一开始就是这么讲解的……

可是这样真的可以么?

= =直接这样dfs是错的……我校小朋友给了我一个大大的反例
sample
假设我们有一个1-4加上数的操作……然后我们以1为根dfs,这样的话从2到3的话,显然1->4的操作是不会影响3的……

所以这样只有两个数据点是不够的

我们不得不在2->3这条边上打上撤去1->4的操作的事件点……那这样的话打的事件点就相当于一条路径上的每个点连出去的边都要打事件点……那么时间复杂度就和暴力无异……事件点操作失去了优越性……

TAT 然后怎么办?事件点这种做法真的不可以吗?

建议思考一下……








小修改

我们这样做之所以不能优化复杂度是因为树上一个点可能有很多子节点……然后对于一个影响该节点的操作,可能每个子节点都需要撤掉这个操作的标记……

既然子节点有多个,那么什么节点只有一个呢?

当然就是父结点……

我们刚才是在深度最深(子孙)的节点打上-1事件点,最浅的点(祖先)打上+1事件点,那么倒过来,改成:

深度最深(子孙)的节点打上+1事件点,最浅的点(祖先)打上-1事件点

然后dfs,dfs到叶子节点就直接维护答案,然后不是叶子节点的话,就先dfs它的所有子节点,然后合并所有子节点的信息,外加维护这些边上的事件点……就可以了,也就是说我们刚才是在从根向叶子推,现在改成叶子向根推,就可以保证只用O(1)的事件点个数来维护一个点的信息了……

怎么维护?维护依旧是大小为x的数出现了多少次= =

我们要支持快速修改大小为x的数的出现次数,询问最大值,以及合并两个数据结构

我们能不能用线段树呢?

然后我们要支持合并,那么所有线段树的值域应该一样……开一棵的内存就是O(M)的(因为有m个操作,所以出现过的数最坏有m个)

dfs有个弊端就是可能会出现很多节点:它们的状态是:dfs过一部分子节点,但是没有遍历完所有子节点,所以对于这些节点,我们都需要保存它们的遍历过的子节点的数据结构,来保证能够合并它的所有子节点的数据结构= =
当然,如果遍历过了一个节点u的所有子节点,并且合并得到了u的数据结构,我们就可以删除它所有子节点的数据结构了,因为它们这些数据结构的所有对u的父亲有用的信息已经被u的数据结构存起来了,它们就没有维护的价值了

所以直接做最坏可能dfs时会存O(n)棵线段树……TAT……内存会很紧张……我们可以用函数式线段树?(似乎是可以的?我没有仔细想)……但内存占用依旧不小……

所以还是放弃线段树为好……

我们为什么不用平衡树呢?

平衡树可以支持快速修改大小为z的数的出现次数,询问最大值,以及合并两个平衡树,如果我们用splay的话,理论上启发式合并的复杂度就是O(nlgn)的了

然后我们来思考平衡树的空间复杂度……

我们依旧可能在dfs的时候要存O(n)的平衡树

但是我们注意到平衡树里面存的是大小为z的数的出现次数……

而这个z的产生,肯定来自于一个操作(x,y,z)

而一个节点的平衡树里面存的所有z,一定都来自于它的这颗子树的操作,

我们发现每个操作的z,在dfs的任何时候最多都只会在一棵平衡树存在

为什么?因为我们每遍历完一个节点的所有子节点,就会合并所有子节点的平衡树并且加上一些修改,最后我们注意遍历完一个节点前,它的子树的操作z只能存在它的子节点的平衡树中,不会存在于u的平衡树中(u的平衡树还没有建出来呢)

……而遍历完了这个节点的所有子节点后,所有的z都转移到它的数据结构里面,同时它的子节点的数据结构全部删除……

这样的话显然每个操作的z,在dfs的任何时候最多都只会在一棵平衡树存在

所以我们可以推出 在dfs的任何时候,所有平衡树的元素个数不超过m

然后空间复杂度就靠谱了……

但是我肯定不想写这个……感觉上这还不如树链剖分好写,而且用到了splay,目测常数不会小= =

但是理论复杂度还是很好的……我们把n,m视为同阶,那么时间为O(nlgn),空间O(n)

所以还能怎么做?

树链剖分请大家想……我怎么好像要用主席树……时间O(nlg^2 n)空间O(nlgn)……不知道是不是我沙茶了

当然也可能有……时间为O(nlgn),空间O(n)而且常数小的做法……那我就不知道了= =……如果你会的话……请联系我……

之所以证明空间复杂度这么罗嗦是因为我和小朋友讲了半天他们都不明白……TAT

Comments

comments powered by Disqus