发现时间并不重要,不妨设 TT 为离散化之后最大的时间。

设在 [i,j][i,j] 中有 wi,jw_{i,j} 个活动被包含,容易 O(n3)O(n^3) 求解。

设 fi,jf_{i,j} 表示 [1,i][1,i] 的时间中有 jj 个活动在第 11 个场地举行,第 22 个场地举行活动的最大值。

那么有转移方程:

fi,j=max⁡k=1i−1(fk,j+wk,i,fk,j−wk,i)f_{i,j}=\max\limits_{k=1}^{i-1}(f_{k,j}+w_{k,i},f_{k,j-w_{k,i}})

设 gi,jg_{i,j} 表示 [i,T][i,T] 的时间中有 jj 个活动在第 11 个场地举行,第 22 个场地举行活动的最大值。

同理,有转移方程:

gi,j=max⁡k=i+1T(gk,j+wk,i,gk,j−wk,i)g_{i,j}=\max\limits_{k=i+1}^T(g_{k,j}+w_{k,i},g_{k,j-w_{k,i}})

预处理的时间复杂度为 O(n3)O(n^3)。

那么第 11 问的答案就显然是:max⁡j=1nmin⁡(fT,j,j)\max\limits_{j=1}^n\min(f_{T,j},j)。

下面考虑固定一个活动的情况。

显然可以得到这个区间的左右端点 L,RL,R,那么枚举前后第 11 个场地分别举办了多少比赛:

AnsL,R=max⁡x=0w1,Lmax⁡y=1wR,Tmin⁡(x+wL,R+y,fL,x+gR,y)Ans_{L,R}=\max\limits_{x=0}^{w_{1,L}}\max\limits_{y=1}^{w_{R,T}}\min(x+w_{L,R}+y,f_{L,x}+g_{R,y})

发现如果固定 ii,那么fi,jf_{i,j} 和 gi,jg_{i,j} 的值随 jj 的值减增大而减小,所以当 ii 增加时 jj 应该尽可能的减少。

考虑维护双指针,那么时间复杂度为 O(n3)O(n^3)。