题解：P14379 【MX-S9-T2】「LAOI-16」摩天大楼

出题人题解。

约定 $\operatorname{mex}$ 的定义域为正整数集合，即 $\operatorname{mex}\{\emptyset\}=1$。

形式化题意：单点修，每次求 $\displaystyle\sum_{l=1}^{n}\sum_{r=l+1}^{n} f(l,r)$，其中 $f(l,r)=1$ 当且仅当存在 $k\in [l,r)\cap \Z$ 使得 $\operatorname{mex}_{i=l}^{k}a_i\not=\operatorname{mex}_{i=k+1}^{r}a_i$，否则 $f(l,r)=0$。

对子区间 $[l,r](1\le l<r\le n)$ 内的数进行分讨：

使得 $f(l,r)=0$ 的情况只有以上两种。

容易得到一段长为 $len$ 的无 $1$ 序列的贡献是 $\frac{len\times(len-1)}{2}$，一段含有 $cnt$ 个 $1$ 的无 $2$ 序列的贡献是 $\frac{cnt\times(cnt-1)}{2}$。

题目要求的是 $\frac{n\times(n-1)}{2}$ 减去所有极长无 $1$ 和无 $2$ 段的贡献。每次修改后求个数是 $\mathcal{O}(n)$ 的，容易做到 $\mathcal{O}(nq)$。

线段树维护区间左侧、右侧极长非 $1$ 段长度，区间左侧、右侧极长非 $2$ 段中 $1$ 的个数即可做到 $\mathcal{O}(q\log n)$，同样可以使用 set 实现。