AGC004E
运动是相对的，显然考虑挪动出口。
假设我们向四个方向最远移动分别是 \(u,d,l,r\)，那么大矩形会从外往内删掉 \(d,u,r,l\)。
而注意到我们这个 \(u,d,l,r\) 框出的范围实质是个矩形，在这个矩形内造成的删除都是相同的，于是整个矩形我们都能走。
因此能救出的机器人一定是矩形内的，但矩形内的不一定能救，可能在之前被删到。
也就是我们需要考虑一个顺序，尝试分讨会发现相当麻烦，跟被删除部分的相交关系不易概括。
于是转而尝试扩展矩形，就可以得到一个四次方的地皮，转移是容易的（把扩展的那一侧加一条进来，注意去掉被删除部分）。
需要 short 卡空间。
P7737
我也会做四年前的 NOI D1T2 了！
首先考虑缩成 DAG，题目的条件画一下就会发现能把 DAG 建成树考虑。
如果没有额外边就是查树链和，如果有一条边能分讨，两条边硬着头皮分讨也能做。
然而如果看错题了就容易想到高妙做法。
考虑 \(k\) 条新加边上的点我们都拉出来，和起点终点一起建出虚树。
考虑暴力一些，把这个虚树还原成 DAG（到目前为止还是树的形态），然后原图可达点就相当于在这个 DAG 上做原问题，缩掉的点可以把权放在覆盖的边上考虑。
考虑附加边，他们显然不会引入虚树上点边之外的可达点组合，于是只会影响虚树上这些点边的可达性，把它们直接作为零权边加入即可。
然后就是暴力了，只需从起点跑正图，终点跑反图，两者都可达就是有贡献的。
CF1801G
考虑预处理出每个 \(t_i\) 结尾的匹配数 \(f_i\)，做个前缀和。
答案显然是 \(f_r-f_{l-1}\) 再减去一些东西，但不太知道是什么东西。
考虑需要减去的一些东西行如 \(x\le l\le y\le r\) 的一个模式串，把它们画出来，发现其实大家都是某个这样的模式串的子串。
很好证啊，总之这就启发我们把某个模式串的子串弄出来考虑，发现只有跟它的一个长度不超过某个值的后缀匹配的其他模式串不需要减。
而这个东西和前面那个 \(f\) 都是可以丢进 ACAM 的，我们只要把每个询问的这个串找出来即可，也就是求出 \(g_i\) 表示 \(i\) 结尾匹配的最长串，然而通过线段树二分找出 \(i-|g_i|<l\) 的最大 \(i\) 即可。