根号分治
做法Ⅰ（by me）：对于点数 \(\leq \sqrt{n}\) 的层都预处理两两之间的答案，从上往下处理复杂度为 \(n\sqrt{n}\)，查询只要暴力往上跳直到预处理过的某一层，同样是 \(\sqrt{n}\)
做法Ⅱ（官方）：每 \(\sqrt{n}\) 层分为一块，对于每块中点数最少的层预处理。查询相同。
把 \(r\) 从左往右移，维护所有区间 \([l,r]\) 的答案。考虑 \(r\) 变为 \(r+1\) 时：
1、多出了一个 \(l=r+1\)
2、对于所有最后一个选的数 \(<h[r+1]\) 的 \([l,r]\) 答案加一。满足这个条件的 \(l\) 一定是一段后缀，直接区间加。
强制在线，主席树维护（预处理）即可。询问做法显然。
选出来的每个连通块直径不可能 \(\ge 3\)，因为如果这样，把中间的边去掉一定更优。那么每个被选中的节点要么是中心节点，要么是四周的节点。考虑随机化，钦定每个点的类型，然后跑网络流。随机个 \(4000\) 次差不多了。
November Challenge 2020 Division 1
原文：https://www.cnblogs.com/whx666/p/15217616.html