JOISC2019 简要题解
官网 AtCoder LOJ 試験 / Examination 三维偏序板子，CDQ 即可。 代码 ビーバーの会合 / Meetings 首先有一个结论：Query(x,y,z) 返回的是三个点两两之间 LCA 中最深的那个。 我们先在 $[1,n)$ 中随机一个点 $y$，然后询问 $(0,y,z)$，即可求出 $0\to y$ 链上的点以及其它点在链上那个点的子树中。 那么直接递归处理链...
官网 AtCoder LOJ 試験 / Examination 三维偏序板子，CDQ 即可。 代码 ビーバーの会合 / Meetings 首先有一个结论：Query(x,y,z) 返回的是三个点两两之间 LCA 中最深的那个。 我们先在 $[1,n)$ 中随机一个点 $y$，然后询问 $(0,y,z)$，即可求出 $0\to y$ 链上的点以及其它点在链上那个点的子树中。 那么直接递归处理链...
LOJ 分析 假设 > 是没有限制的，那么整个序列被 < 划分为若干段。设这些段的长度为 $a_1,a_2,\cdots$，则方案数为 边界为 $dp_0=0$。将 $(-1)^{cnt_{i-1}}$ 提出后分治 NTT 即可。 代码 // =================================== // author: M_sea // website:...