题解 P6958 【[NEERC2017]The Great Wall】

简要题意：给定三个长度为 $n$ 的整数数组 $a,b,c$ 和整数 $r$，且满足对于任意 $1\le i\le n$ 都有 $a_i<b_i<c_i$。在区间 $[1,n]$ 的所有长度为 $r$ 的子区间里不分顺序地选出两个，记作 $X,Y$。定义这次选择的权值为：

$\sum_{i=1}^na_i[i\notin X\land i\notin Y]+\sum_{i=1}^nb_i[i\in X\oplus i\in Y]+\sum_{i=1}^nc_i[i\in X\land i\in Y]$

求所有 $\frac{(n-r)(n-r+1)}{2}$ 种不同的选择方式中，权值第 $k$ 小的选择的权值是多少。

考虑二分答案。设当前二分中点为 $m$，统计权值小于 $m$ 的选择方案数，若大于 $k-1$ 则答案小于 $m$，否则答案大于等于 $m$。

令数组 $A,B,C$ 分别为 $a,b,c$ 的前缀和数组。令 $X=[x+1,x+r],Y=[y+1,y+r]$。由于 $X,Y$ 不分顺序，不妨设 $x<y$。按照 $X,Y$ 是否有交分类讨论，分别计算两类的选择方案数。

若 $X,Y$ 无交即 $x+r\le y$，则该方案的权值为 $A_x+B_{x+r}-B_x+A_y-A_{x+r}+B_{y+r}-B_y+A_n-A_{y+r}$。把上式中与 $y$ 有关的项记作 $F(y)$，无关的项记作 $G(x)$。如果枚举 $x$，相当于对每个 $x$ 求满足 $F(y)<m-G(x)$ 且 $y\ge x+r$ 的 $y$ 的数量。可以使用平衡树，从大到小枚举 $x$，一边插入 $F(x+r)$，一边查询平衡树中小于 $m-G(x)$ 的数的数量。

若 $X,Y$ 有交即 $x<y<x+r$，则该方案的权值为 $A_x+B_y-B_x+C_{x+r}-C_y+B_{y+r}-B_{x+r}+A_n-A_{y+r}$。可以用类似的方法，区别在于 $y$ 的范围变为了 $x<y<x+r$，可以先求出 $y>x$ 的方案数，再把 $y\ge x+r$ 的减去。

总时间复杂度为 $O(n\log n\log C_n)$，其中$C_n$ 作为二分的初始右边界。