UOJ Logo zx2003的博客

博客

NOI2019D2T1的 O(n logn) 算法

2019-09-18 20:21:11 By zx2003

感觉也不是很难,不过先前没听人提过。

显然题意可以转化为给定二维平面上的若干个点和若干个矩形,然后需要按某个特定的顺序取出矩形中的所有点。

一个简单的做法是对 $x$ 这一维建线段树,对线段树的每个节点维护一个set,每次需要取出点的时候就在set里通过lower_bound逐个找到需要的点。

这样复杂度是 $O(n\log^2n)$ 。

更优秀的做法是把所有点的 $y$ 坐标和询问矩形的下边界排个序,从小到大进行扫描线,同时维护出每个矩形在线段树的每个节点上lower_bound的结果。

取出点的时候,在线段树的每个节点上我们需要执行的操作是1.找到某个位置往后第一个没被删除的点;2.删除某个点。

显然这可以使用并查集做到线性,链接在这里

代码在这里

为了方便实现以及实践效率,该代码中并没有使用线性并查集。

由于数据太水,运行时间被kdtree吊打。

反正数据结构的技能点不是技能点,打表的技能点才是技能点,随便出个T1数据乱造就好了对吧。

关于 [JSOI2019]节日庆典 的一个线性做法

2019-06-01 20:48:08 By zx2003

题目链接

很久以前我想过这个问题,但当时没有什么好的办法。

昨天去做了下江苏省选二轮的题,发现居然被出出来了。

看到问题后一个自然的想法是求出每个前缀的lyndon word分解(模板题在此)。

但是博主只知道Duval算法(可以看鏼爷论文),然后该算法需要在字符串结尾补$ - \infty $字符,如果要求出每个前缀的lyndon word分解,原来的均摊分析就失效了。

回忆一下Duval算法的过程,前缀$i$做完之后是(若干已经做好的)+(某个串s)重复t遍+s的某个前缀u。

可以证明,已经做好的部分对答案没有影响,(某个串s)重复t遍对答案有影响的部分只有第一次出现的位置,而$u$整个串都可能对答案有影响。

怎么办?

一个想法是,那就同时维护出串$u$,在执行Duval算法后的状态。

但是串$u$执行完Duval算法后会得到一个串u',我们需要递归执行前述的过程。

容易发现$|u| \le |s| \le \frac{i}{2}$,所以这个“递归”只会有 $logn$ 层。

具体实现可以参考这份代码

让我们思考一些可能的优化。

首先一个想法是,在Duval算法运行过程中,既然串$u$在之前已经出现过了,那么是不是可以复用之前的运算结果?

记串u第一次出现的位置的结尾处为$x$

也就是说,我们猜想$ans_i=min(串s第一次出现的位置的开头,ans_x)$,注意这里的$ans_i$可以认为是$i$-题目要求输出的真实的答案。

如果这样不对,那么必然存在两个位置$p$和$q$使得前缀$x$从$p$开始和从$q$开始的循环移位都是相等的。

否则这两个位置开始的循环移位在$x$之前已经比出大小,从$x$扩展到$i$不会对大小比较产生影响。

从而前缀$x$构成的串存在非平凡整循环节$y$。

同理可以证明$y$也存在非平凡整循环节.

如此递归下去,可以得到串$x$字符全部相等,此时我们可以平凡地验证结论的正确性。

有了这个结论,配合线性SA和$O(n)-O(1)$RMQ,我们可以获得本题的一个线性算法。

不过线性SA和$O(n)-O(1)$RMQ太难写了,博主写不动。

由于lyndon word的性质和Duval算法的正确性,在处理前缀$i$的答案时,$ans_x$所对应的后缀必然大于等于串s的等长前缀。

所以我们只需使用字符串哈希判定子串相等,之后便转化为了一个子串和原串比较大小,这可以通过exkmp来线性实现。

最后提交在这里,好像比$O(nlogn)$还慢。

如果本文论述出现了漏洞,欢迎读者指出。

PS: 听说16年有篇论文提出了关于子串最小循环的$O(n)-O(1)$算法,感觉本文可能只在OI中有用。

CTS2019D2T2的一种非标算做法

2019-05-14 19:32:02 By zx2003

下午上台发言的时候有点呆滞,感觉讲的东西自己都听不懂。可能讲课水平不太行。

首先考虑计数所有子串均大于等于s的串的个数。

然后对串s建立KMP自动机,补齐26n条转移边的那种。

注意根据题意,部分跳回根的转移边是不合法的

之后枚举在自动机里走了无穷多个串s之后到达的节点是点u。

由这个定义,在自动机里,从点u出发行走完一个完整的串s之后,会回到点u自己。

于是我们只要解决在一张有向图上,一个点出发走m步回到自己的方案数即可。单次复杂度$O(m * n * 26)$

由于还要枚举点u,所以总的复杂度是$O(n^2m * 26)$

而且可以发现这个算法并不依赖于n与m的大小关系。

这样我们就能获得60分啦

实际上这个算法是有漏洞的。

一个点每条转移边并不是都能走。

想像一下,串s形如abdabc,我们现在在长度为5的前缀对应的节点上。

如果下一个字符是c,那么在这个无穷循环串中,我们就会获得一个子串abc,显然由此可以导出一个比s小的子串。

所以,每个点上所有不是跳回根的转移边只有字符最大的一条有用。

如果从根出发只走这样的转移边,那么会形成一个rho的形状。

考虑在这个rho上计数。

我们先算出$f_{i,j}$表示从根出发走i步,走到节点j的方案数。这一部分复杂度$O(nm)$。

然后还是跟之前一样枚举节点u。

如果u不经过根,那么路径唯一,方案数可以$O(1)$计算。

如果u经过根,那么枚举从u出发走几步才跳回根。这一部分复杂度也是$O(nm)$。

最后该算法总复杂度为$O(mn)$。

感觉rho的结构挺简洁的吧,不过考场上由于某些原因,并没有考虑过改进复杂度。

有没有老哥来把前面这个算法优化一下啊?

upd:

可能是可以优化的。

设生成函数F满足$f_i$为从根出发走$i$步第一次走回根的方案数。

F是可以直接在KMP过程中计算的。

所有节点走$m$步并且经过根的总方案数应该是$[x^m] (F' * x -F +1) * \frac{1}{1-F}$

复杂度应该是$O(n+mlogm)$。

十二省联考D2T3 hope 不用求逆的做法

2019-04-12 18:15:28 By zx2003

大概有两种,第一种是魔改原官方题解做法,第二种则是直接避免(求出每个点的子树答案)。


算法一

2019.6.1upd:他假了,原因可以见lca的回复

在长链剖分的时候我们需要维护一个类似与滑动窗口的东西。

每次从滑动窗口里踢掉一个东西的时候,我们需要求出这个元素的真实值,官方题解在这里需要求逆。

但实际上每次遇到这种情况暴力$O(L)$地下传标记复杂度是对的。

证明的大概思路是,这样做的复杂度是链长+$\sum 每相邻两次的重叠长度$,然后对于每次重叠,一定存在一个短子树的深度大于等于重叠长度。

所以复杂度与长链剖分相同,仍为$O(n)$


算法二

一个自然的想法是通过树分治来规避求逆元。

但是一个很大的问题在于,我们仍然需要求出子连通块中的某个点到分治中心的答案,而且这一步相对于原问题没有任何简化。

我们能不能简化这一步呢?

注意到如果连通块直径不超过$L$,那么这一步是可以简单树上DP来完成的。

这就启示我们使用Top cluster 剖分。

我们可以将原树分割成$O(\frac{n}{L})$个直径不超过$L$的簇。

对于每个簇,可以预处理出,在簇的内部,两个端点的DP数组。

簇与簇之间的影响需要$O(\frac{n}{L})$次合并DP数组来计算。

合并两个DP数组的复杂度为$O(L)$,最后总复杂度为$O(\frac{n}{L} * L)=O(n)$


但是好像想要出个不能求逆的加强版比较困难,博主一时没想到有什么,不可逆,性质恰到好处,在本题中还能方便维护的信息。

算法一没有实现过,但应该是对的(吧)。

算法二的实现在这里->链接

由于滥用vector导致常数巨大,而且博主懒得卡常,所以只有80分。

关于[ZJOI2017]汉诺塔一题的一个问题

2019-03-06 11:34:23 By zx2003

题面保证“在实际的测试点中,T 组数据的 K 都是相同的”。

但是extra test 1并不满足这个性质。

能否予以修正? @whzzt

zx2003 Avatar