P15534 【MYCOI R1】那猫猫城的集市 题解

第一次 div.2 场切 3 道！
题目大意

给定一棵树，每个点上有一个对换 \(\sigma_i=(a_i b_i)\)。\(q\) 次询问，每次给定 \(u,v,x\)。设 \(u\to v\) 路径上的点分别是 \(u,k_1,k_2,\dots,k_m,v\)，求 \(\sigma_v\sigma_{k_m}\dots\sigma_{k_1}\sigma_u(x)\)，即对路径上对换复合的单点求值。
Solution

注意到对换的逆就是其自身。尝试用类似树上前缀和的方法去做。
拿下面这棵树中 \(u=5,v=7\) 的询问举例。

\[\begin{aligned}&\sigma_7\sigma_6\sigma_3\sigma_4\sigma_5\left(x\right) \\=&\left(\sigma_7\sigma_6\right)\sigma_3\left(\sigma_4\sigma_5\right)\left(x\right) \\=&\left(\sigma_7\sigma_6\color{red}\sigma_3\sigma_2\sigma_1\color{blue}\sigma_1\sigma_2\sigma_3\color{black}\right)\sigma_3\left(\color{red}\sigma_3\sigma_2\sigma_1\color{blue}\sigma_1\sigma_2\sigma_3\color{black}\sigma_4\sigma_5\right)\left(x\right)\\=&\left(\sigma_7\sigma_6\color{red}\sigma_3\sigma_2\sigma_1\color{black}\right)\left(\color{blue}\sigma_1\sigma_2\sigma_3\color{black}\right)\sigma_3\left(\color{red}\sigma_3\sigma_2\sigma_1\color{black}\right)\left(\color{blue}\sigma_1\sigma_2\sigma_3\color{black}\sigma_4\sigma_5\right)\left(x\right)\end{aligned}\]
这样一来，特殊处理 LCA 后我们就拆出了四个前缀对换积，可能是左乘，也可能是右乘。可以维护一个 \(n\) 阶排列表示当前对换积，同时维护其逆，则左右乘对换均可以做到 \(O(1)\)。然后离线下来把询问挂在链的端点，四遍 dfs 即可。
时间复杂度 \(O(n\log n)\)。实现精细的话可以把倍增 LCA 换成 Tarjan，做到 \(O(n\alpha(n))\)。
Code

[code]#include #define rep(i,a,b) for(int i(a);ib;--i)#define rept(i,a,b) for(int i(a);i=b;--i)#define eb emplace_back#define pii pair#define il inline#define gc (p1==p2&&(p2=(p1=buf)+fread(buf,1,1