定义一个不会自己暴动的人 $i$ 会被 $lst(i)$ 个人影响导致暴动，那么发现题目中所有的区间 $[lst(i),i]$ 之间都只有两种关系：包含和不相交。

这个结论十分好证明，不妨假设 $\exists i,j\in[1,n]\cap\mathbb{Z}$ 满足 $lst(i)\le lst(j)\le j\le i$，那么显然根据定义 $lst(i)=lst(j)$ 也就不存在不包含但是相交的关系了。

假设

$[lst(i),i]\subseteq[lst(j),j]\wedge\nexists k\mid [lst(i),i]\subseteq[lst(k),k]\vee [lst(k),k]\subseteq[lst(j),j]$

那么将 $i$ 设为 $j$ 的儿子。

显然这样建出的森林如果选择叶子节点，那么注定从根节点到叶子节点都不会出现暴动，直接使用长链剖分维护就可以了，时间复杂度为 $O(n\log n)$。

收获：优化 DP 不一定只能是 DP。