NIT

线段树 一般线段树维护的东西是什么？设其维护的信息的半群 \((A,+)\)，维护标记的半群 \((T,\times)\) 和一种运算 \(*\mapsto A*T\to A\)。 要求 \((b+c)*a=b*a+c*a\)。 一般而言，矩阵是满足这东西的最一般东西，所以线段树一定可以用矩阵搞。 ......

给一个长为 \(n\) 的数组，可以执行以下操作任意次： 选择 \(l, r(1 \leq l < r \leq n)\) ，让 \(\forall i(l \leq i \leq r), a_i = mex(\{a_l, a_{l+1}, \cdots, a_{r}\})\) 。 问最小操作数使得 ......