怎么快速求数列(A[i]+A[j])*(j-i)的最大值

可以用李超树维护凸壳

希望能对您有帮助

这个李超树随便维护吧

主要有一个A[i]*j的东西

然后推式子化成kX+b的形式

直接上李超树就ok了

🤣🤣🤣

您看看理解吗？

😂😂😂

😁😁😁

由于同时和a[j]和j有关所以不能单纯维护当作斜率相关的问题来做 本问题是经典的决策单调性问题。 考虑我们选择j时如果j1>j2且a[j1]>a[j2]显然j2时候不如j1，因此我们用单调队列筛掉这些不符合条件的j2，最后得到一个单调下降子序列。 同理，选择i时如果i1<i2且a[i1]>a[i2]显然i2时候不如i1，帅选后i的选择区域也将在一个单调上升子序列中。 现在在一个单调上升子序列中选择i，一个单调下降子序列中选择j。 接下来考虑j对i1和i2的值f(i1,j)=(A[i1]+A[j])*(j-i1),f(i2,j)=(A[i2]+A[j])*(j-i2)作差 不妨设i1>i2 f(i1,j)-f(i2,j)=j*(A[i1]-A[i2])-(A[i1]*i1-A[i2]*i2)-A[j]*(i1-i2)               =(A[i1]-A[i2],i1-i2)·(j,-a[j])-(A[i1]*i1-A[i2]*i2) 显然，随着j的增大f(i1,j)-f(i2,j)单调递增，也就是说，对于任意i1，i2存在一个在j0之后 (f(i1,j)-f(i2,j))*(j-j0)>=0 故我们在i待选择的单调上升子序列中的每个相邻元素计算其分界的j即可。具体实现就是用一个单调栈维护每个分界点，每次对相邻两个元素二分其分界点，然后维护单调栈。 1.得到i的候选序列I={i1,i2...ip} 2.得到j的候选序列J={j1,j2...jq} 3.初始单调栈s为空 4.枚举x，根据f(ix,j)-f(ix+1,j)的算出分界点jx，将jx比栈顶元素小，不断把元素踢出，然后加入jx 5.根据单调栈中的元素，得到每个序列J最优的决策ix，计算，并求最大值。 PS:这个问题转化称这样可能更好理解，二维的点集A={(i,a[i])},B={(i,-a[i])}，在A中取一个点，在B中取一个点，最后要求其面积最大，当然最后做法本质没区别

(A[i]+A[j])*(j-i) = A[i]*i - j*A[j] 很明显，j*A[j]是一个定值，枚举i=[1,n]，然后记录前缀最小的 j*A[j]就行了