简要题意
给定 (n,k,{(a_i,b_i)}_{i=1}^n)，求出 (max{min_{i=1}^n{a_{p_i}+ik}-max_{i=1}^n{b_{p_i}+ik}|pin mathfrak{S}_n})。(1leq a_i,b_ileq 10^9,knleq 10^9,1leq nleq 10^5)。
题解
答案等价于 (max{min_{i=1}^n{a_i+q_ik}-max_{i=1}^n{b_i+q_ik}|qin mathfrak{S}_n})。进一步地，可以发现答案只与排列中的相对位置有关，于是 (q) 可以取数轴上的任意一段连续的 (n) 个整点（不妨设为 ([t,t+n-1]capmathbb{Z})）而不影响答案。
考虑枚举 (M=max{b_i+q_ik})，可以得到 (q_i) 的上界：(forall i,q_ileq r_i=leftlfloorfrac{M-b_i}{k} ight floor)。根据贪心策略，此时选择最大的有解的 (t) 一定最优。由 Hall 定理，此时 (t=min_{i=1}^n{r_i-i+1})。同时，注意到当 (M) 增加 (k) 时，(r_i) 和 (t) 都会增加 (1)，于是可以只在 ([0,k-1]) 的范围内枚举 (M)。
二分答案 (mid)，枚举 (Min[0,k-1])，可以得到 (q_i) 的上下界：(forall i,l_i=max{leftlceilfrac{M+mid-a_i}{k} ight ceil,t}leq q_ileq r_i=min{leftlfloorfrac{M-b_i}{k} ight floor,t})。由 Hall 定理，此时有解当且仅当不存在一个区间 ([l,r](lleq r))，使得 (s(l,r)>r-l+1)，其中 (s(l,r)) 表示被 ([l,r]) 包含的 ([l_i,r_i]) 区间个数。
注意到 (t) 在 (M) 从 (0) 到 (k-1) 枚举的过程中只会增加 (1)（或不变），不妨设为从 (t') 变为 (t'+1)，变化的时间为 (tt)（若不变，则为 (infty)）。接下来，只需要分别对 (Min[0,tt-1],t=t') 与 (Min[tt,k-1],t=t'+1) 分别判断即可。
考虑对 (Min[L,R]) 和确定的 (t) 进行判断。注意到 (R-L+1<=k)，于是 (l_i,r_i) 在 (M) 从 (L) 到 (R) 枚举的过程中只会增加 (1)（或不变），不妨分别设为从 (l_i',r_i') 变为 (l_i'+1,r_i'+1)，变化的时间为 (tl_i,tr_i)（若不变，则为 (infty)）。
对 (r_i) 进行排序。记 (q(i,j)=r_j-l_i+1-s(l_i,r_j))，那么有解当且仅当不存在 (i<j) 使得 (q(i,j)<0)。注意到 (l_i) 之间、(r_i) 之间的相对顺序不会改变，于是 (s(l_i,r_j)) 不会改变。那么只需要对 (q'(i,j)=r_j'-l_i'+1-s(l_i,r_j)) 进行分类讨论：
- 当 (q'(i,j)<-1) 时，恒非法；
- 当 (q'(i,j)=-1) 时，当且仅当 (tr_jleq M<tl_i) 时合法；
- 当 (q'(i,j)=0) 时，当且仅当 (tl_ileq M<tr_j) 时非法；
- 当 (q'(i,j)>0) 时，恒合法。
注意到固定 (j) 时，同种限制取最小的 (tl_i) 一定最紧。于是可以从小到大枚举 (r_j')，用线段树维护 (q'(i,j)) 的最小值和次小值以及此时分别对应的最小的 (tl_i)（这样当不存在 (q'(i,j)<-1) 的情况时能得到所有限制）。
最终会得到 (O(n)) 个限制，对于 (q'(i,j)=-1) 得到的限制可以轻松求出它们的交，然后将 (q'(i,j)=0) 得到的限制排序后和前面求得的交进行对称差判断即可。
时间复杂度 (O(nlog nlog A))，其中 (A) 是答案的值域大小（此题中为 (2 imes10^9)）。