生成膜咒
题里面的定义就是 (border)，求所有子串的每个前缀的 (border) 的和，深度就是 (border) 的个数
考虑添加一个字符对答案的贡献就是它对应的每个后缀的 (border) 的个数
转到 (SAM) 上发现如果当前 (endpos) 集合的大小大于 (1) 那么对答案就有 ((len_x-len_{fa[x]}) imes (sz[x]-1))
离线搞出来后缀树，树剖线段树进行链加和查询增量即可
在线就是 (LCT)，复杂度还少 (log)
simulate
这题主要是考虑每个点的减少带来的连锁反应，具体而言，设当前点为 (i)，([1,i-1]) 的所有数已经小于 (2)，同时用栈来维护所有 (0) 的位置
分两种情况
-
(a[i-1]=0)：对应将这个点减少 (1)，栈顶弹掉，(a_{i+1}) 增加 (1)
-
(a[i-1] eq 1)：手玩一下发现情况是 (st[top]) 右移，(a_{i+1}) 增加 (1)，(a[i]) 减少 (1)
所以模拟即可，真的不超过联赛难度吧，没做出来真的不应该吧
circle
首先如果钦定的 (k) 个点有环，那么直接 (impossible)
有一个结论：强连通竞赛图必然存在不小于 (3) 元环，归纳可以证
那么需要删掉所有的三元环，(60') 的暴力就是 (Theta(n^3)) 找环
考虑图上三元环的构成，合法的只能是两个被钦定或者一个被钦定（三个钦定的就不是 (DAG) 了，三个没有被钦定的无环是题设）
一个没有被钦定的直接删掉，最后需要考虑的就是两个被钦定的删哪个
设不被钦定点 (x) 向被钦定点连边的序列 (S)，(S_i) 表示 (x) 向被钦定点中拓扑序为 (i) 连边的方向，(A) 表示指向，(B) 表示被指向
如果有 (B) 在 (A) 后面出现，那么这个点必删
考虑剩下的点的 (B) 和 (A) 的分界线位置，共存问题就被转化成了二维偏序
时间复杂度 (Theta(n^2))