九条可怜老师吉老师在他的博客中大力赞扬 UR 。
于是博主就决定慢慢把 UR 补完。
希望补完之后能有吉老师十分之一的水平。
UOJ Easy Round #1
A
最小是 \(2\sqrt{n}\)，最大是 \(g+l\)。
用三次根号分治分解 \(g,l\)，剩下的要么相等，要么都是完全平方数。
C
离线，建操作树，用可撤销并查集求解。
Add 是加一个儿子，Delete 是跳到 \(k\) 级父亲，Return 是回到上一步所在位置。
求父亲类似长链剖分用个数组记录动指针。
UOJ Round #1
A
枚举缩进量 \(x\)，当前代码量就是 \(\sum_{i=1}^n\lfloor\frac{a_i}{x}\rfloor a_i\text{ mod }x\)。
显然的整数分块。
B
把 \(x\) 模一个大于 \(x\) 的数不会有任何改变。
故设 \(f[i]\) 表示当前的值为 \(i\)，所有大于 \(i\) 的数都已经放好了的方案数，枚举转移即可。
UOJ Round #2
A
从左往右扫，遇到一个不合法的右括号，就往右找第一个左括号交换。
因为是右边的第一个左括号，所以如果下一次仍然有不合法的右括号，就可以从上次的那个位置开始继续往右找左括号。
C
先套上简单容斥，\(f[i]\) 表示 \(\gcd\) 是 \(i\) 的倍数的方案数。
对树长链剖分，这样就只需要在链合并的时候计算对 \(f\) 的贡献。
朴素的想法维护深度桶，合并枚举 \(i\)，直接求当前链的 \(i\) 的倍数个数和合并链的 \(i\) 的倍数个数。这样复杂度是 \(\sum dep\) 的，不太行。
故考虑根号分治，在加入当前点的时候就直接预处理深度模 \(1\sim B\) 等于 \(x\) 的数的个数，剩下的同上暴力。
复杂度比较玄学，\(B=50\) 可过。
UOJ Round #3
A
不难发现次大公约数就是最大公约数除掉最小质因子。
而最大公约数一定是 \(a[1]\) 的因子。
预处理出 \(a[1]\) 的所有因子之后，对每个 \(\gcd\) 判断即可。
UOJ Round #4
A
当 \(a\geq \sqrt{n}\) 的时候，\(b\) 已经没有用了，两人只能操作 \(a\)，故可以直接 \(O(1)\) 判。
剩下的部分可以直接 DP。
B
把当前剩下的 \(k\) 平均分配给三个数组（如果某个越界了就匀出来一点给别的），然后分别查询，那么查询值最小的那个一定可以被放进去，否则把它退出来，加入别的，别的一定比它大，就不优。
所以可以直接这么搞若干次，每次可以确定 \(\frac{1}{3}k\) 个数，当 \(k\) 足够小的之后就直接暴力即可，可以在次数限制内求得答案。