CF1270H 题解
IsaacX
·
·
题解
Number of Components
联通块数显然很难直接维护，考虑发掘一些性质：连通块必然是 a 上一段区间。
证明：若存在 a_i<a_j，设 k \in (i,j)。分类讨论。
- 若 a_k<a_i，则有 a_k<a_j。(k,j) 连边，所以 k 与 i,j 联通。
- 若 a_k \ge a_i，则 (k,i) 连边，所以 k 与 i,j 联通。
证明完结论后，问题转化为计算 Ans=\sum\limits_{i\in[1,n)}[\min\limits_{j\in[1,i]}a_j>\max\limits_{j\in(i,n]}a_j]。
注意到 a_i\le10^6 且互不相同，考虑统计所有 v=\max\limits_{j\in(i,n]}a_j。如果 v 能够造成贡献（合法），则 v 最多贡献 1，且 v 在序列 a 中出现。
我们对每个 v 生成 01 序列 B(v) ：B(v)_i=[a_i>v]。则合法的 v 生成出来的 B(v) 一定形如：111\dots1100\dots000，即 cnt_{10}(v)=1。
考虑维护每个 cnt_{10}(v)：若 v\in(a_i,a_{i+1}]，则 B(v)_i 处会出现 10。也就是 cnt_{10}(v)=\sum_{i\in[1,n)}[a_i<v \le a_{i+1}]。
我们可以开个线段树维护所有 cnt_{10}(v)，节点上记录区间最小值 mx 以及当前在 a 中出现且是最小值的位置个数 cnt，如果 mx=1，则 ans+=cnt。