A.钢琴教室
线段树二分板子题，对于 \(a_i<i\) 的将 \([a_i+1,i]\) 区间加一，查询的话线段树上二分即可。
B.丰雪千里祥音颂
[PA2019] Terytoria，今年终于会写了。
钦定某一条边必走，这样状态都确定了，枚举这条边，线段树维护最大值个数即可。
C.不连续子串
所有非空子序列的非空子序列个数和。
有点厉害，显然要 \(dp\)，我们钦定钦定一种子序列在最左的出现位置处统计到。
设外层子序列为 \(S\)，内层子序列为 \(T\)，\(f_i\) 为考虑到第 \(i\) 位且钦定 \(i\) 在 \(T\) 内的答案。
枚举 \(T\) 的上一个位置 \(j\)，考虑将 \((j,i)\) 中的数填入 \(S\) 的方案数，有以下限制：
- \(\forall p\in(j, i),a_p = a_i\), \(a_p\) 不能选 (不然不是 \(T\) 中最左)
- 令 \(l\) 为最大的 \(p\in(j, i)\) 使得 \(a_p = a_i\), 必须 \(∃q\in(l, i)\) 的 \(a_q\) 选入 \(S\) (不然该方案应在 \(l\) 处被统计)
- 对 \(S\) 中每相邻两个数 \(p,q\), 要求 \(∀k∈(p, q),a[k]\neq a[q]\) (不然不是 \(S\) 中最左)
复杂度 \(O(n^2)\)
D.复读机
设当前二分答案为 \(v\)，我们将 \(\le\lfloor\frac{v}{2}\rfloor\) 的称为小数，反之称为大数。
小数可以连着选，都选上就好，唯一要考虑的是两个相邻小数之间能不能添上一个大数，所以我们可以用 \(\text{set}\) 在 \(O(n\log n)\) 的时间内求出若干四元组 \((i,j,l,r)\) 表示 \(v\in[l,r]\) 时，\((i,j)\) 有 \(1\) 的贡献，差分完后就变成了三元组。
对值域进行扫描线后就变成了单点加，然后把所有的询问放一块整体二分即可，复杂度 \(O(n+q)\log^2n\)，可以变成 \(O(n+q)\log n\)，但是我不会。