09-03 题解

比赛地址

补题地址

这回打算改变一下方式, 从写 "怎么做题" 变成 "怎么想题"

T1

什么样的两个 \(a_i\) 能被合并到一个 Bug 上?

很简单 (不过我也想了好一会), mod 2 同余的两个可以合并在一起

为了培养最强 Bug, 肯定不能往上叠负数, 所以上述内容针对序列中的所有正数

确定了选哪些数, 最少的操作步数是确定的, 这里不再赘述

如果序列里没有正数怎么办?

显然只能选一个最大(绝对值最小)的负数(或 0)

但是注意, 对于值相同的若干个下标 \(i\), 他们对应的最小步数可能是不同的 (? 我也不确定)

T2

如果没有 "传送门" 该怎么做 ?

这就变成了简单的数连通块个数, 并查集维护维护

有 "传送门" 呢 ?

这就相当于在连通块之间连上了一些有向边

根据上述思路, 把每个连通块缩成一个点, 确定该点能到达哪些点 (代表着连通块), 查询时看看所有可达的连通块中包不包括终点即可

但是赛时我没有想这么多, 用了原理类似但实现不太一样的方法 : 该连通块内有哪些传送门, 这些传送门又能到达哪些传送门, 所有可达的传送门的出口是否存在和终点在一个连通块里的

T3

翻转一个区间对整个序列的逆序对数有什么影响 ?

区间内部的 "顺序对" "和逆序对" 互换, 区间外不受影响

怎么利用这个信息 ?

这一点我没想到, 所以只打了 \(O(n^2 log\ n)\) 的暴力

序列长度是 2 的幂次, 很适合分治 (形成一棵满二叉树)

对于一个分治区间, 计算他的左半部分对右半部分贡献的顺序对和逆序对

1. 如果翻转在左半边或右半边内部, 那么这部分贡献不变, 向下递归
2. 如果翻转包含了这个区间, 那么逆序对和顺序对的个数交换

暴力做每次询问是 \(O(n\ log\ n)\) 的, 怎么优化 ?

每次翻转的区间是等长的, 他们在分治树上位于同一层

可以先找到包含 \(l_i\) 到 \(r_i\) 的所有块的大区间, 在上面打个标记, 告诉他我在长度 (可用点的深度表示) 等于某某时进行一次翻转

这就要求我们在每一个点上存储他的子树中深度为 \(x\) 的顺序对和逆序对的和

幸好这样做只会增加一个 log, 在 Push_up 时就可以处理出这部分信息

Push_down 中有一些细节, 需要你 (我) 仔细思考一下