3635.六元组
题解 1
形式化一下原题要求:
a,b,c∑[xb∈[la,ra]][xc∈[lb,rb]][xa∈[lc,rc]]
考虑先进行容斥,将原题降落限制转换为 [xi∈[li,ri]]=[xi≤ri]−[xi≤li−1],这个时候每架飞机被我们拆成两架,并将符号看成容斥系数,也就是变成 (xi,ri,+1) 和 (xi,li−1,−1),为了方便,我们看三个都是 ri 的情况:
a,b,c∑[xb≤ra][xc≤rb][xa≤rc]⋅wa⋅wb⋅wc
按照 r 从小到大枚举 a,此时我们关心所有 xb≤ra 的 b,将其放进数据结构中,对于每一个加入的 b,会对所有 xc≤rb 造成 numb 的贡献(即b 位置的飞机数量),定义 wc=∑b 已加入[xc≤rb]⋅numb。
每加入一个 b,就要对所有满足条件的 wc 加 numb,也就是前缀加法。
统计答案时,要考虑所有 xa≤rc 的 c,并将答案 ans←ans+∑xa≤rcwc⋅numa⋅numc。
最后一步就是维护 wc,需要一个数据结构支持前缀加法和区间求和,使用分块维护或者线段树即可。
题解 2
别看题目叫六元组,实际只跟飞机 a,b,c 有关,因为他们两端确定了机场标号。
也就是我们只要统计有多少个三元组 (a,b,c),使得 xa,xb,xc 互不相同并且有包含关系。
由于三个位置的大小不固定,也就是有 6 种可能性,我们先来考虑 xa<xb<xc 的情况。
这种时候条件变为 xa∈[lb,rb],xb∈[lc,rc],xc∈[la,ra]。
考虑固定 c 进行计数,我们需要统计所有满足 xa∈[lc,rc] 并且存在 xa<xb<xc 的 a 的数量。
考虑如何预处理存在中间 b 的数量,令 F(a,c) 表示 a 经过两次飞行到达 c 的方案数,那么答案即为 ∑xa∈[lc,rc]F(a,c)。
可是 F(a,c) 在每次 c 变化时会发生改变,我们需要一种快速计算的方式。
没错,没啥好办法,没有好办法不如想想分块()
我们将飞机按照位置排序,分成大小为 len 的块,对于每个块我们预处理出 f[k][i][p] 表示从第 i 块内任意飞机出发,经过 k 次飞行到达位置 p 的方案总数,具体预处理:
- 当 k=0 时,自身贡献为 1。
- 当 k=1 时,将第 i 块内的每个飞机 a 对应的区间 [la,ra] 加 1。
- 当 k=2 时,由于要飞两次,我们可以从 f[1][i][p] 的基础上开始飞,也就是把第 i 个块的 f[1][i][b] 加到 [lb,rb] 上。
这个预处理复杂度为 O(nn)。
现在扫描线 c,对于当前位置我们要求出 ∑xa∈[lc,rc]F(a,c),直接把 c 按照整块用 f[2],剩下的暴力计算即可。
暴力计算时,枚举每个位置作为 a,我们要求出 xb∈[la,ra] 的 b 的数量,可以通过树状数组维护,具体的,对每个 b 的 lb,rb+1 标记 +1,−1 即可。
