题解 P6958 【[NEERC2017]The Great Wall】

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

i=1nai[iXiY]+i=1nbi[iXiY]+i=1nci[iXiY]\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]

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

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

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

X,YX,Y 无交即 x+ryx+r\le y,则该方案的权值为 Ax+Bx+rBx+AyAx+r+By+rBy+AnAy+rA_x+B_{x+r}-B_x+A_y-A_{x+r}+B_{y+r}-B_y+A_n-A_{y+r}。把上式中与 yy 有关的项记作 F(y)F(y),无关的项记作 G(x)G(x)。如果枚举 xx,相当于对每个 xx 求满足 F(y)<mG(x)F(y)<m-G(x)yx+ry\ge x+ryy 的数量。可以使用平衡树,从大到小枚举 xx,一边插入 F(x+r)F(x+r),一边查询平衡树中小于 mG(x)m-G(x) 的数的数量。

X,YX,Y 有交即 x<y<x+rx<y<x+r,则该方案的权值为 Ax+ByBx+Cx+rCy+By+rBx+r+AnAy+rA_x+B_y-B_x+C_{x+r}-C_y+B_{y+r}-B_{x+r}+A_n-A_{y+r}。可以用类似的方法,区别在于 yy 的范围变为了 x<y<x+rx<y<x+r,可以先求出 y>xy>x 的方案数,再把 yx+ry\ge x+r 的减去。

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