12/3
来到了衡实。
要先找回代码的感觉……做一做联赛 T4 吧。
12/4
被卡常了。
我不做了。
学网络流去。
最小割
一直不太清楚这个东西是干什么的……果然需要多做一些题掌握一些模型？
另外割成两块不是指彻底变成两块，而是源点和汇点之间不可达。
做了两个题，感觉好魔幻啊。
还是说尽量去总结一下。
首先最小割的特点，就是对于一个类似于二分图的东西（左右是源点和汇点，中间是一些其他的点相连），选出一些边，满足如下性质：
-
割完之后的任意一个点要么满足能从源点到达，要么能到达汇点，并且只满足一个条件。
-
当满足上述条件时，容易发现任何一条从源点到汇点的路径都必须至少断掉一条边。
首先加无穷边表示这条边不可断确实是一个常用的技巧。
然后在两边的边的断开有一种统一性。
就是为了满足上面的条件而形成的性质。
这两个题有一个特点，就是每个点有两种选择。
在图上分别对应源点和汇点，最终怎样联通就说明怎么选。
这俩题还是这样的：两个点同时选会有额外的贡献。
为了把这额外的贡献表示出来，在图中多加一个虚拟的点和一条平行的路径，在对应的一边相连，再将两个点和那个虚拟节点相连。
然后你发现，如果两个点中有一个点不选这一边，也就是那一条边被断掉了，那么多连的那一条边也一定会被断掉，否则就没有与右边完全断掉了。
这样就实现了对应的操作，同时由于算的都是断掉的边的总和，所以一般就会去算舍弃的总和。
12/5
大概是做了一整天最小割的样子，基本上就是满足上面的条件而出现的比较好的性质。
晚上搬宿舍楼了，从一层楼的六楼搬到另一层楼的六楼。
这辈子再也不想爬楼了。
12/6
突然意识到还有两天就学考了。
有上下界网络流
其实就相当于是多了一个下界的限制？
好的，做了两个题。板子刷得还是挺顺利的，所以稍微来总结一下。
把整个的网络流都总结一下吧。
首先，网络流是什么呢？大概是可以抽象成有若干个指标，然后他们之间有一些相互限制或者相互作用，然后要给这些指标分配相应的值以达成某些目的。
听起来很 DP，但是这些题目往往数据范围不大，限制比较复杂，适合用图表示而不是数字，并且分配的数字要求精细，所以就可以网络流了。
正常的网络流大抵就是这样，解决类似于分配指标的问题。
之后是费用流，就是在保证最大流的前提下给每条边上的每个单位流量又加上了费用，当然还有可行费用流，就是不要求一定是最大流。
这东西好像不太好抽象的样子，抽象出来也比较明显？
然后是最小割，这个就比较抽象了，第一眼甚至不知道他是干什么的。
在某些问题中，指标之间的相互作用不仅仅是限制有无，有时还会产生额外的贡献（比如某些矩形内部栅栏状的交点问题）。这样就不适宜用普通的网络流求解了。因为流的上限限制是固定的，并不能有额外的贡献。
于是有了最小割。大体思想大概是把源点和汇点分别看成是两个状态，割完以后与那个联通就相当于选择了哪个状态，算的时候先加上所有状态的贡献，再把没有被选上的状态减去。
当然也有以最小割直接作为答案的题，最小割的题目中流量分配是很关键的问题。
顺带一提，此时流量上限即使为零也是可以出现在最小割的图中的，两者并没有什么直接影响。
最后就是上下界全家桶了.
所谓上下界,不过是在原本只有上界的基础上加了一个下界限制罢了。通过几遍最大流的调整可以仅仅增加一些常数来解决问题。
正如课件所说的,核心思想是调整。对于无源汇上下界，首先给每条边加载下界流量，然后建出对应的残量网络，由于此时想要满足总体流量守恒的话，残量网络必定是不守恒的（加载下界流量后不流量守恒的情况下），所以建一个虚拟的源点和汇点，负责平衡对应的流量。
对于有源汇的，把首尾相接就变成无源汇的了。
如果要求是最大流，跑完上面的流之后再在剩下的原图上跑最大流。
最小流只需要反向跑最大流就行。
12/13
来到了首师附。
在广大 HE oier 和 **CCF 的不懈努力下，HE 省队名额成功从 \(15\) 个变成了 \(7\) 个。
仍然保留三分之一校线。
这副本难度直接到地狱级了。
概率很小，极小，大家心知肚明。
那又怎样呢？
“我都走到这里了，你好歹让我正式上一次省选考场再退吧？”
释然的同时，心里多少还偷偷抱着一点点侥幸的期许。
12/14
好\(^{tm}\)大的雪啊……
做了两天下午这个七彩树,收获了还不少。
首先有一个，如果要统计树的子树内的颜色数，有一种是直接拍扁成序列然后上主席树。
但是我们注意到他查的是整个子树里面的，意味着可以进行某些类似于差分的操作。
比如两个颜色相同的的节点，它们什么时候会算到一起呢？就是查询点在其 \(lca\) 及以上的时候。
所以直接把多出来的贡献放到 \(lca\) 上就可以啦。
（此处如果多想一步，对于普通序列上的颜色段问题，是否也可以弄成一棵树？大抵是不太行，毕竟查询区间很跳跃）
如果我再问，不是整个子树了，我们只查节点向下若干层的呢？
考虑一层一层地加入节点，动态维护 \(lca\) 上的权值信息，对每个序列用 \(set\) 维护当前已入选段。
如果我再问，我强制在线呢？
我们发现虽然有两个维度，但是父子节点之间的信息有很大联系和共通性，因此可以主席树，以深度为纵轴，节点编号为横轴，提前扫一遍就解决了。
12/26
我去我怎么又咕咕咕了再这样下去成鸽王了
元旦不放假，欧耶！
LCT
可以动态维护一些树上信息，主要包括断边和连边。同时能够隔离出一整条路径，各种操作方面都比较灵活，在维护最值方面也有一定的优势。
劣势就是代码又长又不好调细节还贼多，还用到了 \(Splay\)，感觉不复习的话就要变成黑盒了。
稍微总结一下这几天出现的错误。
-
初始化的时候把 \(return\) 写在 \(for\) 里面。
-
没有对 \(0\) 进行正确的初始化。
-
\(rotate\) 里面写错。
-
下传标记的错误。
-
基本上很难实现边权下放，所以以后直接把边抽象成一个点得了。
-
连边和断边的时候如果不判断是否合法还要多连一下，所以以后直接判断一下就完了。
-
下标范围弄错。
-
注意 \(access\) 或者 \(findroot\) 操作之后的当前根是什么。
-
区分 \(makeroot\) 和 \(access+Splay\) 的区别。
后缀数组
然后是本来打算今天开后缀数组，但是好像时间不够了，所以是明天的事了。
12/27
后缀数组
就是对一个字符串的所有后缀，维护每个后缀的排名和每个排名对应的后缀。
首先是排序。
倍增的排序做法差不多也是能够看懂，他说的第二关键字排序的实质……
是因为除了 \(0\) 之外本身就是有序的吧？
所以是只需要把 \(0\) 放到前面，然后剩下的原序放入即可。
\(sa\) 数组既是编号，也是起始位置。
哦，我算跳到外面的是第二关键字起点跳到外面的。
上面那个枚举的是第一关键字，下面这个枚举的是第二关键字。
这个时候我怎么可能会算上出去的那些呢！
\(id,sa\) 返回的就是对应排名的编号，\(rk,oldrk\) 返回的就是对应编号的排名，这个比较绕，要搞明白。
哈哈
通过一些应用，大概是了解了后缀数组的用处了。
后缀数组是有用的，是因为很多情况下我们并不关注后缀的情况。
由于字符串比较的特性，如果前面我们关注的部分不同，他会给出合理的判断；如果前面关注的部分相同，那么后面谁大谁小也无所谓了。
\(height\) 数组
对于字符串来说，排序本身也是一种判定相似度的方法。
那么统计 \(lcp\) 的 \(height\) 也是很好用的。
12/28
今天是个好日子。今天既是肯德基疯狂星期四，又是德克士卡友日。可惜我在学校。
喵星球上的点名
非常神奇的一道题。但是感觉最神奇的是我居然把想到的巨麻烦无比的思路写出来了……
题解做法：
首先把所有串杂糅到一起，然后处理处 \(height\) 直接找到每个串所处区间，复杂度 \(O(n)\)
然后就变成了两部分。一个是统计区间内颜色种类，一个是统计每种颜色被多少区间覆盖。
第一问使用莫队，复杂度 \(O(n\sqrt n)\)
第二问对于每一种颜色，使用差分。当这种颜色最开始出现时，统计剩下还有多少区间；当这种颜色最后一次出现时，统计剩下还有多少区间。两者减去，复杂度 \(O(n)\)
我的做法：
首先懒得把所有串杂糅到一起，选择求出 \(sa\) 之后两次二分找出区间。好写，赢；复杂度 \(O(n\log n)\) 还有一个 \(2\) 的常数，输；不用 \(height\)，赢。
第一问选择使用 HH的项链 离线直接淦，复杂度 \(O(n\log n)\)，赢。
第二问使用主席树直接淦，复杂度 \(O(n\log n)\)，输。
理论总复杂度 \(O(n\log n)\)，赢；自带超级大常数，输；好写，赢；跑得比 \(jjq\) 快，赢麻了。
12/29
今天有模拟赛
这是非常危险的。无论是前半个小时死机重启，还是三个半小时的死磕一题，还是后面用半个小时仅写暴力不想正解。
你说得对，但是我 \(T3\) 没开 \(long long\) 痛失赛时首 \(A\)，唉。
T1，从后往前来说，后面的人的选择是固定的，必定是选比较小的那一个，那么前一个人就是在后面的人选剩下的范围里面选比较小的那一个。
感觉我赛时想到这一层就可以直接开做了。
证明的话，就是归纳证明。当前的人不选那一个的话，前面的人依旧按照对应的规则选，选了 \(A,B\) 之外的数就是把问题推给前面的人，选了 \(A,B\) 中的一个数，这个问题就解决了，另外一个就一定不会被选。
然后就证明了。
关于转移的优化，也是比较有教育意义的。对于某一个来说，前面的人对他没有影响，在 \(p\) 的转移过程中后面的影响只会不断增加，那么记录每一个位置就能够单调移动了。
T2，交互题，阴间数学题，内存微操题，buff 叠满了。
学到的比较有用的（？）就是 \(n\) 个 \((0,1)\) 随机变量的期望最小值为 \(\frac{1}{n+1}\)
T3，要是开 long long 我就场切了
是一堆 \(RMQ\) 和巨多二分的无意义堆砌，感觉比较好的是使用后缀和+二分求区间前缀最大值和。
大雾
今天是怎么做到弥漫一整天的雾的？甚至一直都是那种“十米之外，人畜不分”的状态。
12/30
品酒大会
为啥要用并差集啊？直接单调栈扫一遍不是也可以吗？
恼了，不要被诈骗了。
一时兴起的 tui 歌
歌剧2 Опера №2
Дом мой достроен,
家盖好了，
Но я в нем один.
里面的我孑然一身。
Хлопнул дверь за спиной
房门在身后砰然作响。
Ветер осенний стучится в окно,
秋风拍打着窗户，
Плачет опять надо мной.
凄然，为我而泣。
Ночью гроза, А на утро туман.
夜雷阵阵，晨雾弥漫。
Солнце остыло совсем.
阳光已彻底冰冷。
Давние боли Идут чередой.
久远的痛接踵而至，
Пусть собираются все.
让大家都准备好吧。
Wuuuuuuuoooooooooooooooooooo~~~
Wuuuuuuuoooooooooooooooooooo~~~
Дом мой достроен,
家盖好了，
Но я в нем один.
里面的我孑然一身。
Хлопнул дверь за спиной.
房门在身后怦然作响。
Ветер осенний стучится в окно
秋风拍打着窗户，
Плачет опять надо мной.
凄然，为我而泣。
Это судьба, а судьбу не могу
这就是命运，
Я ни о чем просить.
无法祈求改变。
Только я знаю, как после меня
我只知道，在我走之后，
Станут ветра голосить
是风儿无尽的呻吟。
Wuuuuuuuoooooooooooooooooooo~~~
Wuuuuuuuoooooooooooooooooooo~~~
双倍回文
一堆无意义的巨大复杂麻烦做法被喵了（这其中也包括你的 PAM）。
才意识到一个字符串里面本质不同的回文串只会有 \(n\) 个。
因为每次从前面转移 \(k\) 过来的时候，那个回文串是一样的，没有必要计入答案。
所以只在每次暴力扩展的时候统计答案即可。
怎么可以这么优美啊！
12/31
PAM 回文自动机
感觉一般优美。
用来处理每个点结尾的本质不同的回文串的。
其实还是挺好的。
但是这种题的做法好像都挺多的样子。
1/1
元旦快乐~
SAM 后缀自动机
确实讲得挺乱的。
但是稍微总结一下，就是 \(SAM\) 上面的每个节点都可以认为是对应着原本的串中的一个前缀，从起点到这个点的每一条路径都是这个前缀的某一个后缀。
这些后缀的共同点是他们在原串中的出现位置的集合是相同的，因此对于某一个前缀，表示它的节点不一定唯一；在一个节点内也不一定能够表示完所有的后缀。
但是这些后缀的长度，在一个节点内一定是连续的。因为在原串中的出现位置是一个随长度减小单调不降的东西。
为了将这些分散开的后缀结合起来，定义一个后缀链接，由当前节点连向上一个节点，能够把他们的后缀集合完美地拼起来。
在构建的时候，要考虑的事情是构建出一个连续的后缀集合，只需要在之前连续的区间上连边就行了，通过后缀链接就能够找到连续的区间。
如果途中发现已经有了对应的转移边，并且这个转移边还是最大边，这也就跟我们之前的区间连上了，直接把后缀链接连到这里即可。
如果不是最大边，我们需要把这个点拆成两个点，一个让他是最大边，一个是剩下的东西。分别维护一下这两个点就对了。
现在就只差复杂度的证明了！
好的，证明也会了。
但是现在题做不出来……
1/2
我发现了，在 SAM 极优的线性做法和普适性下，空间永远比时间先颤抖。
1/4
之前是一直在改模拟赛，所以啥都没写。
昨天的模拟赛
首先发现了自己的问题，就是心态很容易受到前两个小时影响。要是前两个小时有什么建树的话还比较好，要是没有基本上就寄了。
而且我自己调节能力还贼烂。
所以之后要么是专心做题，不去想有的没的，要么能够快快回复过来，这样太受罪了。
T1 是树剖的神秘题，但是可以用点分树做，只需要对每个节点维护一个 set 一棵线段树再总体维护一个可删堆。
T2 是 min-max 容斥 + 轮廓线 dp 的神秘题，所以咕了。
T3 是一个根号分治的好 dp 题，总的来说就是利用各种 dp 性质进行优化，学到了可以多个数的滚动。
GSAM 广义后缀自动机
实际上就是能够处理多个串的 SAM，一般来说直接把 las 放到起始点重新跑一遍就行了，但是要特判是否有已有边，以及是否要新建节点。
相当于是在 tire 树上面进行 dfs，如果直接给出 tire 树的话，不能直接插入子串，可以 bfs。
1/5
熟悉的文章
SAM 不能够当做黑盒，它的 fa 数组的意义和用法都很重要。
一开始拿优先队列做的，居然能过去，我哭死。
当然可以简化成维护一个单调区间内的最小值，太久没做过优先队列都忘了这玩意能用优先队列维护了。
维护一个单调递增的优先队列即可。
每次从队尾插，然后弹队首查队首。
1/7
你以为我咕了两天，实际上我被恶心了两天。
你的名字
人话题面：给定一个模板串，每次询问给定一个字符串和模板串的一个区间，求字符串里面有多少本质不同的子串满足没有在给定区间内出现过。
这要是单次做方法很多，但不是每一种方法都能够优化到多次询问。
考虑求在给定区间内出现过的不同子串。
我们能够考虑到一些事情，比如说因为排除掉的子串也是本质不同的，所以肯定也是要在当前询问串的 SAM 上面跑的。
另外，这玩意也是一个单调性的东西。也就是说只需要对每一个前缀维护其能够匹配上的最大后缀长度即可。
我们可以记一个类似的长度标记，然后最后统一 dfs 更新一下。
在进行匹配的时候，如果当前匹配不上，就给模板串跳父亲节点，直到跳到跟或者能够匹配上为止。
这是比较暴力的做法，对两边都建一遍 SAM。
但是现在我们有了多次询问的区间限制，咋整呢？
可以想到我们实际上是要维护某一个节点所代表的串在一个前缀里面最后出现的位置，再拿它和左端点比较一下就行了。
所以我们干脆对每一个节点维护其出现位置的集合，用线段树合并就可以。
这里线段树合并要魔改一下可持久化，以及有左端点限制之后长度的变化从单调递减变成了可能是先增后减，要判断一下。
linux 编译开无限栈
ulimit -s 512000
1/8
又是被恶心的一天。
本来比赛部分分拿得挺好，赛后改的时候我看见 T2 一个 dp 似乎比较好改，就没管大家都在改 T1。
想的是等大家改完 T1 改 T2 的时候我把我不会的问一问也就过了，改 T1 的时候也有更多的坑可以参考。
结果是一整天都没把 T2 调出来，而且大家没人改 T2？
输，输麻了。
结合之前也是这样，一道题，虽然他有难度，但是首先需要半天思考，然后需要半天写出来。
这样一天写一道题，或者一道题都写不了，感觉效率很低。
但是仔细想一想，之前 Apj 说一道题最多想两个小时。
是不是我思维密度不够且码力不强才导致这样的呢？
啊啊啊恼恼恼
1/10
还是之前的那个题。
太恶心了哥，不想被恶心所以过来推歌了。
为什么说推歌好呢？因为我都是手打歌词，过程中就能够逐渐平静下来。
人间不值得-大柯
渡口爱上深山，
薄雪中意晚莲。
夕阳熬红双眼 想等来晨钟聊聊天。
心上人在梅边柳边，
偏不在身边，
小白蛇浇透临安 许仙却没带伞。
少女压坏秋千，
书生十年落选。
命运总是挑挑拣拣 诸事不成全。
小和尚没化到缘，
又路过烧鸭店。
拈杯酒 眯着眼，
说专心看人间，
看长安 建安 与潘安
都想沾一沾。
神仙掐指算，
此去少圆满，
得来失 聚了散 千万莫求全。
借泥炉 烧碗饭，
在檐上种炊烟，
把小寒 大寒 与心寒
都来暖一暖。
好提胆闯人海，
再探风月关，
兜兜转转，八十一难，
我们走着看。
竹马去寻竹马，
青梅意兴阑珊。
伯牙琴弦摔断 叔夜刚绝交山巨源。
知己半路就散，
结发总另结新欢，
小情侣恰好遇见 喜鹊没来上班。
长生岂能如愿，
古稀尚靠垂怜，
老病倒比莺莺燕燕 多陪二十年。
小嫦娥偷吃灵药，
却反而羡人间。
拈杯酒 眯着眼，
说专心看人间。
看长安 建安 与潘安
都想沾一沾。
神仙掐指算，
此去少圆满。
得来失 聚了散 千万莫求全。
借泥炉 烧碗饭，
在檐上种炊烟，
把小寒 大寒 与心寒，
都来暖一暖。
好提胆闯人海，
再探风月关，
兜兜转转，八十一难，
我们走着看。
人生在世不称意呀，
失眠或失恋。
只劝你来把个盏，
侃呀么侃大山。
喝碗大酒撑条船，
说今生不靠岸，
去天涯海角浪个遍 失意当尝鲜。
这一路手握剑，
身侧有千帆。
时不时，回头看看，
百味是人间。
时不时，也睡个懒觉，
醒来 多加餐。
这首歌属于是为数不多的我会向别人推荐的歌，建议听一听。
那种半白话半戏腔，听起来很仙的感觉。
而且你不觉得歌词也很好么！