给定一张图，$q$ 个询问，每次询问只考虑图中 $s_i$ 个点构成的连通块数。数据保证 $\sum s_i\le 10^5$。
考虑分块。当 $s_i\lt k$ 时暴力 $O(s_i^2)$ 枚举所有点对同时维护并查集。 $s_i\ge k$ 时暴力 $O(m)$ 枚举所有边同时维护并查集。
从均摊复杂度考虑，消耗每点 $\sum s_i$ 的复杂度为 $O(\max(\cfrac {s_i^2}{s_i}(s_i\lt k),\cfrac m{s_i}(s_i\ge k))\log s_i)=O(\max (k,\cfrac mk)\log k)$。
取 $k=O(\sqrt m)$ 时总时间复杂度为 $O(\sum s_i\sqrt m\log m)$。
给定一个不可重集，求最大子集满足子集中数构成等差数列。
先将不可重集排序得到序列 $A$，然后令 $\text{dp}(i,j)$ 表示等差数列最后一项为 $a_j$ 且倒数第二项为 $a_i$ 时的等差数列的长度。
考虑枚举 $i$，同时双指针 $k\lt i\lt j$ 查找满足 $a_k+a_j=a_i$ 的数，有状态转移 $\text{dp}(i,j)=\text{dp}(k,i)+1$。时间复杂度 $O(n^2)$。
给定一棵树，树上每点有一种颜色。接下来两种操作：
将无根树转为以 $1$ 为根的有根树，同时处理得到每个点的 $\text{dfs}$ 序。
不难发现，对颜色为 $c$ 的结点的最小子图的边数等价于所有该颜色结点所有 $\text{dfs}$ 序相邻结点距离加上 $\text{dfs}$ 序最大最小两点距离和除以 $2$。
考虑 $\text{set}$ 维护即可，时间复杂度 $O((n+q)\log n)$。
给定 $n$ 个事件，时间分两种：
接下来 $q$ 个询问，每次询问当初始时有 $b$ 辆车时所有人的等待时间和。
先假设初始时没有车，考虑根据初始事件构造“时间 $-$ 等待人数”图，则答案恰好为该图形围成的面积。
考虑初始时有 $b$ 辆车的情况，易知这等价于将图形向下移动 $b$ 个单位，同时删去小于 $0$ 的部分。
不难发现这同时等价于直线 $y=b$ 与原图形上方曲线围成面积。考虑将询问根据 $b$ 排序，利用扫描线法维护答案，时间复杂度 $O(n\log n)$。
需要注意无解情况的特判。另外发现也可以吉司机线段树区间置 $\max$ 再询问 $\text{sum}$ 无脑维护。