2025 ICPC WF

考虑根被插入的时间，在根被插入之前的数都会放到同一个儿子，插入之后的数会交替往两边插入，形式一定形如 $\texttt{LLLLXRLRL}$ 或 $\texttt{RRRRXLRLRL}$，这样我们就递归到了儿子的子问题。合并的时候分类讨论一下 $sz_{ls}$ 和 $sz_{rs}$ 的大小关系，暴力合并的复杂度只有 $O(\min(sz_{ls},sz_{rs}))$，时间复杂度 $O(n\log n)$。

每走一步就能得到走的方向和其他空地方向的优先级关系，暴力维护有没有出现环就做完了。$O(rc+|s|)$。

题目相当于每次连 $(a+n,b)$ 的双向边，询问有多少 $(u,v)$ 满足有 $x\in\{u,u+n\},y\in\{v,v+n\}$，$(x,y)$ 连通。

考虑并查集合并的时候启发式合并连通块的颜色数，然后我们先认为答案是每个连通块的 $\binom{sz}2$ 的和，这样只有一个点对在两个连通块同时出现的时候才会算重，考虑维护这样的点对个数。

合并两个连通块 $S,T$（$|S|\ge|T|$） 的时候，首先个数要减去 $\binom{|S\cap T|}2$，然后对于 $x\in T,x\notin S$，如果 $x$ 在第三个集合 $U$ 中出现，个数要加上 $|S\cup U|$。由于每个数只出现两次，可以离线下来把每个相同的数对放在平面上 DFS 序对应的点二维数点。时间复杂度 $O(n\log^2n+m\log n)$。

按 $p$ 从大到小贪心考虑，$p$ 的位置必定填的是一个所有猫的位置集合的交中的数，如果交中所有数都已经在更大的 $p$ 中出现过或者不同的数已经超过 $m-p+1$ 个那就不合法，否则显然存在方案。时间复杂度 $O(n+m)$ 或 $O(n+m\log m)$。

考虑小凯的疑惑，设 $g_i=\gcd(a_1,\dots,a_i)$，所有 $kg_n+\sum\limits_{i=2}^n[g_{i-1}\nmid a_i]g_{i-1}a_i$ 肯定能被表示出来，这个东西只有 $O(V^2)$。如果 $m$ 只有 $O(V^2)$ 这个级别就暴力，否则数位 DP 算所有 $g_n$ 的倍数。$O(V^2+V\log m)$。

首先对于每个 $i$ 做 $n$ 次 $(i,1)$ 尝试让 $k$ 增加，这样可以使序列变成一个排列。

对于 $i\in[1,n-1]$，我们尝试确定 $a_1-i$ 的位置。我们把 $a_2\sim a_n$ 都 $+i$ 之后 $k$ 显然是 $n-1$，然后序列中没有 $a_1+i$，对每个 $j$ 询问 $(j,i)$ 即可检查他的值是不是 $a_1-i$。询问次数大约 $3n^2$。

首先我们需要 $k\in[2n-1,n^2]$。打表发现 $k\ne n^2-2$。

考虑递归构造，如果 $k\le4n-4$ 就把 $n$ 放在最下面，否则放在最上面，这样在 $n$ 足够大的时候 $k\in[2n-1,n^2]\setminus\{n^2-2\}$，$n\le 10$ 的时候暴力全排列。$O(n)$。

我们需要 $d_{i,j}+d_{i+1,j+1}-d_{i+1,j}-d_{i,j+1}=0$。我们可以把这些等式随意加起来，这样就是“一个环，每个点都是直角，奇数位和等于偶数位和”的限制。对每个行列赋权使得 $f_i+d_{i,j}=g_j$，要求 $\max f_i\le\min g_j$，连边 DFS 讨论一下即可。$O(n+m+k)$。

往下走肯定是直着往下走，差分覆盖一下能躲太阳的 $y$。$O(n+V)$。