周弈帆的博客

Description

给一个由左右括号组成的正确括号序列（保证一个左括号一定对应右边的一个右括号）。

通过这个括号序列，我们可以构建一棵树：左括号表示进入子树，右括号表示从当前子树返回。括号相当于描述了一棵树先序遍历的出入栈过程。

现在，我们有q次操作。每次操作会交换括号序列中的两个的括号位置，该操作保证括号序列的正确性。每次操作后，都能得到一颗新的树。要求输出最开始和每次操作后树的直径（树上某两点距离的最大值）。

序列代表的树有$n$个节点，操作共$q$次。$3 \leq n \leq 100 000, q \leq100 000$
输出$n+1$棵树的直径

Sample Input & Output

5 5
(((())))
4 5
3 4
5 6
3 6
2 5

4
3
3
2
4
4

Solution

首先考虑到树的子树具有子结构性质。每一步操作都没有完全改变整棵树，有很多子结构的信息是相同的。

那么可以这样思考，在括号序列的任意一个位置开始往后走，我都可以得到一颗与这个位置前面的节点独立的一颗树。这棵树不一定是子树，因为从任意一个位置开始的括号序列可能会多出几个右括号，这种情况下这棵树会往回生长。

再从题目的问题入手，题目要我们求出每颗树的直径来。路径长可以看成两个树的深度减去两倍他们lca的深度。即：设点$u$的深度为$d(u)$,那么$u$到$v$的路径长$l(u, v)=d(u)+d(v)-2\times d(lca(u,v))$。而直径就是所有路径长的最大值。也就是说，如果能得知每个点的深度，并设法维护最大的路径长，就能得到答案。通过括号序列得到每个点每个时刻的深度是很容易的，现在我们就要设法维护路径长，得知路径长又必须知道点对的lca是谁。

恰好，题目给的是树的一个dfs序。任意两点的lca，都是在左边节点之后，右边节点之前访问。那我们也不用管lca是谁了，随便拿$u,v$点中间的一个点$w$，使得$d(u)+d(v)-2\times d(w)$最大的$w$就是它们的lca。即：$l(u, v)=max \{ d(u)+d(v)-2\times d(w) | t_u \leq t_w \leq t_v \}$ ，其中 $t$ 为括号序列中访问节点的时间(也可以说是序列中的下标）。

那问题就变得更简单了。只要是满足 $t_a \leq t_b \leq t_c$ 的三元组 $a,b,c$ ，$d(a) + d(c) - 2 * d(b)$ 就可能是一条路径长。维护最大的这个值，就可以得到直径。

如果只是算一次的话，一边维护当前深度，一边记录下最大的$d(a)$，最小的$d(b)$等值很容易就可以地$O(n)$维护当前直径。但问题是，题目有q次操作。这就得回到开始的分析了——每次操作过后，还有很多子结构的信息保留了下来。

我们需要的是子结构的哪些信息呢？注意到我们计算答案只用到了深度，在每一个子结构代表的树中，我们也必须得维护一些用于计算最大的 $d(a)+d(c)-2\times d(b)$ 的一些深度信息。我们可以把某个子结构开始位置当作相对深度，并记录在这个相对深度下，深度的最大最小值，路径左半边（左边的点到lca距离）的最大值和路径右半边的最大值。同时，还要记录这个子结构的总深度，以得到它和后面一个子结构的相对深度。通过以上信息，就可以维护子结构中最大的 $d(a)+d(c)-2\times d(b)$了。

这种用子结构来解决问题的思想和分治是类似的。分治的每一个结果都可以存在线段树中。虽然第一次求解的复杂度是$O(nlogn)$，但对于每次修改，都能在$O(logn)$的时间里得到新的答案。

总的时间复杂度$O((n + q)logn)$

Review

这道题实际上算法并没有很难，写起来也很容易，但比较考验思维，需要把问题进行巧妙地转换。我一直没有想出解法，是看完官方题解才写出这道题的。虽然我没有自己想出来，但在回味题目巧妙的解法时，还是学到了很多东西的。

在每次操作中，一定是有一些子结构没有改变的。这一点我一直都很清楚，一直都想找出这个子结构。但我一直都拘泥于树的结构，希望先把括号序列转变成树，再找出交换括号是对应树上的把哪一个子树移到哪个地方的操作。这样想下去的话，是怎么也找不出正解的。

想出这道题的关键，应该是想出lca可以用深度表示，而括号序列保证了lca在两点之间。这样的话，求直径就变成了维护几个最大最小值再做计算的问题。这里可以反映出我对树上的一些计算的表达形式还不够熟悉，没有第一时间把求直径的方法转换。而且，我对dfs序的性质不够敏感，没有利用好这个性质。

这样想出了用最大最小值维护答案，怎么建线段树，要维护哪些变量稍微想一想就能想出来。而其中能用线段树维护答案是这道题可以在时限内被解出来的关键。能够用线段树维护子结构，是因为每个路径包含的$a,b,c$三个值的时间是在一个连续区间里的，即$t_a \leq t_b \leq t_c$。这一个序列上的连续性使得问题能够通过线段树来维护。

这也给了我一些启示：线段树不是只能做那些给一个$[l,r]$区间，做一些修改操作的题目的。线段树维护的是连续区间上的性质。如果一个题目中看到了子结构性质，且这些结构构成了连续区间，就可以考虑用线段树来维护。或者换一种想法，如果一个问题可以用连续区间的分治来解决，那么分治的每一步结果就可以用线段树来保存。

自信地点击提交按钮后，得到依旧是一行刺眼的Wrong Answer。

数个小时的付出，丝毫没有得到回报。提交记录上，代码行数越变越多，判题结果却永远见不到绿色的那8个字母。

绝望笼罩了心头，焦躁充斥了大脑，整个世界变得黑暗了起来。

万般无奈下，颤颤巍巍地用鼠标复制一段文字，放到搜索引擎里面，点开第一个链接。

片刻之后，你恍然大悟。一切都好起来了，世界再次变得光明。

题解，正是照亮世界的那束光。

只要你参加过算法竞赛的训练，就一定接触过题解，上面的提到的经历，也都能感同身受。

我看过很多题解，也一直有考虑过自己写题解。但我一直因为一些问题而犹豫不前：我为什么要写题解呢？怎么样的解题记录才算好呢？

思考了很久后，我今天写出我的第一篇解题记录。我也顺便写一下我的思考结果，稍微谈一谈我对解题记录的认识。

别人的“题解”

大多数的题解都是这样的：标题是题目来源及题目名称，后面用括号写下题目算法。正文内容先把题目完完全全复制过来，之后贴上自己代码，谈一下解题的思路。大家写题解都默认使用了这套“模板”。

这样写题解是为了什么呢？是用来给那些想不出题的人来看吗？仔细一想这是不太合理的。没写过这道题的人，认真阅读这篇题解的概率极低；看过而不会写这道题的人，肯定已经理解了题意，试过了输入输出。再把多余的信息写上来是没有意义的。此外，「别人的代码」是比医生的病例还要难看懂的东西。如果要把方法讲清楚来，很多时候用文字或者伪代码来表达算法，比直接贴代码效果好很多。最后还有一小点，很多题目偏向思维题，知道了做法就可以立刻写出题来。如果把题目的算法直接写在标题里，会让那些还摇摆不定不知道要不要认真看完题解的人立刻知道题目的做法。综上，只要稍微想想就能发现，“题解”并不是写给别人看的。虽然网上的题解被大家当成了写不出题的救命稻草。

比较合理的想法是，“题解”的称呼有失偏颇，正确说法应该是解题记录。解题记录就是给以后的自己复习看的。标题里的算法方便自己找到对应类型的题目；复制的题面能避免翻原网站的麻烦；自己的代码让自己能快速理解思路；解题思路里的三言两语能快速唤起写这道题时的记忆。这样一看，解题记录纯粹是为了方便自己而写，这种说法有道理多了。

但我依旧对这种写解题记录的方式抱有一丝的厌恶。

以我狭隘的心理来揣测，许多人写题解，只是为了写题解而已。他们看到了别人的博客，看到了几百篇、上千篇解题的记录，他们感到了敬畏与心虚。于是，他们开通了自己的博客，用同样的格式来写解题记录。自己的博客越写越多，那颗空虚的内心也会越来越踏实。

也不能说这样完全不好。起码每写完一道题，贴完一道题目的题解，你能够收获一份成就感，能够让自己坚持下去。

但除此之外，这样写解题记录就是浪费自己时间。

写完一道题目，这题水不水，你学到了多少东西，你有没有学到东西，大家心里自己都有数。单纯地让解题记录数目++，只是让自己心里好受一点：不管参加比赛打得怎么样，不管我菜不菜，起码我还写了这么多题目。

那些写了几百题上千题的人，不是因为他们写了解题记录而厉害，是因为他们真的认认真真想要去提升自己，认认真真地写了那么多题目才厉害啊！

这是我一直没去写解题记录的原因。

我对自己解题记录的要求

做事首先要目标明确。思考与尝试了一段时间后，我总结出了我自己写解题记录想要达到的目的。

1. 对于解题时思路不清楚，甚至看了题解的题目，要借写解题记录的机会，彻底地把题目再思考一遍，把题目吃透来。
2. 记录反思写题时碰到的一些轻微的思考错误、代码错误，争取以后不犯错。
3. 对于略带套路的题目，写解题记录能让自己加深印象，记住这种比较特殊的题型。
4. 如果有人在写这题时碰到了困难，碰巧看到我的解题记录，我能保证他能通过我的解题记录彻底理解这道题。
5. 给未来的自己当回忆录看。

上述目的是按重要性降序排序的。与学新东西同理，写解题记录时，你会为了把事情说清楚，而不得不自己先把事情全部理解透。通过写解题记录这种手段来达到完全理解题目，这大概是写解题记录最大的目的。可以说第一条是最最重要的，相比之下后面几条都没那么重要。

可以看出，最应该写解题记录的题目，应该是在补题或学新专题时，那些略微超出自己当前能力，要稍微看看题解才能想出的题目。这些题是真正能提升自己的题。而在比赛中，你能过的题目，你一定都已经完全掌握了，这些题目就没有写记录的必要了。

顺带提一下我当前的记录格式。我会先把题意用较为清晰的话表达出来，再附上题目的样例。之后我会按照思维顺序把题目的解法娓娓道来。最后以反思收尾，回顾整道题的收获。整篇记录，起承转合，抑扬顿挫，虽无音韵、色彩之美，却有逻辑、通顺之妙。能想出这种格式的人，不可谓不是一个奇才。

今天是我第一次在博客里写解题记录。老实说，花的时间很多，我也能理解为什么很多人只是贴个代码稍微提两句题目——有认真写一篇解题记录的时间，下一题都写完了。但是我还是不愿意潦草地只把解题记录当成普通的记录。要做就把事情做好。哪怕以后我因为怕苦怕累，再也不写解题记录了。哪怕整个互联网中，只流传了我一篇质量奇高的解题记录，这篇解题记录成了我的绝唱，那也没有什么遗憾的。毕竟我的优秀作品还会有很多，这篇解题记录只是钻石里的一块金子。

Description

给m个由A,C,G,T组成的DNA片段。现在你需要构造一些长度为n的字符串，使这些字符串完全被这些DNA片段覆盖。求构造方案数 $mod$ $1e9+9$ 。（DNA片段之间可以互相重叠）

长度 $n\leq1000$，片段个数 $m\leq10$，片段长度不大于10.

Sample Input & Output

6 2
CAT
TACT

2

（CATCAT和CATACT是可行的方案）

Solution

DNA间可以相互重叠，也就是匹配完某个DNA后，匹配下一个DNA时不一定会从头开始，而是从下一个DNA的某个前缀开始（这个前缀也是当前DNA的后缀）。为了表示这种关系，肯定会想到使用AC自动机来表示匹配的状态。

有了AC自动机，我们就可以把所有 $4^n$个字符串全部输入自动机，保证状态转移“合法”，统计出最终所有满足条件的状态就行了。现在我们要做的事情有三件：统计状态，判断状态转移是否合法，判断结果是否满足条件。我们一件一件来解决。

每个状态对应AC自动机上的一个节点，因此用一个dp[MAX_NODE]数组就可以存处于当前状态的方案数。每多放入一个字符，状态就会发生转移。理论上，当前字符数的状态只与上一字符数的状态有关，拿两个dp数组循环用就行了。但为了书写方便还是先定义成dp[MAXN][MAX_NODE]，每次dp[i]由dp[i - 1]转移而来。

接下来来判断合法的状态。所有字符串都要被DNA覆盖，也就是在AC自动机上转移的时候，不能还没走到终点（DNA的结束点），就跑到另一个DNA字符串的前缀去了。只有当走到了终点的时候，才可以随意地走下一步（但是不能走回根）。

统计答案也很简单，只有那些DNA字符串结束点对应的状态才能被统计进最终答案。

根据以上分析可以写出以下式子：

$当j 为终点:$
$dp[i][j.next[k]] += dp[i - 1][j] (j.next[k] \neq root, k \in {A, C, G, T})$
$否则:$
$dp[i][j.next[k]] += dp[i - 1][j] (j.next[k] 不通过fail转移, k \in {A, C, G, T})$

提交上述代码会得到WA的结果。

考虑下面的例子: 3 3 ACCC A C。ACC显然是一个满足条件的字符串，但在自动机上，ACC却不是一个字符串的结尾，最终不会被统计答案。

那我是不是应该把字符串结尾通过fail传递下去呢？也就是说，只要一个字符串的后缀是某个更短的字符串的结尾，那这个字符串也被认为是满足条件的字符串。这样更不对了。考虑例子：2 2 ACC C，AC不满足条件，却因为有后缀C被错误地统计进了答案。

这个时候我们发现，怎么样都无法合理地表示答案。换句话说，现在这种定义状态的方式，会混淆一些本质不同的状态。在定义一个状态时，只是记录这个状态处于AC自动机的哪个节点是不够的，还得记录一些其它的东西。

从本质上思考，一个满足条件的字符串可以分成两部分，后一部分是最后一个被覆盖的DNA，前一部分是之前匹配好的一堆DNA。前一部分和后一部分可以重复。对于AC自动机上的一个状态，它的最长的DNA后缀是确定的，但是它之前已经被匹配好的长度是不确定的。而一旦我们确定了这两个值，我们只要判断之前匹配好的长度加上最长的DNA的后缀长度是否大于等于整个当前字符串的长度即可（等价于前一部分和后一部分正好拼接或覆盖）。我们在dp中还要加一维，记录某个状态被匹配的长度。顺便，为了之后的判断，AC自动机上每个节点的长度和最长DNA后缀的长度也要提前统计好来，后者可以通过fail边来转移。

和开始一样，继续解决三个问题：状态定义、答案判断、合法转移判断。

现在，$dp[i][j][k]$被定义为放第$i$个字符时，处于AC自动机上$j$号节点，在自动机前面已经匹配好了长度为$k$（而不是总长度已经匹配好了$k$）的方案数。$j.len,j.low$分别表示某个节点的长度，最长DNA后缀长度。

对于某个$j,k$，若$j.low + k \geq j.len$，则说明这个状态满足条件。最终$dp[n][j][k]$中满足条件的状态的dp值之和就是题目的答案。

转移时，我们不再死板通过判断一条边是否是通过fail转移的来判断这个转移合不合法。在当前一个非答案状态$i,j,k$上，对于下一状态$j.next$，只要$j.next.len + k > j.len$，就能保证在状态转移时中间没有“断掉”。下一个状态的最长匹配长度为$j.next.len + k - j.len - 1$。也就是说:
$dp[i + 1][j.next][j.next.len + k - j.len - 1] += dp[i][j][k]$

对于某个状态，如果它已经满足了被覆盖的条件，则下一状态的最长匹配长度一定是下一状态的长度减1（因为多出了一个新的未匹配字符），写成式子的话：
$dp[i + 1][j.next][j.next.len - 1] += dp[i][j][k]$

至此，题目顺利解完。dp数组是1000 100 10的，时间复杂度$O(n|str|\sum|str|)$

Review

题解部分应该是正常的思考过程，发现二维不够后用三维dp，这也是我写这题从WA改到AC的过程。

之前我一直以为，AC自动机中dp都很容易，只和处于哪个节点有关。看完题面后，我立马敲了一个二维dp出来，很快WA了。

在cf上对着样例调试多次后，我才发现怎么定义dp都不行。看了一眼题解，发现状态要多定义一维后，我重新地把题目考虑了一遍，定义出了新的状态。

后来状态转移我差不多写完了，交上去WA了一个大的样例。仔细思考过后我发现，非答案状态在转移时，它的最长匹配长度可能会变的，这一步转移需要认真考虑。改完这一处后总算AC了。

这题对我最大的启示和警示是，AC自动机的dp不一定都那么简单，很多时候但靠节点来定义状态是不够的。

在用dp时，一定要把状态的每一个变量的转移都考虑好。尤其是在重新定义了dp状态后，最好能完全从头推一遍递推关系。

2019年的3月17日，对于人类来说，可能只是普通的一天。但是，这一天却发生了一件影响极其深远的事：天才游戏设计师、世界著名大局观选手、改变中国的十四亿人中重要的一员——周弈帆开始写博客了。

第一篇博客就不谈什么大的东西了，我就谈一谈我为什么要写博客。

为什么要写？

人活得久了，见过的悲欢离合越多，对这个世界的理解也就越加深刻。现在的我虽年未弱冠，但已经隐隐参透出了这个世界的一些奥妙。如果把这些宝贵的知识财富一直藏在我的心里，那对于世界思想界来说将是一件极为可惜的事。所以，我想把我自己对于一些我熟悉的事情的看法、经验整理一下，创造出一些有趣的 「理论」，供世人品鉴。

现在的我没什么大的成就，唯一的可以提一提的就是在高考这个战场上杀出了一条血路。在学校学了这么多年，我深深感受到了学习的方法性。差的老师、烂的教材，都会为你的学习带来极大的阻碍。我想写一些简明易懂的 「技术文章」，来减少那些恰好和我专业方向相同的人的时间。

人嘛，总是希望得到别人的认同——你吹我，你就是我的好朋友；你黑我，我就恨不得把你喷到改口为止。虽然我的反应不会这么激烈，但那份渴望认同的心还是和常人无异的。我有时也会发一些带有主观色彩的 「评论」 文章。我的文字功底不是很好，写不出什么辞藻华丽，又有内涵的抒情文，但我可以用结构严谨的议论文，一字一句地说清楚我的看法。

为什么是博客？

自互联网在中国开始兴盛以来，主流社交方式换了一波又一波。我虽目睹了整个互联网的发展过程，却因为年纪尚小，没有亲身投入到这股浪潮中。当我想好好得在社交媒体上展示自己时，却发现我已经不太适应主流的社交媒体了。

对于大部分像我这样的平民百姓来说，社交媒体就是满足自己虚荣心的小小舞台。分享出生活中亮眼的几个片段，极力吸引住熟人的注意。每一次被浏览，那渴望被关注的心就会得到一丝的满足。

对于某些媒体来说，社交媒体不过是一个敛财的工具。被关注得越多，得到的收益越多。只是四处张罗吆喝也还好，但用一些有成本的手段去创造关注，这就让社交媒体本身的性质改变了。

越快越短的东西，只会让价值不断地消失。

我仔细想想，还是博客好。在一个人的天地里，能够随心所欲地发言。我会在这里，慢慢地、静静地，书写我自己的价值。博客是也算是一个社交媒体，虽然不会有太多的人去关注，但也不会有多余的东西。

我的目标

今天勉强算是完成了第一篇博客，但距离我准备写博客已经过去一个多月了，我本身拖延症似乎有点重。再加上博客本来就是带有娱乐性质的东西，强求自己做一些事也没必要。在博客经营上大而具体的目标就不订了。

然而，如果我享受到了写博客的乐趣，我就会竭尽所能，去写出一些有价值的东西。之后，我会让更多的人去看的文章。我不求别的，只希望某些人在看过我的文章后，能发自内心地说出：

从字里行间就能看出来，这个小伙子天赋异禀，才高八斗。遣词不可谓不精妙；造句不可谓不用心；道理不可谓不深刻。可谓是江山代有人才出。看着他的文字，我的脑海中就浮现出一幅英俊、帅气、潇洒、精致的脸庞。此人前途无量啊。