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 分析 如果只能用操作 $1$，根据某个经典结论答案就是逆序对数。于是很容易想到 $\mathcal{O}(n^3\log n)$ 的暴力：枚举操作 $2$ 交换了哪两个位置，然后求逆序对即可。 考虑优化。因为每次只交换了两个位置，所以没有必要整个重新求一遍逆序对。假设交换了 $i$ 和 $j$，原来的逆序对数是 $A$，那么交换后的逆序对数 $A'$ 为 讨论一下：当 $p_i&l...
Luogu LOJ 分析 首先考虑怎么求出所有交点。 注意到 $a$ 与 $b$ 有交（假设 $y_{a,0}<y_{b,0}$ ）当且仅当 $y_{a,1}>y_{b,1}$ 。 那么可以用 set 来维护 $y_{x,1}$ ，然后暴力求出所有交点。 因为交点个数 $\leq 500000$ ，所以可以过。 容易发现 $a,b$ 的贡献和 $c$ 的贡献是独立的。 先考虑怎...