1.P3920 [WC2014]紫荆花之恋
离线怎么做？考虑把点分树建出来。
在线怎么做？考虑定期重构,暴力查散点，跳点分树查整点。
2.CF1063F String Journey
\(O(n\sqrt{n})\) :观察到答案不超过 \(\sqrt{n}\) ，暴力即可。
\(O(n\log n)\) ：考虑 \(dp_i\) 表示 \([i,n]\) 这个串的答案，则 \(dp_i\le dp_{i+1}+1\) 。
倒着 dp ，每次判断 \(dp_i\) 是否 \(\geq x\) ，只需要做 \(O(n)\) 次判断。
相当于要找到一个 \(j\) 使得 \(j\geq i+x,dp_j\geq x-1,\max(lcp(i,j),lcp(i+1,j))\geq x-1\) 。
注意到 \(i+x\) 单调不增。lcp 利用 SAM 处理，则变成 fail 树上的单点修改，子树 max ，线段树维护即可。
3.P4649 [IOI2007] training 训练路径
注意到没有偶环，相当于每个非树边覆盖的路径，长度是奇数，且两两不交。
如果一个路径 \(i\) 覆盖了一条边，就给这个边染上颜色 \(i\) 。
\(dp_{x,i}\) 表示处理了子树 \(x\) ， \(x\) 到 \(fa\) 染色为 \(i\) ，最大的权值。我们对于每个路径，在 lca 处算贡献。
转移是一个状压 dp 的过程，复杂度 \(O(2^10(n+m)+nm)\) 。
标签：geq,lcp,max,路径,sqrt,杂题,dp From： https://www.cnblogs.com/cwhfy/p/17096613.html