Stage 1: Shenyang
A
只需要考虑每个 pair 的贡献即可，而相交的 pair 数量是线性的，因此可以暴力搞，剩下的不相交的 pair 拿前缀和做就行了，复杂度 \(\mathcal O(n\log n)\)。
corner case 是当一方的区间全部退化的时候，需要重新计算一下出现的概率。
B
C
发现长度更长的区间不会更劣，因此一定取到 \(r-l=d\)，进一步地发现 \(l,r\) 中必有一者是 \(a_i\) 中的一个，那么暴力枚举判断即可，时间复杂度 \(\mathcal O(n^2)\)。
更优的做法是，发现每个 \((a_i,a_{i+1})\) 的贡献形如关于 \(l\) 的一次函数，那么做扫描线即可，时间复杂度 \(\mathcal O(n\log n)\)。
D
模拟。
E
首先可以把给定的图中所有边双缩起来，他们直接可以任意连边。现在我们得到一棵树，需要计算有多少种方案，在树上两两点之间连接一些非树边，使得这些边覆盖了所有的树边。
我们可以考虑容斥，钦定一些边不能被覆盖，这样不能覆盖的边断开后，整棵树被分成了若干个连通块，每个连通块内部可以任意连边。这就容易用树形 dp 解决了：设 \(f_{u,i}\) 为 \(u\) 子树，当前连通块大小为 \(i\) 的总和（乘上了容斥系数）。每次转移一条断开的边的时候乘上 \(-1\)，转移一条连上的边的时候乘上 \(2^{ij-1}\)，时间复杂度 \(\mathcal O(n^2)\)。
F
首先，\(n,m\) 同为奇数无解。接下来不妨设 \(m\) 为偶数。
我们发现，如果能构造出一行，恰好一半的连续段是纯色的，那么把这个 pattern 复制 \(n\) 遍显然是合法构造。对于这个问题，我们相当于要构造正整数序列 \(l_1,l_2\dots l_k\)，满足 \(\sum l_i=m\)，\(\sum \frac{l_i(l_i+1)}{2}=\frac{m(m+1)}{4}\)，可以直接从大到小贪心。
G
在线回答问询十分困难，考虑离线，把问询挂在第一棵树的对应节点上。
我们考虑做这样一步转化：在第二棵树的 \(u\) 节点新增一个儿子，到 \(u\) 的距离为 \(dis_1(a,u)\)，那么我们要求的就是 \(dis_2(b,v)\) 的最大值，其中 \(v\) 是任意选定的一个点。容易发现，我们一定会选择直径的一个端点，这就将问题大大简化了：我们现在只需要考虑怎么维护直径即可。
直接任意枚举 \(a\) 的话，树的变化很不规律，我们考虑 dfs 式枚举，每次从 \(fa_u\to u\) 时，子树中的 \(dis_1\) 会减少，子树外的 \(dis_1\) 会增加，可以被表示为 dfs 序上的三段区间修改，再查询直径就很容易了，用线段树维护区间直径，每次 \(\binom{4}{2}\) 个点对进行合并，时间复杂度 \(\mathcal O(n\log^2 n+q\log n)\)，可以用欧拉序 LCA 优化到 \(\mathcal O(n\log n+q)\)，虽然没啥必要。
H
一开始读错题了，还以为是任意两个子串拼起来，结果是任意两个回文子串，那就好做一百倍了。
考虑怎样的回文串 \(P,Q\) 满足 \(P+Q\) 是回文串：当且仅当 \(P\) 和 \(Q\) 的最小循环节相同。
那么我们可以通过 manacher 求出所有本质不同回文子串和最小循环节，用哈希判断即可。时间复杂度 \(\mathcal O(n\log n)\)。
I
先考虑如何解决单组询问：我们假设一开始全都取到 \(b_i\)，那么对于第 \(i\) 种物品，先取会获得 \(a_i-b_i\) 的代价减少，后取代价不变。那么我们显然会按照 \(a_i-b_i\) 先负后正的顺序取。
那么多组询问也很简单了，考虑数据结构，要支持的操作类似：插入，删除，求所有 rank 为奇数 / 偶数的元素之和，可以用平衡树或值域线段树维护。时间复杂度 \(\mathcal O(n\log n)\)。
J
K
L
直接搜索即可，状态数为 \((n!)^2\)。
M
Stage 2: Hong Kong
A
考虑直接上树形 dp，即设 \(f_u\) 为 \(u\) 子树中需要的最少寄存器数量，那么转移就是 \(f_u=\max {f_{v_1},f_{v_2}+1}\)，其中 \(v_1\) 是按照 \(f\) 排序后最大子树，\(v_2\) 是按照 \(f\) 排序后次大子树。
时间复杂度 \(\mathcal O(n)\)。
B
发现黑色连通块数量必定为 \(1\)，因此统计白色连通块的期望数量。
这种题一般比较经典的想法是去统计一些特殊点的数量。在这个题中，观察到每个白色连通块都恰好包含一个右方和下方都是黑色的点，考虑统计这样的点的数量。
枚举每个点 \((i,j)\)，计算其作为上述点的概率。那么概率就是 \((i,j)\) 没被染色，且 \((i+1,j)\) 和 \((i,j+1)\) 均被染色的概率，可以用后缀和计算。时间复杂度 \(\mathcal O(n^2)\)。
C
首先判掉一些显然无解的情况，比如 \(n>2^m,m>2^n\)，\(n,m\) 同时为奇数。
不妨设 \(m\) 为偶数，首先容易用 \(\lceil\log_2 m\rceil\) 行区分这 \(m\) 列，并保持每行每列的 \(0,1\) 个数相等，只需要做一步分治即可。
接下来，我们不需要管列的相等情况了，只需要保持总和恰为一半即可。我们可以选一个串和他的补集，这样总和恰好为一半，不断找这样的没出现过的串加入。对于 \(1\) 个数恰好为 \(\frac{m}{2}\) 的串可以直接放入。
时间复杂度 \(\mathcal O(n^2)\)。
D
既然是 DAG，考虑做一个 dp，设 \(f_{u,i}\) 为走到点 \(u\)，走过 \(i\) 条白边，最少走过几条黑边。如果可以预处理得到 \(f\)，那么查询的时候只需要找到 \(Ai+Bf_{u,i}\) 的最小值即可。
进一步地，如果把 \((i,f_{u,i})\) 当作点放在平面上，可能取到最小值的点集一定是一个下凸壳。那么我们不妨对于每个点维护这个凸包，每次转移就是做凸包的合并。题解说他可以证明凸包点数是 \(\mathcal O(n^{\frac{2}{3}})\)，但是我不是很懂。
每次合并凸包就把所有入点对应凸包的点加进来排个序重新单调栈建凸包即可，时间复杂度 \(\mathcal O(n^{\frac{5}{3}}\log n)\)，但是常数极小，可以通过。
E
补集转化，计算有多少区间包含至少一个恰好出现了 \(k\) 次的数字。
考虑枚举这个数字以及其连续的 \(k\) 次出现，这样的区间数量是 \(\mathcal O(n)\) 的，设这段区间为 \([l,r]\)，\(l\) 左边第一个这个数字的出现位置为 \(l'\)，右边第一个这个数字的出现位置为 \(r'\)，那么左端点在 \([l'+1,l]\) 中，右端点在 \([r,r'-1]\) 中的区间都满足条件。这样就转化为矩形面积并，扫描线即可，时间复杂度 \(\mathcal O(n\log n)\)。
F
发现对于相邻的两段，长度差 \(\ge 2\) 一定不优，因此合法解数量不超过 \(3^k\) （实际上会更少），直接爆搜，用高精度判断即可。时间复杂度 \(\mathcal O(3^kn)\)。
G
计算几何，skip。
H
发现冷却时间一定取 \(l\)，答案即为 \(\lceil\frac{l}{b}\rceil\times b\times k\)。时间复杂度 \(\mathcal O(1)\)。
I
区间平面最近点对。
全局平面最近点对有这样一个神秘做法：考虑增量式，维护当前答案 \(d\)，加入一个新点的时候，以 \(d\times d\) 为单位将平面分成若干个小正方形，每个正方形中的点数是 \(\mathcal O(1)\)，且最近点对一定只会从有公共点的相邻小正方形中取到，因此我们就得到了一个 \(\mathcal O(n)\) （大常数）的平面最近点对做法。
考虑把这个做法搬到区间询问上。这里我们要用到一种很重要的思想：支配点对。大致思路就是，找出 \(<\mathcal O(n^2)\) 数量级的关键点对，使得任意区间问询的答案都来自这些点对。这时候我们就可以直接做扫描线求出区间点对答案了。很多区间点对问询问题都可以用这种思想简化问题。
我们考虑效仿上面那个全局做法：我们现在希望任意 \(d\times d\) 的点对都出现。考虑二进制分组，以 \(2,4,\dots 2^d\) 为边长划分平面，我们发现任意有效点对一定在至少一个边长中作为有效点对出现。那么问题就迎刃而解了：枚举边长后，我们对于同一个块内的点，编号相邻的 \(\mathcal O(1)\) 个加入支配点对，对于相邻的块，编号相邻的 \(\mathcal O(1)\) 个加入支配点对，然后做扫描线即可。现在需要支持 \(\mathcal O(n\log V)\) 次单点修改，\(\mathcal O(q)\) 次矩形查询最小值，可以用线段树做到 \(\mathcal O(n\log V\log n+q\log n)\)，这样我们就惊人地推出了区间最近点对的 polylog 做法。然而在实际运行中，由于前半部分常数太大，我们需要进行根号平衡，用 \(\mathcal O(1)\) 修改，\(\mathcal O(\sqrt n)\) 查询的分块做到 \(\mathcal O(n\log V+q\sqrt n)\)，可以通过。
J
首先，将答案用比较形式化的语言描述出来：我们要求的值即为 \(\frac{1}{n^2}\sum\limits_{i=0}^{n-1}\max(\sum\limits_{j=0}^{n-1}i\oplus j,in)\)。
把 \(\frac{1}{n^2}\) 这个常系数拿走，并且把 \(\max\) 内部同时减去 \(in\)：设 \(f_i=\sum\limits_{j=0}^{n-1}i\oplus j-in\)，那么所求即为 \(\sum\limits_{i=0}^{n-1}\max(f_i,0)+in\)，这时候这个 \(in\) 直接拿走，是个常数。
\(f\) 现在还要枚举 \(j\)，很不容易处理，考虑枚举每个二进制位，计算其贡献次数，得到 \(f_i=\sum\limits_{j}2^jc_jp_j\)，其中 \(p_j\) 表示 \([0,n-1]\) 中有多少个数在二进制下第 \(j\) 位为 \(1\)，容易 \(\mathcal O(\log n)\) 预处理得到；\(c_j\) 表示这位的系数，当 \(i\) 的第 \(j\) 位为 \(1\) 时，\(c_j=-1\)，否则 \(c_j=1\)（这里官方题解写反了，很愚蠢），容易代入验证其正确性。
我们很容易猜测到 \(f_i\) 的同符号连续段不会超过 \(\mathcal O(\log n)\) 个。具体可以考虑出现一个高位的 \(c_j=-1\) 后，想要翻盘变化符号长度至少得将近翻倍。因此如果我们找到了这些区间，计算总和就会简单很多：只需要对非负连续段求和即可。
我们考虑如何找到这样的区间：首先，对于固定的左端点 \(l\)，极长连续段的右端点 \(r\) 一定具有可二分性，那么我们考虑二分，然后判断这个区间是否全部符号相同。判断可以考虑数位 dp，即设 \(mx_{i,j,k},mn_{i,j,k}\) 分别为从高到低填到第 \(i\) 位，\(\ge l\) 和 \(\le r\) 的限制是否已经满足的 \(f\) 最大值和最小值。
接着需要考虑如何对连续区间求和。也可以数位 dp，即设 \(dp_{i,j,k},w_{i,j,k}\) 分别为从高到低填到第 \(i\) 位，\(\ge l\) 和 \(\le r\) 的限制是否已经满足的 \(f\) 的总和和填入总方案数。
时间复杂度 \(\mathcal O(\log^3 n)\)。
K
发现答案不超过 \(mn=\min\{a_i\}\)，能否取到这个上界是容易判断的（利用性质 \(a\mod b\le \frac{a}{2}\)）。当取不到的时候，最大值显然为 \(\lfloor\frac{mn}{2}\rfloor\)，因为瓶颈在于 \(mn\)。
时间复杂度 \(\mathcal O(n)\)。
L
首先判掉显然不合法的情况：\(b\) 不是 \(a\) 的子序列。
最优方案显然是从大到小删除，容易用调整法证明。
现在考虑删除一个数的时候，我们一定会尽量用长度较大的区间，因为这样对于之后的数更有利，他们的限制更容易满足。我们可以从大到小枚举 \(i\)，用 set 维护当前已经比 \(i\) 大的位置集合，容易二分得到 \(i\) 所在的可行区间 \([l,r]\)。
现在找出 \([l,r]\) 中还没被删除的数的数量，可以用树状数组维护，设这个数量为 \(c\)，那么选取的区间长度至少得是 \(c\)，我们可以再维护一个 set，存储当前可行的区间长度集合，每次二分即可。
时间复杂度 \(\mathcal O(n\log n)\)。
标签：frac,log,Cup,Universal,1st,区间,mathcal,考虑,复杂度 From： https://www.cnblogs.com/petitsouris/p/18122367