状态开始回暖了，但是还是好菜/kk
134 qoj3998. The Profiteer（背包，分治）
套用决策单调性的分治，查询最优端点的时候二分查找，可以做到 \(\mathcal{O}(nk\log^2 n)\)。
上面的做法是可以优化的：二分的时候把确定的范围直接加入，这样就是 \(\mathcal{O}(nk\log n)\) 的了。
https://qoj.ac/submission/304529
135 qoj1173. Knowledge Is...（贪心）
大力贪心，把所有区间按照 \(l\) 排序，如果能够匹配没有匹配的区间，那么直接匹配。否则，拆一个右端点最小的匹配，然后把当前区间和这个区间匹配。
可以使用线段树维护。但实际上如果一个匹配的左侧区间和右侧区间都能匹配，那么拆左边或者拆右边效果是相同的。
https://qoj.ac/submission/305547
136 qoj5357. 芒果冰加了空气（DP，计数）
考虑对于每个子树构造点分治方案，然后合并。
先考虑 \(u\) 为分治中心的时候连通块大小为 \(1\) 的情况。那么假设子树 \(v\) 中有 \(c_v\) 个连通块与 \(u\) 接触，那么方案数是 \(\binom{\sum c_v}{c_{v_1},c_{v_2},\cdots c_{v_k}}\)。否则，当 \(u\) 的联通块大小不为 \(1\) 的时候，我们可以考虑 \(v\) 的子树中有 \(d_v\leq c_v\) 个联通块层数比 \(u\) 浅，那么方案数就是把 \(c\) 换成 \(d\)。
直接在树上 DP，复杂度为 \(\mathcal{O}(n^2)\)。
https://qoj.ac/submission/306315
137 qoj6101. Ring Road（分治，最短路）
边分治，每次处理跨过两个联通块的最短路。
由于连接两个联通块的边只有 \(\mathcal{O}(1)\) 条，所以把这些边单独提出来跑最短路即可。
138 qoj970. Best Subsequence（贪心，整体二分）
发现如果相邻的两个数都 \(\leq \frac{W}{2}\)，那么它们之间相当于没有限制。可以构造出一组解使得这些数全部被选上。把 \(>\frac{W}{2}\) 的元素选上，只需要在每个连续段选一个最小的即可，施调整法可以证明这样是最优的。
考虑整体二分 \(W\)，从小到大扫描 \(W\)，使用 set 维护 \(\leq \frac{W}{2}\) 的集合以及每个连续段的最小值，用树状数组做区间询问可以求出其中有多少个 \(\leq \frac{W}{2}\) 的元素和 \(>\frac{W}{2}\) 的元素。可以在外层循环 \(30\) 次来达到二分的效果。
139 qoj6638. Treelection
相当于限制除了 \(u\) 之外，其它每个结点不能放超过 \(sz_u-2\) 个票。
先不考虑 \(u\) 的特殊性，考虑贪心，每次把票放在最深的祖先上。维护 \(f_u\) 表示 \(u\) 子树内还有多少票，转移是 \(f_u=\max(\sum f_v-X,0)+1\)，合法条件是 \(f_1=1\)。
假设 \(u\) 的子树也满足 \(sz_u-2\) 的限制，那么 \(u\) 的特殊性被消除，答案只和 \(sz_u-2\) 与最小合法 \(X\) 的大小关系有关，可以二分求出 \(X\)。否则，我们需要额外考虑 \(X=sz_u-1,f_1=2\) 的情况。此时我们需要判断 \(f_1\) 中多出的票能不能删去，合法条件即为对于 \(u\) 的所有祖先 \(anc\) 都有 \(f_{anc}>1\)。
140 qoj6540. Beautiful Sequence（贪心）
钦定集合 \(S,T\) 使得 \(S\) 为满足条件的元素而 \(T\) 不是。
考虑判断合法，将 \(S\) 中元素去重并从大到小排序，\(T\) 中元素从大到小排序，那么合法条件是 \(T_i\leq \min(S_i,S_{i+1})\)（如果不存在元素，则视作 \(-\infty\)）
考虑先钦定 \(S\) 是全集，从 \(S\) 中删去元素使得合法，最终的目标是最小化 \(T\) 中元素个数。注意到最终的 \(T\) 满足 \(|T|=|S|-1\)（\(|T|\) 是可重集），而对于一次删除操作，如果我们删去的元素是最后一个，那么 \(|T|\gets|T|+cnt_u\)，\(|S|\gets |S|-1\)，否则，\(|T|\gets|T|+cnt_u\)。注意到前者是更优的，所以我们会贪心选 \(cnt_u\) 尽量小的元素。所以可以把所有数按照 \(cnt_u\) 排序，从小到大能选则选。可以证明这样是正确的（考虑唯一的问题是我们选了一个出现次数较少但值较大的元素，可能影响后面的判断，但其实可以大力调整）。
暴力实现可以平方，考虑优化判断的过程。注意到我们把 \(T\) 中的元素看作数轴上的一个 \(-1\)，\(S\) 中的元素看做 \(1\)，条件相当于折线始终不会碰到 \(y=0\)。线段树维护即可。
141 2024.1.16 cheer（差分，gcd）
注意到差分之后 \(\gcd\) 不变，考虑差分。差分后一次操作只会改变 \(4\) 个点的权值。
任意选 \(5\) 个点，答案一定是这 \(5\) 个点点权的 \(\gcd\) 的因数。对于它的每个素数因子 \(p^k\) 考虑。分类讨论：
- 没有点不被 \(p^k\) 整除，直接加。
- 恰好 \(2\) 个点被 \(p^k\) 整除，那么只有修改祖先链才有用。
- 恰好 \(4\) 个点被 \(p^k\) 整除，那么只有确定的路径有用。
所以我们只需要考虑 \(\log V\) 条路径的答案，暴力即可。
142 2024.1.17 tree（MST，边分治）
大力 boruvka 可以得到 \(\mathcal{O}(n\log^3 n)\) 做法。
考虑大力优化这个做法。注意到瓶颈在于边分治中的排序，而每次 boruvka 排序的过程是相同的。所以可以直接把分治过程离线，求最短边的部分双指针解决。复杂度 \(\mathcal{O}(n\log^2 n)\)。
143 CF1158E Strange device（树交互，并行操作）
操作明示把树分层。
考虑二分，每次询问出距离 \(l\) 不超过 \(mid-l-1\) 和 \(mid-l\) 的结点，那么可以把点分成 \([l,mid),[mid,mid],(mid,r]\) 三类。
考虑并行，每次找到所有二分的区间，一次把所有奇数或所有偶数的区间割开，可以做到 \(4\log n\) 的操作次数。
然后询问每一层，可以按照模 \(3\) 的余数分层，然后二进制分组一下，然后并行一下，就可以做到 \(3\log n\) 了。
https://codeforces.com/contest/1158/submission/242177866