dwjshift's Blog

spoj COT系列题

| Comments

先挖个大坑慢慢填……
数据结构盛宴 地狱
因为代码都比较长,所以会另外开一篇文来贴代码

COT

这么裸就不多说了吧- -
对了顺带一题在bzoj上交的话最后一行不能打换行,否则会PE……

COT2

离线的话树上莫队随便搞搞就是了,简单地说就是弄出dfs序(括号序列)然后在上面跑莫队(喂这不是跟没说一样么
主要还是讲讲在线的做法。这题在bzoj上是强制在线的。
我一开始是想着直接在dfs序上分块……在dfs序上找个关键点,相邻关键点的距离都是,预处理出每对关键点间每个元素出现的次数,然后就爆炸了0.0
既然如此为什么不像在序列上分块一样直接处理两两关键点之间的答案呢?这样的话,就需要查询dfs序的一段区间中某元素的出现次数。我们知道,在dfs序上的某个区间,当且仅当某个点左括号或者右括号只出现了一个的时候,它才能被算上。受到这个限制后好像就没法查了……?至少我现在没想到怎么搞啦
那既然在序列上搞失败了就直接在树上选关键点吧……如果一个节点的子树中有一个节点与它的距离大于,且它们之间的路径上没有关键点,我们就把这个节点选为关键点。这样子最多只会选出个关键点。当然为了方便,要把根节点也选为关键点。这样就得到了一个非常好用的性质:任意一个节点向上爬至多次就能遇到一个关键点。
因此我们可以直接处理出每个关键点到每个节点的路径上的不同元素个数,然后在查询的时候花的时间从处理好的路径转移到查询路径上来。
但是这样又有一个问题了:我们需要查询一段路径中某个元素的出现个数。可以对于每个节点,用函数式块状数组存下它到根节点的路径中每个元素的出现次数。预处理这个东西的时间空间复杂度都是,查询是
总的来说这个做法的时间复杂度是的值要根据常数稍微调整一下。于是我在本地A了之后就直接交bzoj了……然后居然T了!于是我就拼命玩常数,终于才过了……时限卡的太紧了T_T……对了这一题在bzoj上最后一行依然不能打换行(捂脸
各种细节就看代码吧
以后再找时间研究一下"ChairAlgorithm"

COT5

查询树上两个节点的距离,一般是先找到它们的,然后就是它们的距离了。
比较显然的是,对于两个节点,它们的是满足最大的一个节点。用线段树或者平衡树就能轻松维护这个了。
那怎么求节点的深度呢?可以枚举所有节点,并分别求出它们与,那么不同的的个数就是节点的深度了。容易发现,treap的中序遍历其实就是关于单调上升的一个序列。(为了方便,下面说到序列中元素的权值,都是指这个节点的值)如果有多个节点与都相同,那么这些节点在这个序列上必定是相邻的一段。因此,我们就可以这样求节点的深度:把一个区间的右端点定在,左端点从开始往左扫;再把一个区间的左端点定在,右端点从开始往右扫。往左扫的时候,区间中元素的最大值的变化次数就是与所有值比它小的节点的不同的个数;往右扫类似。那么,把往左扫和往右扫时区间中元素的最大值的变化次数加起来,便是节点的深度。
下面只讨论往左扫的做法,往右扫的话是对称的,这里不再赘述。我们用线段树来维护这个序列,对于线段树的每个节点,维护这个区间中元素的最大值,以及从区间右端点往左端点扫的时候最大值的变化次数。在合并两个区间的时候,我们要查询在中,以的最大值为初值来扫的时候最大值的变化次数。这时,我们需要继续分治下去:
1、若小于,那么,直接查询
2、否则就继续查询,再加上在中以的最大值为初值来扫的时候最大值的变化次数,即减去
由于每次合并区间的时候都要用一个log的时间来查询,所以总的时间复杂度是的。我偷懒不想写离散化,所以就直接写动态开点线段树了。

Comments

comments powered by Disqus