CCO '21

「CCO 2021」换换排序

题意转化为: \(Q\)次查询数组中两个值之间形成的逆序对数.

这个问题可以利用双指针在\(O(\#a+\#b)\)时间内解决, 且贡献是对称的.

考虑根号分治, 对于\(\#a\ge B\)的值, 利用\(O(n\cdot \#a)\)时间求出对所有数的逆序对个数.

对于其余部分, 每次询问时间是\(O(B)\) 的.

时间可以做到\(O(n\sqrt Q)\)

空间: 在线\(O(n\sqrt n)\), 离线\(O(n)\).

「CCO 2021」在黑暗中走出另一个迷宫

考虑如果每一个指针都指向父亲, 移动的过程就是Euler Tour.

考虑到当每个点被第一次访问到以后, 回溯时一定会把指针指向它的父亲.

模拟这个让整棵树逐渐变得"合法"的过程: 每访问一个"不合法"的节点, 对在指针顺时针方向的节点都进行访问(按照dfs序), 然后回溯. 而剩下的节点一定会在下一轮从根出发时被第一次访问到.

于是直接进行dfs, 每次dfs顺时针方向的儿子, 把其他的儿子加入一个队列中, 依次处理, 可以得到每一个点最早访问到的轮数.

于是问题转化为在欧拉序上不断插入, 查询第k大.

时间\(O(n\log n + Q)\).

「CCO 2021」商旅

首先对没有出度的点递归删除, 去除无解情况.

现在考虑最大边权的边\(e\), 如果它是\(e.u\)的唯一出边, 则\(e.u\)的答案一定是\(e.r\). 删掉这条边, 并递归删除无出度的点和它连的边. 删除边\(e\)时, \(\mathrm{chkmin}(Ans_{e.u}, \max(e.r,Ans_{e.v}-e.p))\).

如果它不是唯一出边, 这条边一定不对答案造成影响, 直接删掉.

对于残余图重新进行这个操作即可. 注意唯一出边时用\(\mathrm{chkmin}\), 不要直接赋值, 因为可能再递归删除时得到了更小的答案.