[APIO2018] 新家

求 $\max$ 式的最小值，首先二分答案，问题转化为单点修改，区间查询是否所有颜色都出现过。

二分后这个问题可以归约到三维数点，带上二分是 $O((n+q)\log^3(n+q))$ 的复杂度。

不过显然这个问题是比三维数点弱的，因为查询的是所有颜色是否都出现过，而非求颜色个数。沿用区间数颜色的记每个位置 $i$ 的上一次为该颜色的位置 $p_i$ 的想法，不难发现区间 $[l,r]$ 中所有颜色均出现，当且仅当对于所有颜色有 $p_i\le l$，其中 $i$ 为该颜色在 $r$ 之后第一次出现的位置（为了让每个颜色都出现，需要在序列末尾把每个颜色都添加一遍），当且仅当对于所有 $i>r$ 都有 $p_i\le l$。

所以用线段树维护后缀 $p_i$ 最小值，在线段树上二分即可做到 $O(q\log n)$。