A
一个序列 \(a\)，你需要对其每个前缀计算：至少要多少次交换相邻元素的操作使得序列变为“单峰”，即由一个递增序列和一个递减序列拼起来。\(n\le 5e5\)。
我一开始的想法是：枚举切点，左边的数排序成递增，右边的数排序为递减，贡献是逆序对+正序对。
然而这是错误，因为不保证左边的某个数去右边不是更优，右边的数也可以去左边。
还是考虑按照逆序对的形式计算贡献，即对于每对相对位置发生改变的数对计算贡献。
考虑把这些数对的贡献放到他们较小的那个去计算。
如果一个数选择到左边，那么要穿过所有左边比他大的数；选择到右边同理。
那么其贡献就是两个的较小值。那么把 \(\min\) 拆掉，二分出取右边的取值范围，剩下的就取左边。
二分考虑主席树上二分；关于取右边的贡献放到较大的数去算贡献。考虑用一个树状数组维护。
主席树的话版本为 \(i\) 就维护 \(\ge i\) 所有数的位置，那么就可以主席树上二分了。
B
\(n\) 个区间，他们要么不交要么包含，你需要给每个区间选一个非空子区间，使得所有子区间都不交，最大化所有子区间长度的和。\(n\le 5000\)。
考虑建出区间树，然后在树上 dp。那么对于一个区间，这个区间的子区间有如下几种选择：
填在儿子区间内；填在其左侧/右侧多出的部分中；填在两个相邻儿子区间的夹缝中。
我们很难通过枚举子区间的位置来决策，因为可以填到儿子区间内部。
所以我们考虑在计算儿子的时候就把区间给选出来，然后做一个树形 dp。
设 \(f_{u,i,0/1,0/1}\) 表示 \(u\) 子树内已经欠了 \(i\) 个子区间在祖先选，当前左/右多出来的区间是否可选。
合并的话先合并儿子假设合并相邻两个区间，那么 \(g_{u,i,p,q}=\max_{j,t}(f_{v_1,j,p,t}+f_{v_2,i-j,t,q})\)。
然后最后算上 \(u\) 的贡献，\(u\) 这里可以选一个子区间，可以插中间，也可以插两端。