20240222A 代码待补
T1
赛时过了，以后再说。
T2
考虑题设是什么。
其实容易发现他的算法正确当且仅当 \(\forall i,f_i=0\cup f_i=f_{i-1}+1\)（显然吧）。
先考虑一个比较本质的做法。枚举 \(f\) 的最大值在哪个位置以及它具体是多少（若有多个只枚举第一个），那么显然我们就能找到一段 \(S[l\sim r]=T[1\sim r-l+1]\)，即我们能确定 \(T\) 的前若干位。由于我们枚举的是最大值，故 \(T\) 的下一位要根据那一段的每次出现受到若干限制，然后剩下就可以乱填了。
然后我们就可以确定整个 \(f\) 长什么样了，这样就有了一个很本质的 \(O(n^3)\) 做法。
注意到固定 \(l\)（就是上文 \(S[l\sim r]\) 的 \(l\)）后，每次 \(r\) 增加到 \(r'\) 只有 \(S[l\sim r']\) 每次出现位置的 \(f\) 会改变，那么先枚举 \(l\) 再从第一个第一次出现的 \(S[l\sim r]\) 开始往右枚举，总修改次数就是 \(O(n^2)\) 的，然后对于每个 \(l\) 求 \(f\) 的初值总复杂度也是 \(O(n^2)\) 的。
据说有复杂度正确的暴力求法，但是我只能想到 sam。
T3
和题目说的一样，把边分成两部分考虑。
第一部分区间连区间可以线段树优化建图然后 dij。
然后后面还是考虑 dij，容易发现差不多是个 \(kx+b\) 的形式，并且从 \(i\) 开始，对于一对 \(i<j<j'\) 必定只有在 \(j\) 已经被标了 \(vis\) 后才可能用 \(i\) 更新 \(j'\)（左边同理）。由于是一次函数可以想到用李超树，那么对于每个 \(j\)，把所有修改全部堆在 \(j\) 一直到给 \(j\) 标 \(vis\) 时再传给左右，这个可以李超树合并。
复杂度 \(O(n \log^2 n)\)，瓶颈在前面的线段树优化建图。