日记

沟槽的树套树，沟槽的体考。

Two Permutations# Link to

我们发现，$P_i$ 和 $Q_i$ 是绑定的，不会分开。如果 $P,Q$ 都无序十分的难做且 $P,Q$ 的顺序是不变的。我们可以将 $P$ 排序，然后考虑 $Q$。

我们建一个模型：将 $P,Q$ 和与之对应的 $R$ 看作上下两排。如果有 $u < v$，那么就建一条 $u \to v$ 的边。边可以是横着（$P,Q$ 内部建边），也可以是竖着 （$P \to Q$ 或 $Q \to P$）。非法当且仅当出现了环。

我们考虑 $Q$ 中的最大值 $Q_u$。

• 如果 $u$ 是向上建边的起点，说明 $S_u$ 及 $S$ 从 $u$ 开始的后缀都是 $0$，往上建边。因为 $P$ 已经按照从小到大排序了，后面的一定比前面的大。而 $Q$ 这里又是最大值，后面一定比 $Q_u$ 小，那么说明这段后缀都是向上建边。这有什么用？这就说明后面不会成环且 $S$ 确定了，不用考虑了。
• 如果 $u$ 是向下建边的终点，只能说明 $S_u = 1$。但是因为 $Q_u$ 是最大值，所以它的边一定是往左右的，不会成环。

所以我们可以把题意转化成这样：有一个序列 $Q$，每轮可以执行一次两种操作：

1. 把 $Q$ 的最大值 $Q_u$ 及从 $u$ 开始的后缀删掉。
2. 只删掉 $Q$ 的最大值 $Q_u$。

求出删完 $Q$ 的方案数。

结论：答案就是 $Q$ 的上升可空子序列数量。如何理解？我们只考虑操作 1。上升子序列就是一种操作 1 的操作序列。因为每次取走的是一段后缀且 $Q_u$ 是最大值，所以下一个操作的就只能是 $u$ 前面的比 $Q_u$ 小的数。

那有人要问了？操作 2 你没考虑啊？其实也是考虑的。因为是子序列，所以里面可能夹杂着有空位，这些空位就是操作 2 的地方。因为操作 2 的 $S$ 只能是 $1$，方案数是 $1$，所以不用计算。

树状数组优化 dp 即可。

Guess Sequence# Link to

我们对于 $S_i \to T_i$ 建一条边。那么整个图一定是一棵树。如果不是一棵树那么就一定有点没被连边，这个点就可以乱取。

我们考虑对于一个点 $u$，如果 $b_u$ 乘上了 $x$，那么 $b_v$（$v$ 是与 $u$ 相邻的点）为了乘积不变，就得乘上 $\frac{1}{x}$。经过一番推导，我们发现，点 $v$ 的深度与 $u$ 的奇偶性相同，$b_u$ 乘上了 $x$，$b_v$ 也得乘上 $x$，反之乘上 $\frac{1}{x}$。这样我们就把 $n$ 个点分成了两个集合。深度为奇的成一个集合，深度为偶的成另一个集合。

我们发现，如果一个集合的数里有个共同的因数 $x$，那么就可以把当前集合里的的乘上 $\frac{1}{x}$，另一个集合里的就乘上 $x$，可以构造一个新的 $b$，显然不行。所以我们需要把 $a$ 分成两个 $\gcd$ 为 $1$ 的集合，如果可行就是 Yes，反之就是 No。

后日谈 # Link to 后日谈

什么两米八三，我才跳了一米八三。

事情的起因是这样的：我们去体考，考立定跳远。前面的贾皓博第一跳只跳了 $2.4$ 米多。我就在想：是不是成外的测量器具有问题啊？我之前的 $2.6$ 米是不是不真啊？于是第一跳就全力。大概是腿太粗？力量太大？

跑完 $1000$ 米直接燃尽了，整个下午都没法学习。