时代的眼泪。

· · 题解

  • 小 L 小 L，小 D CMO 金了，你呢？
  • ……
  • 小 L 小 L，小 Z 考进 HEZ 了，你呢？
  • ……
  • 小 L 不说话，她想哭。虽然她和任意一次哭的事件都有联系，但是她不会哭。因为啊，她是时代的眼泪。

咕了两个月后来补题解。

P6579 [Ynoi2019] Happy Sugar Life / P6774 [NOI2020] 时代的眼泪

  • 给出长度为 n 的排列 (p_1,\dots,p_n)，q 次询问 (l,r,a,b)，求 \sum\limits_{l\le i<j\le r}[p_i<p_j\land p_i,p_j\in [a,b]]。

问题不弱于区间逆序对数，考虑以 \mathcal{O}(\sqrt n) 为块长分块。

对于一次询问，可以将答案划分成以下几个不交的部分：

考虑分别计算这些贡献。

Case 4 & 5

以 Case 5 为例，枚举散块内的位置 j，则 i 来自一个区间 [L,R]。问题变成求区间内有多少个值域在 [a,b]\cap[1,p_j) 内的数。考虑前缀差分再离线扫描线，此时一共有 \mathcal{O}(n) 次修改，\mathcal{O}(q\sqrt n) 次查询，维护值域的前缀个数，使用 \mathcal{O}(\sqrt n) 修改 \mathcal{O}(1) 查询的分块即可。

注意到有 \mathcal{O}(q\sqrt{n}) 次查询，但是她们来自于 \mathcal{O}(q) 个询问，即只有 \mathcal{O}(q) 种本质不同的查询参数 (L,R,a',b')。因此可以考虑将前缀询问挂在右端点上时再额外存储该散块内的下标区间，查询时再枚举区间内的元素，这样空间复杂度是 \mathcal{O}(n+q)。

时间复杂度为 \mathcal{O}((n+q)\sqrt n)。

Case 1

记这个散块为 [L,R]，其所属整块为 [l',r']。

拆贡献，可以转化为下标在 [l',R] 内、值域在 [a,b] 内的贡献，减去下标在 [l',L-1] 内、值域在 [a,b] 内的贡献，再减去 i\in[l',L-1],j\in [L,R],a\le p_i<p_j\le b 的贡献。

第三种可以和 Case 4 & 5 一样处理。至于前两者，形式都是某个散块前缀 [l',x] 内的贡献。记 k_x 表示 [l',x) 中 且值域在 [a,b]\cap [1,p_x) 的贡献。则一个散块前缀的贡献为其内所有 k_x 之和。

考虑枚举每个位置 x，然后枚举她所在散块内的每个询问，若询问区间包含了 x 则将对于询问的答案贡献上 k_x。考虑再维护一个 \mathcal{O}(\sqrt n) 修改 \mathcal{O}(1) 查询的分块，扫描到 x 时维护前缀 [1,x) 内的值域前缀个数，那么每次扫描只需要在查询结束后加入 x 的信息。我们考虑先做完所有散块询问再处理 Case 4 & 5 中的询问，因此在处理散块询问时，Case 4 & 5 中的分块仍然保留着 x 所在块之前的信息，拿在两个分块中查询得到的前缀信息差分一下即可得到 k_x。

由于散块总共 \mathcal{O}(q) 个，而每个询问被其散块所属的整块内的 \mathcal{O}(\sqrt n) 个位置枚举到，因此时间复杂度为 \mathcal{O}((n+q)\sqrt n)。

Case 2

离线，逐块处理。

对块内元素离散化（某种元素 x 的离散化值定义为块内小于等于她的元素个数），则只会出现 \mathcal{O}(\sqrt n) 种值。记 f_{u,v} 表示 i<j 且 p_i 离散化值在 [1,u] 内、p_j 离散化值在 [1,v] 内的贡献。这个二维前缀和一下就好。单次时间复杂度为 \mathcal{O}(n)。

枚举每个查询，若她包含了整个块，则先得到原值域 [a,b] 所限制的离散化值的值域 [a',b']，则要求 p_i,p_j 离散化值在这个范围内的贡献，差分为 f_{b',b'}-f_{a'-1,b'}-f_{b',a'-1}+f_{a'-1,a'-1} 即可。

时间复杂度为 \mathcal{O}((n+q)\sqrt n)。

Case 3

记一个询问对应的整块编号区间为 [L,R]。

拆贡献，转化为下标在 [L,R] 的块内、值域在 [1,b] 内的贡献，减去下标在 [L,R] 的块内、值域在 [1,a) 内的贡献，再对于每个 [L,R] 内的块 B，减去 [L,B) 的块内值域在 [1,a) 的位置和 B 中值域在 [a,b] 内的贡献。

前两类贡献的形式都是一段块间在某个前缀值域内的贡献。考虑扫描这个值域 [1,v]，记 s_{l,r} 表示 [l,r] 这段块间的贡献，再记 c_x 表示块 x 内值域在 [1,v] 内的元素个数。记 v 这个值所在块为 m，则对于 m 右边的块 r，s_{m,r} 无变化，因为 v 是当前最大值不存在这个位置后面的元素和她构成顺序对。对于 m 左边的块 l，她和块 m 之间的贡献增加 c_l，对应的 s_{l,m} 增加 \sum\limits_{x\in[l,m)}c_x。从 m-1 往左扫描 l，维护 y=\sum\limits_{x\in[l,m)}c_x，然后给对应的 s_{l,r} 加上 y。

对于第三类贡献，只要维护块 B 前 [1,a) 内的元素个数。可以在做 Case 2 的时候，对于每个询问 t 维护 \text{cnt}_t 表示 [L,B) 的块内 [1,a) 内的元素个数。而我们的离散化值就是前缀值域个数。因此差分出区间内的值域个数然后乘上 \text{cnt}_t 即为这一块的贡献。最后再让 \text{cnt}_t 加上 B 内对应值域内的元素个数即可。

时间复杂度为 \mathcal{O}((n+q)\sqrt{n})。

做完了。

总时间复杂度为 \mathcal{O}((n+q)\sqrt{n})，空间复杂度为 \mathcal{O}(n+q)。

AC Link / Code