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

· · 题解

先锐评一下幽默题解区，一篇自称单根号的题解是假的，另一篇自称单根号的题解没给代码，姑且认为她是变化莫测的。剩下的做法全部带 \log。所以来一篇正常题解。

先考虑每辆车到哪个加油站。显然是让第 i 左的车去第 i 左的加油站。下面给出证明：

假设第 i 左的车位置为 x，去的加油站位置为 X。第 i+1 左的车位置为 y，去的加油站位置为 Y。如果 X \ge Y，则交换两车的目的地后：

因此记第 i 左的车去的加油站为 p_i，则 p_i 单调不降。故第 i 左的车去的加油站为第 i 左的。

\mathcal{Q.E.D.}

那么我们记 a_i,b_i 均为排过序的数组，则要求单点修改 a_i，然后对新数组重新排序，求 \sum\limits_{i=1}^n|a_i-b_i|。

这个比较困难，考虑把每一时刻车所在位置和加油站所在位置上的点 P 在数轴上表示出来离散化一下，则一共有 \mathcal{O}(n+q) 个点，且每一段路程一定由若干个相邻点构成的线段组成。所以考虑每一条线段的贡献。

记从左至右第 i 条线段长度为 w_i，起点为 P_i，终点为 P_{i+1}。记 \text{sa}_i 表示当前 P_i 之前车的数量，\text{sb}_i 表示 P_i 之前加油站的数量。则第 i 条线段会被经过 |\text{sa}_i-\text{sb}_i| 次。

因为考虑什么情况下会经过这条线段，显然要求车和加油站分布在她的两侧。不妨令 \text{sa}_i\ge \text{sb}_i，则对于 j\in [1,\text{sb}_i] 有 a_j,b_j\le P_i，对于 j\in (\text{sb}_i,\text{sa}_i] 有 a_j\le P_i<b_j，对于 j\in (\text{sb}_i,n] 有 a_j,b_j>P_i。因此在两侧的就是 (\text{sb}_i,\text{sa}_i] 内的这些车和加油站，故被经过 |\text{sa}_i-\text{sb}_i| 次。对于 \text{sa}_i< \text{sb}_i 的情况是同理的。

记 s_i=\text{sa}_i-\text{sb}_i，则对于一次挪车的操作，设其从 P_x 挪至 P_y，不考虑 x=y。若 P_x<P_y，相当于区间 [x,y) 内 \text{sa}_i 减 1 即 s_i 减 1。否则相当于区间 [x,y) 内 \text{sa}_i 加 1 即 s_i 加 1。

现在问题变成 s_i 区间加减 \boldsymbol 1，求全局 \sum\limits_{i=1}^m|s_i|w_i，其中 m 是线段的数量。

考虑以 \mathcal{O}(\sqrt{n+q}) 为块长分块，离线逐块处理。记当前块为 [L,R]。对于查询把绝对值拆开，对于 s_i\ge 0 的部分贡献为 \sum\limits_{s_i\ge 0} s_iw_i，对于 s_i<0 的部分贡献为 -\sum\limits_{s_i<0} s_iw_i。

考虑整块修改。维护辅助数组 s'_i 和全局加标记 T 使得任意时刻 s'_i+T=s_i。

当全局 s_i 加 1 时，T 加 1，对于原来 s_i\ge 0 的部分，|s_i| 加 1，贡献增加 \sum \limits_{s_i\ge 0}w_i。对于原来 s_i<0 的部分，|s_i| 减 1，贡献减少 \sum\limits_{s_i<0} w_i。

当全局 s_i 减 1 时，T 减 1，对于原来 s_i\ge 1 的部分，|s_i| 减 1，贡献减少 \sum\limits_{s_i\ge 1}w_i。对于原来 s_i\le 0 的部分，|s_i| 加 1，贡献增加 \sum\limits_{s_i\le 0}w_i。

维护 \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。则当前块对修改后答案相较于修改前增加、减少的贡献可以通过 \text{po},\text{ne},\text{cn}_{-T} 表示出来。同时 \text{po},\text{ne} 的变化量也可以被 \text{cn}_{-T},\text{cn}_{-T-1} 表示出来。注意这里给下标加一个偏移量。注意到 |s_i|\le n，偏移量设为 n 即可，且 \text{cn} 占用的空间为 \mathcal{O}(n)。

每次整块修改都是 \mathcal{O}(1) 的，一共进行 \mathcal{O}(q\sqrt{n+q}) 次，故总时间复杂度为 \mathcal{O}(q\sqrt{n+q})。

对于散块修改，下放标记然后重构即可。但是重构 \text{cn} 的时候不能暴力遍历值域。注意到整块修改不会修改 s'_i，因此 \text{cn} 中不为 0 的下标只有 s'_L,\dots,s'_R 这些，存储每次的 s'_i 并在重构时清空这些位置即可。单次时间复杂度为 \mathcal{O}(\sqrt{n+q})，一共 \mathcal{O}(q) 次，故总时间复杂度 \mathcal{O}(q\sqrt{n+q})。

综上，该做法时间复杂度为 \mathcal{O}(q\sqrt{n+q})，空间复杂度为 \mathcal{O}(n+q)。

AC Link / Code