20220922考试总结
T1
中规中矩的一道题，但是我的做法比较蠢。
考虑最终那些序列可以成为答案的方式没有问题，但是我考虑的条件是对于 \(a_i\)，大于等于它的数必须多余 \(n-i+1\) 个。这样需要记录的东西是 \(2\) 维的，然后转移还不是优雅的前缀和形式。实际上可以考虑 \(b_i\ge a_i\) 这个条件，也就是多想一想的事，这样的转移可以写成优雅的前缀和。
像这种转化后考虑条件的题，一定要找一个简易的条件去做。
T2
中规中矩的一道状压题。
我考虑直接爆搜联通块，但是这样的做法不是很优雅。转移时其实仅和当前选了哪些点有关，所以其实可以动态规划，做到 \(3^n\)，这种联通块相关的题，一定要考虑联通块之间有没有关系，能不能用动态规划搞定。
T3
中规中矩的一道数据结构优化动态规划的题。
一种比较经典的动态规划优化方式是拿数据结构维护可能的转移，这题本身有着比较优美的性质，可以将对转移代价的贡献拆成两个区间加。
对于修改独立的情况，如果要快速求出答案需要预处理序列，不妨考虑二进制分组。
T4
有意思的二分题。
最大值最小还是可以考虑二分的。
对于这种两者加起来不超过一个数的题，往往可以考虑每个数与 \(\frac{s}{2}\) 的关系。
这种题，显然最终的答案序列是很多个不超过 \(\frac{s}{2}\) 的，中间夹着不超过一个大于 \(\frac{s}{2}\) 的，所以容易证明不超过 \(\frac{s}{2}\) 的数是必选的，如果不选，一定可以调整过去。
然后二分之后需要 check 一下总个数。一个区间中存在合法的大于 \(\frac{s}{2}\) 的数，当且仅当最小值合法。但是如果真的要检查区间最小值个数，那是非常困难的，因为我们需要先得知每个区间的位置，这个位置个数是 \(O(n)\) 的。
所以不妨从合法的数本身的性质考虑，容易发现，合法的数，与它左右两边第一个小于它的数的和一定是小于 \(s\) 的，如果出现相等那么为了避免重复需要设一个第二关键字。
这样就可以做到 \(O(\log)\) check 了，对于两边的边界，可以特判掉。
我们发现需要 check 的东西形如 \([l,r]\) 中 \(\le x\) 的数的个数，这是整体二分擅长处理的东西，所以考虑整体二分，二分的时候将原来的有序组有序的分裂下去，就变成了一维偏序，而且不需要排序（已经有序了）。求左右区间端点也可以类似的做。
对于边界，可以用 ST 表特判，时间复杂度 \(O(n\log n)\)。常数比较大。
整体二分的卡常是有一些技巧的，比如巧妙处理归并，归并的同时分裂数组，通过下标分裂而不是
vector 等。