题解：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) 内的数进行分讨：

  1. 不存在 1。无论区间断在哪里，都满足左区间 \operatorname{mex} 等于右区间 \operatorname{mex}，故 f(l,r)=0。

  2. 在下标 l,r 处为 1。若 [l + 1, r - 1] 不存在 2，则 f(l,r)=0。

使得 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 实现。