题解：P6579 [Ynoi2019] Happy Sugar Life

Eterna · 2025-11-24 20:05:00 · 题解

区间查询某值域内的顺序对数。

对于所有点 (i,a_i) 建立平面直角坐标系如下：

现在我们要计算部分 (1,2,3,4) 的答案 s_{1,2,3,4}。

可以变为 s_{1,2,3,4}=s_{1,2}+s_{3,4}+s_{1,3}+s_{2,4}+s_{1,4}+s_{2,3}-s_{1}-s_{2}-s_{3}-s_{4}。

对于更多行列的情况，答案为每行答案加每列答案加行列均不同的两部分构成的答案减去每个部分的答案。

考虑树套树的结构，则一次询问在序列和值域上均被划分为 \mathcal{O}(\log n) 层。

1. 对于每行答案或每列答案显然可以用相同的方法求出，以每列答案为例：

   可以对于每列将询问挂在行上，每次列上的询问相当于区间顺序对。

   这样，对于行上的树结构，每一层都有 \mathcal{O}(m) 个询问。

   考虑使用莫队二次离线解决。则复杂度为 T(n)=2T(n/2)+\mathcal{O}(n\sqrt{m})=\mathcal{O}(n\sqrt{m})。

2. 对于行列均不同的答案。显然，若这个行列均不同的两部分顺序是对的，将两部分点的数量相乘即可。

3. 对于每个部分的答案。考虑使用线段树合并计算，然后每组询问可以直接 \mathcal{O}(\log^2 n) 枚举。

于是我们在 \mathcal{O}(n\sqrt{m}+m \log ^2 n) 的时间复杂度内解决这个问题。

tips：对于莫队二次离线，我们将其中扫描线的复杂度略去。因为扫描线部分可以 o(n\sqrt{n})。且 \mathcal{O}(n\sqrt{n}) 在这题本身就小于 \mathcal{O}(n\sqrt{m})。