~~ 如果您认为本文偏短是因为我太颓，那就错了，因为我在写多项式~~
每一个你不满意的现在，都有一个你没有努力的曾经。
陶陶天天“潮”讽我。
测试终于没了，发挥垃圾的一批，不到期望分数一半。不过奖励名额还是没什么问题的。
然后最后这周可能得略微侧重一下实现能力与细节问题。
LCT就不学了（但是已经n次网上模拟赛考了。。）
重点是字符串（广义SAM以及SAM的用法可能得学）和多项式(也就学了不到两周不过感觉很有趣？)
这里并不会更新SAM和多项式，那些会被更新在前面写的专题中。
但是准备复习AC自动机，准确来说是提高一下。（突然想到联赛以前我从来没认真写过什么东西。。。）
[NOI2011]阿狸的打字机
题目背景
阿狸喜欢收藏各种稀奇古怪的东西，最近他淘到一台老式的打字机。
题目描述
打字机上只有28个按键，分别印有26个小写英文字母和’B’、’P’两个字母。经阿狸研究发现，这个打字机是这样工作的：
·输入小写字母，打字机的一个凹槽中会加入这个字母(这个字母加在凹槽的最后)。
·按一下印有’B’的按键，打字机凹槽中最后一个字母会消失。
·按一下印有’P’的按键，打字机会在纸上打印出凹槽中现有的所有字母并换行，但凹槽中的字母不会消失。
例如，阿狸输入aPaPBbP，纸上被打印的字符如下：
a aa ab 我们把纸上打印出来的字符串从1开始顺序编号，一直到n。打字机有一个非常有趣的功能，在打字机中暗藏一个带数字的小键盘，在小键盘上输入两个数(x,y)（其中1≤x,y≤n），打字机会显示第x个打印的字符串在第y个打印的字符串中出现了多少次。
阿狸发现了这个功能以后很兴奋，他想写个程序完成同样的功能，你能帮助他么？
输入输出格式
输入格式：
输入的第一行包含一个字符串，按阿狸的输入顺序给出所有阿狸输入的字符。
第二行包含一个整数m，表示询问个数。
接下来m行描述所有由小键盘输入的询问。其中第i行包含两个整数x, y，表示第i个询问为(x, y)。
输出格式：
输出m行，其中第i行包含一个整数，表示第i个询问的答案。
输入输出样例
输入样例#1：
1 | aPaPBbP |
输出样例#1：
1 | 2 |
说明
数据范围:
对于100%的数据，$n<=100000,m<=100000$,第一行总长度<=100000。
题解
首先我们有一个暴力的思路。
我们建AC自动机的时候顺便记录父节点，这样$B$就可以直接跳父节点完成，$P$相当于对当前的点有个标记，这个标记意味着当前节点代表的串被打印了一次。
然后每个询问怎么搞呢？
假设一个串$x$在$y$中出现，我们只需要枚举每个$y$的前缀，也就是到根的链的每个节点。然后对每个结点跳失配指针进行匹配。
顺便说明一个平凡性质（即废话），假如对于一个字符串$S$的位置$P$,能以$P$结尾匹配到$T$，那么失配指针必然能跳到它，由定义反证即可：
假设节点$T$的长度是$L$ , 由于每次跳的是最大长度，所以如果从一个大的漏掉他跳到一个比他小的，那就不满足定义了。
其实这个性质还是挺重要的。。。
然后获得了70pts的好成绩。正解先咕咕咕，我要看看广义SAM和一个在优化费用流很有用的$Johnson$的$re-weight$算法。
广义后缀自动机
目前看到的所有资料都非常玄学的说只需要每次插入完一个字符串把$la$重置为$root$但并没有说明这样做的正确性和时间复杂度。但是感觉这个东西又非常的强大，所以去集训队论文碰碰运气吧。
Johnson 算法
Task Description:
给定一个无负环带权有向图，我们想要重新赋边权满足
- 所有边权非负
- 任意两点间的最短路径在边权改变后仍然是新图中两点间的最短路径。
直接看应用。
使用Dijkstra优化费用流费用流
SPFA太慢了!费用流中我们是要反复求最短路,为什么每次都要SPFA?
于是我们可以使用Dijkstra来优化费用流.
前提
任何时候残量子图中没有负环,残量子图即由G.E中容量c>0的边的导出子图.
Johnson算法
对于有负权无负环的图的一种在O(VElgV)时间内的APSP算法
算法步骤
1.随便定一个顶点S,调用一次 Bellman Ford 计算出 $h(u) = d(S,u)$
2.构造G’,G’.V=G.V,任何$(u,v,w) in (G.E),(u,v,w+h[u]-h[v]) in G’.E$
3.在G’上跑V次Dijkstra,$d(u,v) = d’(u,v)-h(u)+h(v)$
性质
G’中权值非负,G’中最短路等价于G中最短路
证明
1.权值非负 由三角不等式显然
2.最短路等价 易证对于任何路径$P(u,v)$
$ cost’(P(u,v)) = cost(P(u,v))+h(u)-h(v)$
由上也证明了任何使用顶标的重赋权都能保证最短路等价(其实没证)
算法
类似Johnson算法维护结点顶标$h(u)$
对于任何$(u,v)$保证$h(u)+w(u,v)-h(v) >= 0$,左边仍然是G’中$(u,v)$的权重
初始化$h(u) = 0$,如果有负权则调用一次SPFA得到$h(u) = d(S,u)$
每次增广后所有$h(u) += d’(S,u)$,直到$d’(S,T) = oo$为止
唯一的问题是每次增广后 $h[u]+ = d’(S,u)$ 是否正确的,当然是.
证明
我们只需证明这样能保证任何(u,v),w’(u,v) >= 0
由三角不等式显然 d’(S,v) <= d’(S,u)+w’(u,v)
∴ $d’(S,u)+w’(u,v)-d’(S,v) >= 0$
∵$ w’(u,v) = w(u,v)+h(u)-h(v)$
∴$ d’(S,u)+h(u) +w(u,v) +d’(S,v)+h(v) >=0$
分别令$h(u) += d’(S,u)$新的顶标仍然性质被保持.
由实践在正常情况下$h(u)$不会快速爆$int$.