专栏文章

开车不喝酒，喝酒不开车。老哥不根号，根号不老哥。

llzyqwq
P3992题解参与者 7已保存评论 6

文章操作

快速查看文章及其快照的属性，并进行相关操作。

当前评论
6 条
当前快照
1 份
快照标识符
@miqo9hok
此快照首次捕获于
2025/12/04 08:02
3 个月前
此快照最后确认于
2025/12/04 08:02
3 个月前
查看原文
先锐评一下幽默题解区，一篇自称单根号的题解是假的，另一篇自称单根号的题解没给代码，姑且认为她是变化莫测的。剩下的做法全部带 log⁡\log。所以来一篇正常题解。
先考虑每辆车到哪个加油站。显然是让第 ii 左的车去第 ii 左的加油站。下面给出证明：
假设第 ii 左的车位置为 xx，去的加油站位置为 XX。第 i+1i+1 左的车位置为 yy，去的加油站位置为 YY。如果 X≥YX \ge Y，则交换两车的目的地后：
  • x≤y≤Y≤Xx\le y\le Y\le X：交换前总路程为 X−x+Y−yX-x+Y-y，交换后总路程为 Y−x+X−yY-x+X-y，不劣。
  • x≤Y≤y≤Xx\le Y\le y\le X：交换前总路程为 X−x+Y−y≥X−xX-x+Y-y\ge X-x，交换后的总路程为 Y−x+X−y≤X−xY-x+X-y\le X-x，不劣。
  • x≤Y≤X≤yx\le Y\le X\le y：交换前总路程为 X−x+Y−y≥y−xX-x+Y-y\ge y-x，交换后总路程为 Y−x+y−X≤y−xY-x+y-X\le y-x，不劣。
  • Y≤x≤y≤XY\le x\le y\le X：交换前总路程为 X−x+y−Y≥X−YX-x+y-Y\ge X - Y，交换后总路程为 x−Y+X−y≤X−Yx-Y+X-y\le X-Y，不劣。
  • Y≤x≤X≤yY\le x\le X\le y：交换前总路程为 X−x+Y−y≥y−YX-x+Y-y\ge y-Y，交换后总路程为 x−Y+y−X≤y−Yx-Y+y-X\le y-Y，不劣。
  • Y≤X≤x≤yY\le X\le x\le y：交换前总路程为 x−X+y−Yx-X+y-Y，交换后总路程为 x−Y+y−Xx-Y+y-X，不劣。
因此记第 ii 左的车去的加油站为 pip_i，则 pip_i 单调不降。故第 ii 左的车去的加油站为第 ii 左的。
Q.E.D.\mathcal{Q.E.D.}
那么我们记 ai,bia_i,b_i 均为排过序的数组，则要求单点修改 aia_i，然后对新数组重新排序，求 ∑i=1n∣ai−bi∣\sum\limits_{i=1}^n|a_i-b_i|。
这个比较困难，考虑把每一时刻车所在位置和加油站所在位置上的点 PP 在数轴上表示出来离散化一下，则一共有 O(n+q)\mathcal{O}(n+q) 个点，且每一段路程一定由若干个相邻点构成的线段组成。所以考虑每一条线段的贡献。
记从左至右第 ii 条线段长度为 wiw_i，起点为 PiP_i，终点为 Pi+1P_{i+1}。记 sai\text{sa}_i 表示当前 PiP_i 之前车的数量，sbi\text{sb}_i 表示 PiP_i 之前加油站的数量。则第 ii 条线段会被经过 ∣sai−sbi∣|\text{sa}_i-\text{sb}_i| 次。
因为考虑什么情况下会经过这条线段，显然要求车和加油站分布在她的两侧。不妨令 sai≥sbi\text{sa}_i\ge \text{sb}_i，则对于 j∈[1,sbi]j\in [1,\text{sb}_i] 有 aj,bj≤Pia_j,b_j\le P_i，对于 j∈(sbi,sai]j\in (\text{sb}_i,\text{sa}_i] 有 aj≤Pi<bja_j\le P_i<b_j，对于 j∈(sbi,n]j\in (\text{sb}_i,n] 有 aj,bj>Pia_j,b_j>P_i。因此在两侧的就是 (sbi,sai](\text{sb}_i,\text{sa}_i] 内的这些车和加油站，故被经过 ∣sai−sbi∣|\text{sa}_i-\text{sb}_i| 次。对于 sai<sbi\text{sa}_i< \text{sb}_i 的情况是同理的。
记 si=sai−sbis_i=\text{sa}_i-\text{sb}_i，则对于一次挪车的操作，设其从 PxP_x 挪至 PyP_y，不考虑 x=yx=y。若 Px<PyP_x<P_y，相当于区间 [x,y)[x,y) 内 sai\text{sa}_i 减 11 即 sis_i 减 11。否则相当于区间 [x,y)[x,y) 内 sai\text{sa}_i 加 11 即 sis_i 加 11。
现在问题变成 sis_i 区间加减 1\boldsymbol 1，求全局 ∑i=1m∣si∣wi\sum\limits_{i=1}^m|s_i|w_i，其中 mm 是线段的数量。
考虑以 O(n+q)\mathcal{O}(\sqrt{n+q}) 为块长分块，离线逐块处理。记当前块为 [L,R][L,R]。对于查询把绝对值拆开，对于 si≥0s_i\ge 0 的部分贡献为 ∑si≥0siwi\sum\limits_{s_i\ge 0} s_iw_i，对于 si<0s_i<0 的部分贡献为 −∑si<0siwi-\sum\limits_{s_i<0} s_iw_i。
考虑整块修改。维护辅助数组 si′s'_i 和全局加标记 TT 使得任意时刻 si′+T=sis'_i+T=s_i。
当全局 sis_i 加 11 时，TT 加 11，对于原来 si≥0s_i\ge 0 的部分，∣si∣|s_i| 加 11，贡献增加 ∑si≥0wi\sum \limits_{s_i\ge 0}w_i。对于原来 si<0s_i<0 的部分，∣si∣|s_i| 减 11，贡献减少 ∑si<0wi\sum\limits_{s_i<0} w_i。
当全局 sis_i 减 11 时，TT 减 11，对于原来 si≥1s_i\ge 1 的部分，∣si∣|s_i| 减 11，贡献减少 ∑si≥1wi\sum\limits_{s_i\ge 1}w_i。对于原来 si≤0s_i\le 0 的部分，∣si∣|s_i| 加 11，贡献增加 ∑si≤0wi\sum\limits_{s_i\le 0}w_i。
维护 po=∑si≥0wi,ne=∑si<0wi,cnj=∑si′=jwi\text{po}=\sum\limits_{s_i\ge 0}w_i,\text{ne} = \sum\limits_{s_i<0}w_i,\text{cn}_j=\sum\limits_{s'_i=j}w_i。则当前块对修改后答案相较于修改前增加、减少的贡献可以通过 po,ne,cn−T\text{po},\text{ne},\text{cn}_{-T} 表示出来。同时 po,ne\text{po},\text{ne} 的变化量也可以被 cn−T,cn−T−1\text{cn}_{-T},\text{cn}_{-T-1} 表示出来。注意这里给下标加一个偏移量。注意到 ∣si∣≤n|s_i|\le n，偏移量设为 nn 即可，且 cn\text{cn} 占用的空间为 O(n)\mathcal{O}(n)。
每次整块修改都是 O(1)\mathcal{O}(1) 的，一共进行 O(qn+q)\mathcal{O}(q\sqrt{n+q}) 次，故总时间复杂度为 O(qn+q)\mathcal{O}(q\sqrt{n+q})。
对于散块修改，下放标记然后重构即可。但是重构 cn\text{cn} 的时候不能暴力遍历值域。注意到整块修改不会修改 si′s'_i，因此 cn\text{cn} 中不为 00 的下标只有 sL′,…,sR′s'_L,\dots,s'_R 这些，存储每次的 si′s'_i 并在重构时清空这些位置即可。单次时间复杂度为 O(n+q)\mathcal{O}(\sqrt{n+q})，一共 O(q)\mathcal{O}(q) 次，故总时间复杂度 O(qn+q)\mathcal{O}(q\sqrt{n+q})。
综上，该做法时间复杂度为 O(qn+q)\mathcal{O}(q\sqrt{n+q})，空间复杂度为 O(n+q)\mathcal{O}(n+q)。
AC Link / Code

评论

共 6 条评论，欢迎与作者交流。

正在加载评论...